数据结构魔王语言解释c语言实现

[数据结构]魔王语言解释c语言实现[基本要求]

用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。

（1）B－>tAdA

（2）A－>sae

[测试数据]

B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae【实现】将需要解释的魔王语言当成一个字符数组，入栈1。再依次出栈，入栈2，依次处理顶端字符，若是开括号逐一出栈入队列，直至闭括号出栈。再逐一出队列，按照规则2解释，再重新入栈2。出栈2，按照规则1解释。#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>typedefstructNode//节点{chardata;structNode*next;}Node,*NodePtr;typedefstructStak //栈链表{NodePtrtop;NodePtrbot;intcount;}Stak;//初始化栈voidInitStak(Stak*ts) {ts->top=(NodePtr)malloc(sizeof(Node));if(NULL==ts->top){printf("分配失败");exit(-1);}ts->bot=ts->top;ts->count=0;ts->top->next=NULL;}//入栈voidPush(Stak*S,chare) {NodePtrpnew=(NodePtr)malloc(sizeof(Node));pnew->data=e;pnew->next=S->top;S->top=pnew;S->count++;}//出栈charPop(Stak*S) {NodePtrp;if(S->bot==S->top){//空时返回1删除失败exit(1);}p=S->top;chare=p->data;S->top=S->top->next;free(p);S->count--;returne;}//打印栈voidprin(Stak*S){NodePtrp;p=S->top;while(p!=S->bot){printf("%c\n",p->data);p=p->next;}}boolEmptyStack(Stak*S)//判断是否空栈{if(S->count==0)return1;return0;}typedefstructQNode //队列节点{chardata;structQNode*next;}QNode,*QNodePtr;typedefstructLinkQueue //队列链表{QNodePtrfront,rear;}Queue;//队列初始化voidInitQue(Queue*Q){QNodePtrp=(QNodePtr)malloc(sizeof(QNode)); //p为头节点p->data=NULL;p->next=NULL;Q->front=p;Q->rear=p;}//入队列voidEnQue(Queue*Q,chare){QNodePtrp=(QNodePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p;}charDeQue(Queue*Q)//出队列{QNodePtrp;charc;if(Q->front==Q->rear){//空时exit(1);}p=Q->front->next;c=Q->front->next->data;Q->front->next=p->next;if(p==Q->rear){Q->rear=Q->front;}free(p);returnc;}voidpri(Queue*Q)//打印队列{QNodePtrp;p=Q->front;if(p!=NULL){while(p!=Q->rear){printf("%c",p->next->data);p=p->next;}}}boolEmptyQue(Queue*Q){if(Q->front==Q->rear)return1;return0;}voidReverse(charM[],Stak*S){inti;intlen=strlen(M);intl=0,r=0;for(i=0;i<len;i++){Push(S,M[i]);if(M[i]=='(')l++;if(M[i]==')')r++;}if(l!=r)exit(1);}voidEnA(Queue*Q)//规则1{EnQue(Q,'s');EnQue(Q,'a');EnQue(Q,'e');}voidEnB(Queue*Q)//规则1{EnQue(Q,'t');EnA(Q);EnQue(Q,'d');EnA(Q);}voidFpri(Queue*Q){charc;while(!EmptyQue(Q)){c=DeQue(Q);switch(c){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;default:printf("Error");}}}voidTran(Stak*Sbe,Stak*Saf,Queue*Q){charc;chard;inti=0;while(Sbe->count!=0){c=Pop(Sbe);if(c==')')i=Saf->count;elseif(c=='('){intj=Saf->count;while(j>i){d=Pop(Saf);EnQue(Q,d);j--;}chare=Q->front->next->data;DeQue(Q);while(!EmptyQue(Q))//规则2{chardl=DeQue(Q);Push(Saf,e);Push(Saf,dl);}Push(Saf,e);}elsePush(Saf,c);}while(Saf->count>0){charen;en=Pop(Saf);if(en=='A')EnA(Q);elseif(en=='B')EnB(Q);elseEnQue(Q,en);}Fp