魔王语言解释

发表于 分类于

问题输入
一组数据，数据为一个字符串，表示一个待翻译的字符串。
问题输出
将字符串按规则翻译后输出。
输入样例
B(pxyzABhij)B
输出样例
tsaedsaepjpiphptsaedsaepsaepzpypxptsaedsae

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxsize 100
typedef struct{
	char *base;
	char *top;
	int size; 
}sqStack;   
//构造栈
int InitStack(sqStack *S){
	S->base=(char *)malloc(sizeof(char)*maxsize);
	if(!S->base) exit(0);
	S->size=maxsize;
	S->top=S->base;
	return 1;
} 
//出栈 
int GetTop(sqStack *S,char *c){
	if(S->top==S->base) return 0;
	else *c=*--S->top;
	return 1;
}
//入栈 
int Push(sqStack *S,char c){
	*S->top++=c;
	return 1;
} 
typedef struct QNode * LNode;
struct QNode{
	char data;
	LNode next;
};
typedef struct{
	LNode front;  //队头指针 
	LNode rear;   //队尾指针 
}LinkQueue;
//构造队列 
int InitQueue(LinkQueue *Q){
	Q->front=Q->rear=(LNode)malloc(sizeof(struct QNode));
	Q->front->next=NULL;
	return 1;
}
//入队
int PushQueue(LinkQueue *Q,char c){
	LNode p=(LNode)malloc(sizeof(struct QNode));
	p->data=c;
	p->next=NULL;
	Q->rear->next=p;
	Q->rear=p;
	return 1; 
} 
//出队
int GetQueue(LinkQueue *Q,char *c){
   if(Q->rear==Q->front) return 0;
   LNode p=Q->front->next;
   *c=p->data;
   Q->front->next=p->next;
   if(Q->rear==p) Q->rear=Q->front;
   return 1;
} 
int main(){
	char st[1000],a;
	scanf("%s",st);
	//puts(st);
	sqStack S1,S2;
	LinkQueue L;
	InitQueue(&L);
	InitStack(&S1);
	InitStack(&S2);
	//将字符串从右向左依次入栈 
	for(int i=(strlen(st)-1);i>=0;i--){
		Push(&S1,st[i]);
	}  
	//处理括号内容 
	while(S1.base!=S1.top){
		char r;
		GetTop(&S1,&r);
		if(r!=')'){
			Push(&S2,r);
		} 
		else if(r==')'){
			char C;
			GetTop(&S2,&a);
			while(a!='('){
				PushQueue(&L,a);
				C=a;
				GetTop(&S2,&a);
			}
			while(L.front->next!=L.rear){
				char b;
				GetQueue(&L,&b);
				Push(&S2,C);
				Push(&S2,b);
			}
			Push(&S2,C);
		}
		
	}
    //B和A转化
	while(S2.base!=S2.top){
		char n;
		char A[4]="sae";
		char B[9]="tsaedsae";
		GetTop(&S2,&n);
		if(n!='A'&&n!='B'){
			Push(&S1,n);
		}
		else if(n=='A'){
			for(int i=2;i>=0;i--){
				Push(&S1,A[i]);
			}
		}
		else if(n=='B'){
			for(int i=7;i>=0;i--){
				Push(&S1,B[i]);
			}
		}
	} 
	char m;
	while(S1.base!=S1.top){
		GetTop(&S1,&m);
		printf("%c",m);
	}
}

主要是考察栈和队列，建议画图解决。