数据结构 课程设计报告 魔王语言解释.docx
题目：魔王语言解释问题描述有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听懂, 但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式 的规则由人的语言逐步抽象上去的：(1) a->3 1323m (2) ( 0 6 1 6 25n) >0 5n0 6 n-l0519在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把 他的话解释成人能听得懂的话；基本要求用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言 的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母 代换的变量。魔王语言可含人的词汇。(1) B->tAdA(2) A->sae测试数据B (ehnxgz) B 解释成 tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一 只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。TdSaeZgXnh天地上只鹅追赶蛋恨实现提示将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈， 将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。 其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本操作。while(el!=,),)EnQueue(Q,el);Pop(S,el);if(!QueueEmpty(Q)DeQueue(Q,key);)elsePush(temp9el);f=0;)while(!StackEmpty(temp)边处理边进栈Pop(temp,el);if(el !=flag)把括号外的元素压入中Pusgel);elsewhiIe(!QueueEmpty(Q)处理括号中的元素进栈DeQueue(Q,e2);Push(S,key);Push(S,e2);if(f!=O)最后还要压一个keyPush(S,key);)printf解释后的语言为：nn);while(!StackEmpty(S)依次出栈输出处理后的元素Pop(S,e);EnQueue(Q,e); 元素进队是为了输出对应汉字if(e=fB,)printf(H%s,B);else if(e='A')printf(H%s,A);) else(printf(H%c,e);源代码#include<stdio.h>#include<stdlib.h>#define STACKJNIT.SIZE 100#define STACK_INCREMENT 10struct Stackchar* base;char* top;int stacksize;);void InitStack(struct Stack &s)构造栈s.base=(char)malloc(STACK_INIT_SIZEsizeof(char);s.top=s.base;s.stacksize=STACK INIT SIZE;)void Push(struct Stack &s9char e)压入元素if(s.top-s.base>=STACK_INIT_SIZE)s.base=(char*)realloc(s.baseXs.stacksize+STACK_INCREMENT)：5：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;)elsereturn 0;)void ClearStack(struct Stack &s) s.top=s.base;)struct Queuechar data;struct Queue* next;)；struct LinkQueuestruct 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(chL!=,0,)L+;)for(i=L-l;i>=0;i)Push(s,chi);int main()int i=0;char A=Hsaen;char B=ntsaedsaeH;char flag=,O,;/flag用来标记处理括号int mark=l;int f=0;struct Stack S;struct Stack temp;用来处理括号外的元素InitStack(S);InitStack(temp);struct LinkQueue Q;InitQueue(Q);char MoWang100=n0n;char el,key,e2,e; a / f f -J>.上«£« .J*7*7，<2* !*, * rj* rj* r|. rj. rj. rj* rj* r|. rj. rj. rj. rj* rj> rjw rj. rj. rj* rj* rj* r|. r1. rj. rj. rj* rj* r|. rj. rj. rj* rj> rjw rj. rj. rj* rj* rj* r|. r1. rj. rj. rj* rj* r|. rj. rj. rj* rj> rjw rj. rj. rj* rj* rj* r|. r1. r1.n'')；printf(H欢迎光临广东工业大学printf(''*n”)；printf(''*printf(''*n”)；print*"*printf(''*n，)；1* «£ 小rj* rj* rj* rj* rj*rj* rj* r|* r|w rj* rj* rj* rj* r|* r|* rj*rj rj* rj* rj* rj* rj* rj* 魔王语言解释系统 *«A» r1* rj* r|*rj* r|> rj* rjw rj> rj* rj* rj* r|>rj rj* rj* r|* rj*班级:计算机学院网络工程2007级4班姓名：黄文龙 学号：3107007087printf(| f *#*2*2 *2 *2*2 *2*2 *2*2 *2 2* *2* *1*2 *2*#<2 <2#*2 *2 *2>* *f#*£# *2 <2*# <2* *!> rj* rj* rj* rj* rj* rj> rj* rjw rj> rj> rj> rj> rjw rj> ej> <J> rj* rj> rj* rj* , rj* rj> rjw rj> ej> rj> rj« rj> rj> ej, rj* rj* rj* rj* rj* rj rj* rj* rj> rj> rj* rj« rj> rj>nnn);printf请输入你想要解释的魔王语言（最多含有一个括号）：n”）;gets(MoWang);InStack(MoWang,S); 把要解释的魔王语言压入栈中while(!StackEmpty(S)Pop(S,el);if(el=,(t)if(StackEmpty(S)printf("魔王语言错误!n")；mark=0;break;)while(!StackEmpty(S)Pop(S,el);if(el=')')f=l;break;)else if(!(el>=,a,&&el<=tz,)&&!(el>=,At&&el<=,Z,)priiHf("魔王语言错误！ n");mark=O;break;)if(mark=O)break;)if(f!=l)printf(“魔王语言错误！ nn);break;)else if(el=,),)printf魔王语言错误！ n")；mark=O;break;)else if(!(el>=,a,&&el<=,zt)&&!(el>=,A,&&el<=,Z,)printf("魔王语言错误！ nu);mark=O;break;)if(mark=l&&f=l)ClearStack(S);InStack(MoWang,S);while(!StackEmpty(S)栈不空时Pop(S,el);if(el=tB,)Push(temp,el);else if(el=,A,)Push(temp,el);)else if(el=T)用队存储括号中的元素Push(temp,flag);有括号的话就用flag标Pop(S,el);
