魔王语言解释

实习报告 题目：编制一个魔王语言解释的程序 班级：06052711 姓名：曹旭 学号：06057104 完成日期：2007.11.27一、 需求分析问题描述 有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂。但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐 步抽象上去的： （1）-12.n（2）(12.n)-nn-1.1 在这两种形式中，从左到右均表示解释；从右到左表示抽象。试写一个魔王解释系统，把 他的话解释成人能听懂得话。 基本要求 用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字 母表示人的语言词汇；希腊字母（a,b1,s,y1等）表示可以用大写或小写字母代换的变量。 魔王语言可含人的词汇。 （1）B-tAdA (2) A-sae 测试数据 B（einxgz）B 解释成 tsaedsaeezegexeneietsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅 鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅。” t d s a e z G x n i 天 地 上 一个 鹅 追 赶 下 蛋 恨 实现提示 将魔王的语言自右至左进栈，总是处理栈顶。若是开括号，则逐一出栈，将字母顺序入队 列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者 思考如何处理，应首先实现栈和队列的基本运算二、 概要设计 为实现上述程序功能，应以栈和队列来表示。1. 设定栈的抽象数据类型定义为： ADT Stack 数据对象：D=ai | aiCharSet，I=1，2，.，n,n0 数据关系：R1= |ai-1，aiD,I=1，2，.，n 基本操作： ListInitiate (&S) 操作结果：构造一个空栈S。StackEmpty（S）初始条件：栈S已经存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。Push（&S,e）初始条件：栈S已经存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop（&S,&e）初始条件：栈S已经存在。操作结果：删除S的栈顶元素，并以e返回其值。 ADT Stack2. 设定队列的抽象数据类型定义为：ADTQueue 数据对象：D=ai | aiElemSet，I=1，2，.，n,n0 数据关系：R1= |ai-1，aiD,I=1，2，.，n 基本操作： ListInitiate (&Q) 操作结果：构造一个空队列Q。StackEmpty（Q）初始条件：队列Q已经存在。操作结果：若队列Q为空栈，则返回TRUE，否则返回FALSE。EnQueue（&Q,e）初始条件：队列Q已经存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue（&Q,&e）初始条件：队列Q已经存在。操作结果：删除Q的对头元素，并以e返回其值。 ADT Queue2. 程序包含四个模块：1） 主程序模块：Void main()初始化；For（）接受处理命令；接受处理；2） 栈模块实现栈的抽象数据类型；3） 队列模块实现队列的抽象数据类型。4） 魔王语言解释模块定义线性表的结点结构。各模块的之间的调用关系如下： 主程序模块 魔王语言解释模块 栈模块队列模块三、 详细设计1. 站类型typedef structchar *base;char *top;int stacksize;stack;2. 队列类型typedef struct QNodechar data;struct QNode *next;QNode,*LinkQueueNode;typedef structLinkQueueNode front;LinkQueueNode rear;LinkQueue;3.栈的基本操作int Initstack(stack &s) s.base=(char*)malloc(100*sizeof(char); if(!s.base)exit(0); s.top=s.base; s.stacksize=100; return 1;int IsEmpty(stack s) if(s.top=s.base)return 1;return 0;void push(stack &s,char e)if(s.top-s.base=s.stacksize)s.base=(char*)realloc(s.base,(s.stacksize+10)*sizeof(char);if(!s.base)exit(0);s.top=s.base+s.stacksize;s.stacksize+=10;*s.top+=e;int pop(stack &s,char &e)if(s.top=s.base)exit(0);e=*-s.top;return 1;4队列的基本操作int initQueue(LinkQueue &Q)Q.front=Q.rear=(LinkQueueNode)malloc(sizeof(LinkQueueNode);if(!Q.front)exit(-1);Q.front-next=NULL;return 1;int Isempty(LinkQueue Q)if(Q.front=Q.rear)return 1;return 0;int EnQueue(LinkQueue &Q,char e)LinkQueueNode p;p=(LinkQueueNode)malloc(sizeof(QNode);if(!p)exit(-1);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return 1;char DeQueue(LinkQueue &Q,char &e) LinkQueueNode p;if(Q.front=Q.rear)return 0;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return e;5.求魔王语言解释的伪码算法：void transmite(stack S) LinkQueue Q; initQueue(Q); char c,e,ch; char A3=s,a,e; char B8=t,s,a,e,d,s,a,e; printf(魔王要说的话是：); while(!IsEmpty(S) pop(S,e); if(e=B) printf(tsaedsae); else if(e=A) printf(sae); else if(e=() while(pop(S,e)&e!=) EnQueue(Q,e); push(S,e); DeQueue(Q,c); while(!Isempty(Q) DeQueue(Q,e); push(S,c); push(S,e); push(S,c); while(!IsEmpty(S) pop(S,e); if(e=)break; else if(e=B)printf(tsaedsae);else if(e=A) printf(sae);else printf(%c,e); else printf(%c,e); printf(n);6.主函数和其他函数的算法：void main() bool flag=1; char str,c; while(flag=1) stack S; Initstack(S); char a100; printf(魔王说话了：); int i=0; cina; while(ai)i+; for(int k=i;k=0;k-) push(S,ak); transmite(S);printf(n是否需要继续？是的话请按y: );scanf(%c,&str);if(str=y)flag=1;else flag=0;c=getchar(); 7调用函数关系图反映了演示程序的层次结构： main Initiate transmiteInitiate pop push EnQueue DeQueue Isempty四调试分析1.对&的用法明白了许多。原来有点看不懂标识符&，使调试程序时费了我不少的时间。通过本次实验调试，让我明白了&用法。2.函数调用。函数调用是语言中一块十分重要部分，它可以把一个程序分成若干部分，然后进行配置，所以这块内容一定要学好。3，栈和队列问题比较简单。4，由于考虑不周，如果同样的字母出现时，规则会要求重复输入，最终以最后一个为准，这是一个失误，后来改正程序，过滤掉重复字母，从而实现了简洁正确输入规则。五用户手册 1、本程序运行在DOS命令下 2、进入程序后即显示用户界面：*魔王语言解释系统*魔王说话了：3、注意输入后即可得到相应的结果。六、测试结果 魔王说话了：B(aAb)A 魔王要说的话是：tsaedsae(b(sae(a()sae七、附录 源程序文件名清单： base .H /公用的常量和类型 stkpas.H /栈类型 testmaze.C /主程序