- #include<stdio.h>
- #include<stdlib.h>
- #define STACK_INIT_SIZE 100
- #define STACK_INCREMENT 10
- struct Stack{
- char* base;
- char* top;
- int stacksize;
- };
- void InitStack(struct Stack &s){//构造栈
- s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
- s.top=s.base;
- s.stacksize=STACK_INIT_SIZE;
- }
- void Push(struct Stack &s,char e){//压入元素
- if(s.top-s.base>=STACK_INIT_SIZE){
- s.base=(char*)realloc(s.base,(s.stacksize+STACK_INCREMENT)*sizeof(char));
- s.top=s.base+s.stacksize;
- s.stacksize+=STACK_INCREMENT;
- }
- *(s.top)=e;
- s.top++;
- }
- void Pop(struct Stack &s,char &e){//取出元素
- e=*--s.top;
- }
- int StackEmpty(struct Stack s){//栈是否为空
- if(s.top==s.base){
- return 1;
- }
- else{
- return 0;
- }
- }
- void ClearStack(struct Stack &s){
- s.top=s.base;
- }
- struct Queue{
- char data;
- struct Queue* next;
- };
- struct LinkQueue{
- struct Queue* front;
- struct Queue* rear;
- };
- void InitQueue(struct LinkQueue &q){//构造队
- q.front=q.rear=(struct Queue*)malloc(sizeof(struct Queue));
- q.front->next=NULL;
- }
- void EnQueue(struct LinkQueue &q,char e){//元素入队
- struct Queue* p;
- p=(struct Queue*)malloc(sizeof(struct Queue));
- p->data=e;
- p->next=NULL;
- q.rear->next=p;
- q.rear=p;
- }
- void DeQueue(struct LinkQueue &q,char &e){//元素出队
- struct Queue* p;
- p=q.front->next;
- e=p->data;
- q.front->next=p->next;
- if(q.rear==p){
- q.rear=q.front;
- }
- free(p);
- }
- int QueueEmpty(struct LinkQueue q){//队是否为空
- if(q.front==q.rear){
- return 1;
- }
- else{
- return 0;
- }
- }
- void InStack(char* ch,struct Stack &s){//把字符数组从右至左压入栈中
- int i,L=0;
- while(ch[L]!='\\0'){
- L++;
- }
- for(i=L-1;i>=0;i--){
- Push(s,ch[i]);
- }
- }
- int main(){
- int i=0;
- char A[]="sae";
- char B[]="tsaedsae";
- char flag='0';//flag用来标记处理括号
- int mark=1;
- int f=0;
- struct Stack S;
- struct Stack temp;//用来处理括号外的元素
- InitStack(S);
- InitStack(temp);
- struct LinkQueue Q;
- InitQueue(Q);
- char MoWang[100]="\\0";
- char e1,key,e2,e;
- printf("请输入你想要解释的魔王语言(最多含有一个括号):\\n");
- gets(MoWang);
- InStack(MoWang,S);//把要解释的魔王语言压入栈中
- while(!StackEmpty(S)){
- Pop(S,e1);
- if(e1=='('){
- if(StackEmpty(S)){
- printf("魔王语言错误!\\n");
- mark=0;
- break;
- }
- while(!StackEmpty(S)){
- Pop(S,e1);
- if(e1==')'){
- f=1;
- break;
- }
- else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z')){
- printf("魔王语言错误!\\n");
- mark=0;
- break;
- }
- }
- if(mark==0){
- break;
- }
- if(f!=1){
- printf("魔王语言错误!\\n");
- break;
- }
- }
- else if(e1==')'){
- printf("魔王语言错误!\\n");
- mark=0;
- break;
- }
- else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z')){
- printf("魔王语言错误!\\n");
- mark=0;
- break;
- }
- }
- if(mark==1&&f==1){
- ClearStack(S);
- InStack(MoWang,S);
- while(!StackEmpty(S)){//栈不空时
- Pop(S,e1);
- if(e1=='B'){
- Push(temp,e1);
- }
- else if(e1=='A'){
- Push(temp,e1);
- }
- else if(e1=='('){//用队存储括号中的元素
- Push(temp,flag);//有括号的话就用flag标记
- Pop(S,e1);
- while(e1!=')'){
- EnQueue(Q,e1);
- Pop(S,e1);
- }
- if(!QueueEmpty(Q)){
- DeQueue(Q,key);
- }
- }
- else{
- Push(temp,e1);
- f=0;
- }
- }
- while(!StackEmpty(temp)){//边处理边进栈
- Pop(temp,e1);
- if(e1!=flag){//把括号外的元素压入中
- Push(S,e1);
- }
- else{
- while(!QueueEmpty(Q)){//处理括号中的元素进栈
- DeQueue(Q,e2);
- Push(S,key);
- Push(S,e2);
- }
- if(f!=0){//最后还要压一个key
- Push(S,key);
- }
- }
- }
- printf("解释后的语言为:\\n");
- while(!StackEmpty(S)){//依次出栈输出处理后的元素
- Pop(S,e);
- EnQueue(Q,e);//元素进队是为了输出对应汉字
- if(e=='B'){
- printf("%s",B);
- }
- else if(e=='A'){
- printf("%s",A);
- }
- else{
- printf("%c",e);
- }
- }
- printf("\\n");
- while(!QueueEmpty(Q)){//输出对应汉字
- DeQueue(Q,e);
- switch(e){
- case 't': printf("天");break;
- case 'd' : printf("地"); break;
- case 's' : printf("上"); break;
- case 'a' : printf("一只"); break;
- case 'e' : printf("鹅"); break;
- case 'z' : printf("追"); break;
- case 'g' : printf("赶"); break;
- case 'x' : printf("下"); break;
- case 'n' : printf("蛋"); break;
- case 'h' : printf("恨"); break;
- case 'B' : printf("天上一只鹅地上一只鹅");break;
- case 'A' : printf("上一只鹅");break;
- default : printf("*");break;
- }
- }
- printf("\\n");
- }
- system("pause");
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/190320132484.html
来源: http://www.codesnippet.cn/detail/190320132484.html