魔王语言解释

学号：课程设计题目魔王语言解释学院计算机科学与技术学院专业计算机科学与技术专业班级姓名指导教师2011年07月03日武汉理工大学《数据结构》课程设计说明书1课程设计任务书学生姓名：专业班级：指导教师：工作单位：计算机科学系题目:魔王语言解释初始条件：有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α→β1β2…βm（2）(θδ1δ2…δn)→θδnθδn-1…θδ1θ在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，用下述两条具体规则和上述规则形式（2）实现，把他的话解释成人能听得懂的话。（1）B→tAdA（2）A→sae设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。测试用例见题集p97。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1、问题描述简述题目要解决的问题是什么。2、设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、经验和体会（包括对算法改进的设想）5、附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第20周（6月29日至7月3日）完成。2、7月3日8：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名：年月日系主任（或责任教师）签名：年月日武汉理工大学《数据结构》课程设计说明书2题目：魔王语言解释1问题描述和分析1.1问题重述有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α→β1β2…βm（2）(θδ1δ2…δn)→θδnθδn-1…θδ1θ在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，用下述两条具体规则和上述规则形式（2）实现，把他的话解释成人能听得懂的话。（1）B→tAdA（2）A→sae设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。1.2问题分析重要数据结构包括一个栈和一个辅助队列，一张记录大写字母处理规则的表以及记录闭合左括号对应的括号表达式的表。处理方法是从左至右依次读入待翻译的字符串，根据读入字符做出不同操作。如果读到小写字母，如果当前栈中压入的左括号数目为0，则直接输出，否则入栈；如果读到大写字母，如果当前栈中压入的左括号数目为0，则输出大写字母对应的规则，否则入栈；如果读到左括号，记下在串中的位置，然后入栈；如果读到右括号，则依次弹出栈中的元素并将这些元素加入辅助队列，直到弹出左括号为止。如果当前栈中压入的左括号数目为0，则根据括号内表达式处理规则将队列中存放的从栈中弹出的元素输出，否则将这些元素加入对应左括号位置的表项中进行记录，并生成记录左括号位置的元素然后压栈。最后处理完毕后，翻译后的串输出并且队列和栈中为空。2设计2.1存储结构设计2.1.1设定栈的抽象数据类型:ADTStack｛数据对象：D＝｛ai|ai∈ElemSet,i＝1,2,…,n,n=0｝数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i＝2,…,n}基本操作：Initstack(＆S)操作结果:构造一个空栈S。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回true，否则false。武汉理工大学《数据结构》课程设计说明书3ClearStack（&S）初始条件：栈S已存在操作结果：将S清为空栈Push(＆S,e)初始条件:栈S已存在。操作结果:在栈S的栈顶插入新的栈顶元素e。Pop(＆S,＆e)初始条件:栈s已存在。操作结果:删除S的栈顶元素,并以e返回其值。}ADTStack2.1.2设定队列的抽象数据类型:ADTQueue{数据对象：D＝｛ai|ai∈Elemset,i＝1,2,…,n,n=0｝数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i＝2,…,n}基本操作：Initqueue(&Q)操作结果:构造一个空队列Q。Enqueue(&Q,e)初始条件:队列Q已存在。操作结果:插入元素e为Q的新的队尾元素。Dequeue(&Q,&e)初始条件:Q为非空队列。操作结果:删除Q的队头元素,并用e返回其值。}ADTqueue2.2主要算法设计2.2.1算法文字描述（1）以一维数组demon[]表示魔王语言。（2）魔王语言由用户输入,初始保存在demon[]中。（3）魔王语言与人类语言对应关系固化在程序中。（4）实现过程：A：初始，魔王语言接收后存放在demon[i]中。B：初次遍历数组，将数组中括号内的元素入栈。C：利用栈结构对输入的魔王语言语法进行检查。D：再次遍历数组demon[],将数组中括号内的元素入栈,同时插入相应首字母。E：再次遍历数组，将数组元素依次入队。（小写字母直接入队；大写字母经翻译成相应字符后入队；遇到括号，将栈中保存的元素依次出栈入队）在翻译过程中，如果依旧包含大写字母，则置flag为1，否则为0。F：将队列中元素赋值给demon[i]。如果此时flag=1，则再次重复E过程。直至所有元素为人类语言。G：输出demon[i]。此时数组中元素为对应的人类语言。注：如果程序中没有相应的对应关系，则翻译成“*”。武汉理工大学《数据结构》课程设计说明书42.2.2程序包含模块:（1）主函数模块。其中主函数为:intmain(){初始化栈;初始化队列;接收魔王语言输入到数组demon[i];遍历数组将括号中元素进栈;检查魔王语言是否符合翻译语法；while(栈不为空){大写字母存放在临时栈temp中;遇到括号时临时栈temp添加标示“#”，小写字母全部入队列;}将临时栈temp中元素打进栈S中，遇到“#”时将key和队列元素依次打入栈中；输出栈元素即为翻译语句，输出同时将输出元素入队列用于中文翻译利用上述队列，在switch(){}中查询并输出中文；输出人类语言(数组demon[i]);}（2）魔王语言进栈模块CharInStack（demon[],&S）将魔王的语言自右至左进栈，总是处理栈顶元素。（3)入队列模块.此模块用于处理括号内的字符翻译，遇到“（”开始入队列，直至遇到“）”为止。然后将首字母出列记录于key中，用于以后入栈操作；（4)翻译大小写翻译中文处理模块使用switch(){Case:Case:Default:}（5）检验魔王语言是否符合翻译要求模块此模块用于检验，输入的demon[]是否为合法输入。比如，检查括号是否成对出现，字符是否为52个大小写字母之一……使用此结构实现字符与中文的转换翻译各模块之间调用关系:主函数模块{魔王语言进栈模块;检验魔王语言是否符合翻译要求模块{入队列模块;武汉理工大学《数据结构》课程设计说明书5}翻译大小写翻译中文处理模块}2.2.3流程图武汉理工大学《数据结构》课程设计说明书62.3测试用例设计为了充分验证程序的正确性，我选取下面四组测试数据进行测试：（ehnxgz）解释成:ezegexeneh若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“鹅追鹅赶鹅下鹅蛋鹅恨鹅”。B（ehnxgz）B解释成:tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。B()B解释成:tsaedsaetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅*天上一只鹅地上一只鹅”A（ehnxgz）B解释成:saeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。Tdsaezgxnh天地上一只鹅追赶蛋恨3调试报告1.函数调用比较多,因而得仔细对待数值和地址的传递，地址传递较快。2.由于粗心大意，时常漏掉分号，或者在中文输入法下输入了分号，导致不少的错误；3.函数数组遍历，进栈出栈。入队出队中都要牵扯指针的移动,所以要仔细考虑一循环的条件以及进栈元素的个数.4.程序中设计较多的函数实现，但是鉴于数据结构专注于算法的研究，没有将定义与实现放在不同的文件夹里面。这也方便了实验报告的撰写。4经验和体会算法具体设计情况如下：其中前面大部分算法是对栈和队列的定义和实现，包括栈的结构体的定义，入栈Push()和出栈Pop()函数的定义和实现，判断栈是否为空，清空栈。其次是对单链队列--------队列的链式存储结构相关操作。队列节点的定义，初始化队列函数InitStack()，入队函数EnQueue(),出队函数DeQueue()函数，判断是否为空栈函数QueueEmpty()的定义和实现。最后还有一个将魔王语言自右向左进栈的操作函数。其中大部分是对于栈和队列的一些基本操作。在编写程序的过程中，我也遇到了不少的问题。在魔王语言的算法编写的过程中，也遇到了一些麻烦，例如对于这些算法的综合以及各个算法之间的关系，另外还有一些小的问题：栈和队列的一些小小的联系，还有就是要注意一些在进行队列的指针的操作时，要注意指针的调用，同时开始时因为对于指针的一些用法及调用还有一些不太熟悉，因此有几个地方编写的时候遇到了无法执行的武汉理工大学《数据结构》课程设计说明书7局面，后来又对指针的运算进行了一些改进，才使得指针对于数据元素的调用才比较灵活。由于我们大一学的是C++对于printf()，scanf()这些函数的调用不太熟悉，这次编程前我还特地查阅了一下相关的用法。从这次编写算法的过程中，由于我们自己发现自己对于C语言中的指针的一些基本的描述和执行的操作不是很明白，因此自己还要继续加强对指针的学习，希望下次再遇到指针的问题时能够顺利的解决。认真细心多练习编程才是高效编写优质代码的关键，这也是我在这次课程设计中最大的收获。5附源程序清单和运行结果#includestdio.h#includestdlib.h#defineSTACK_INITSIZE50//栈的初始长度#defineSTACK_INCREASE10//栈空间存储不够时增长#defineMAX_Length100//demon[]数组的最大长度typedefstructStack//栈结构的定义{char*base;char*top;intsize;};voidInitStack(Stack&S)//初始化栈{S.base=(char*)malloc(STACK_INITSIZE*sizeof(char));S.top=S.base;S.size=STACK_INITSIZE;}voidPush(Stack&S,chare)//入栈函数{if(S.top-S.base=STACK_INITSIZE){S.base=(char*)realloc(S.base,(S.size+STACK_INCREASE)*sizeof(char));S.top=S.base+S.size;S.size+=STACK_INCREASE;}*(S.top)=e;S.top++;}voidPop(Stack&S,char&e)//出栈函数{--S.top;e=*S.top;}boolStackEmpty(Stacks)//判断是否为空栈{武汉理工大学《数据结构》课程设计说明书8if(s.top==s.base){returnt