《数据结构-课程设计报告-魔王语言解释》由会员分享，可在线阅读，更多相关《数据结构-课程设计报告-魔王语言解释（11页珍藏版）》请在金锄头文库上搜索。
1、 题目：魔王语言解释问题描述有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）-12m（2）（12n）nn-11在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话；基本要求用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。（1）B-tAdA（2）A-sae测试数据B（ehnxgz）B解释成tsaedsaeeze
2、gexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。Tdsaezgxnh天地上一只鹅追赶蛋恨实现提示将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本操作。源代码 #include#include#define STACK_INIT_SIZE 100#define STACK_INCREMENT 10struct Stack char* ba
3、se; 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(
4、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* nex
5、t; ;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
6、-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
7、Stack &s)/把字符数组从右至左压入栈中 int i,L=0; while(chL!=0) L+; for(i=L-1;i=0;i-) Push(s,chi); 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 MoWa
8、ng100=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=A&e1=a&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!=)
