魔王语言解释数据结构课程设计报告

魔王语言解释程序一、问题引入1.问题描述有一个魔王总是使用自已的一种非常精练而抽象的语言讲话，没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α→β1β2…βm（2）(θβ1β2…βm)→(θβm…β2θβ1θ)在这两种形式中，从左到右均表示解释。写一个魔王解释程序，将魔王的话解释成人能听懂的话。2.基本要求用下述两种规则和下述规则（2）实现。设大写字母表示魔王语言的词汇，小写字母表示人的词汇，希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。(1)B→tAdA(2)A→sae3.测试数据B(einxgz)B解释成tsaedsaeezegexeneietsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。tdsaezgxnh天地上一只鹅追赶下蛋恨4．实现提示将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列在处理后入栈。5.本程序采用的是顺序栈。基本操作列表：(1)据括号的个数设一个标记。记下括号的位置。(2)根据标记来执行依次的操作。(3)没有括号，直接进队，据翻译函数2输出人的语言。(4)有括号，分为括号内的和括号外的。，根据括号的位置：括号外的从右到左入栈；括号内的从左到右入栈，并且依次插入括号内的第一个字符。据翻译函数2出栈并且翻译。二、需求分析1.本演示程序中，魔王语言限制在小写字母‘a’-‘z’之间，且必须限制在括号内以及大写字母A和B。且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。2.魔王语言遵守如下规则：（θδ1δ2δ3…δn）θδnθδn-1…θδ1θBtAdAAsae3.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。4.程序的执行命令有：1）选择操作2）任意键结束5.数据测试B(ehnxgz)B解释成：tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。tdsaezgxnh天地上一只鹅追赶下蛋恨三、概要设计为实现上述功能，需要栈和队列两个抽象数据类型。1.栈抽象数据类型定义ADTstack{数据对象：D={ai|ai∈Elemset,i=1,2,3,…n,n=0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…n}基本操作：InitStack(&s)操作结果：构造一个空栈s。Push(&s,e)初始条件：栈s已存在。操作结果：插入元素e为新的栈顶元素。Pop(&s,&e)初始条件：栈s已存在且非空。操作结果：删除栈s的栈顶元素，并用e返回其值。StackLenth(&s)初始条件：栈s已存在。操作结果：返回s的元素个数，即栈的长度。ClearStack(&s)初始条件：栈s已存在。操作结果：将s清为空栈。DestoryStack(&s)初始条件：栈s已存在。操作结果：栈s被销毁。StackEmpty(&s)初始条件：栈s已存在。操作结果：若是为空栈，则返回TRUE,否则返回FALSE。Traverse(&s,void(*visit)())初始条件：栈s已存在。操作结果：依次遍历栈s中的元素，依次调用函数，一旦失败，则操作失败。}ADTstack2.队列抽象数据类型定义ADTQueue{数据对象：D={ai|ai∈Elemset,i=1,2,3,…n,n=0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…n}基本操作：InitQueue(&q)操作结果：构造一个空队列Q。EnQueue(&q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。QueueLenth(&q)初始条件：队列已存在。操作结果：返回Q的元素个数，即队列的长度。DeQueue(&q,&e)初始条件：队列已存在。操作结果：删除Q的队尾元素，并用e返回其值。QueueEmpty(&q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE.ClearQueue(&q)初始条件：队列Q已存在。操作结果：清空队列Q。DestoryQueue(&q)初始条件：队列Q已存在。操作结果：队列Q被销毁。不再存在。QueueTraverse(&q,Status(*visit)())初始条件：队列Q已存在。操作结果：依次遍历队列Q的元素，依次调用函数，一旦失败，则操作失败。}ADTQueue流程图如下:本程序主要包括以下几个模块：主程序模块：intmain(){GhostLanage();printf(\n\t按任意键退出\n\n);}各子程序模块：/*初始化栈*/voidInitStack(SeqStack*s){s-top=-1;}/*进栈操作*/voidPush(SeqStack*s,StackElementTypex){if(s-top==Stack_Size-1)printf(\n\t栈已满！);else{s-top++;s-elem[s-top]=x;}}/*出栈操作*/voidPop(SeqStack*s,StackElementType*x){if(s-top==-1)printf(\n\t栈为空！);else{*x=s-elem[s-top];s-top--;}}/*取栈顶元素*/voidGetTop(SeqStack*s,StackElementType*x){if(s-top==-1)printf(\n\t栈为空！);else*x=s-elem[s-top];}/*判断栈是否为空*/intIsEmpty(SeqStack*s){if(s-top==-1)return(0);elsereturn(1);}/*魔王语言翻译函数*/voidGhostLanage(){SeqStackB,A,s,B1,A1,r,M;StackElementTypech,ch1,ch2,x;charaa[100];intchoice,i=0,n;InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);printf(魔王语言的转换形式：B-tAdAA-sae);Push(&B,'t');Push(&B,'A');Push(&B,'d');Push(&B,'A');Push(&A,'s');Push(&A,'a');Push(&A,'e');printf(\n请输入要翻译的魔王语言:\n);scanf(%s,aa);for(i=0;aa[i]!='\0';i++)Push(&s,aa[i]);while(IsEmpty(&s)){Pop(&s,&ch);if(ch=='B'){B1=B;while(IsEmpty(&B1)){Pop(&B1,&ch1);if(ch1=='A'){A1=A;while(IsEmpty(&A1)){Pop(&A1,&ch2);Push(&r,ch2);}}elsePush(&r,ch1);}}elseif(ch=='A'){A1=A;while(IsEmpty(&A1)){Pop(&A1,&ch2);Push(&r,ch2);}}elseif(ch==')'){Pop(&s,&ch2);while(ch2!='('){Push(&M,ch2);Pop(&s,&ch2);}GetTop(&M,&ch2);x=ch2;Pop(&M,&ch2);while(IsEmpty(&M)){Push(&r,x);Pop(&M,&ch2);Push(&r,ch2);}Push(&r,x);}elsePush(&r,ch);}M=r;printf(\n\n\t翻译的结果为：);while(IsEmpty(&M)){Pop(&M,&ch);printf(%c,ch);}printf(\n\n\t是否继续翻译为汉语：（1-继续，0-不继续）);scanf(%d,&n);if(n==1){printf(\n\n\t翻译为汉语的结果为：\n\n\t);M=r;while(IsEmpty(&M)){Pop(&M,&ch);if(ch=='t')printf(天);elseif(ch=='d')printf(地);elseif(ch=='s')printf(上);elseif(ch=='a')printf(一只);elseif(ch=='e')printf(鹅);elseif(ch=='z')printf(追);elseif(ch=='g')printf(赶);elseif(ch=='x')printf(下);elseif(ch=='n')printf(蛋);elseif(ch=='h')printf(恨);}printf(\n);}else;}模块间的关系是：主程序翻译函数1翻译函数2栈模块四、详细设计本程序中的主要函数有：voidInitStack(SeqStack*s);/*初始化栈*/voidPush(SeqStack*s,StackElementTypex);/*进栈操作*/voidPop(SeqStack*s,StackElementType*x);/*出栈操作*/voidGetTop(SeqStack*s,StackElementType*x);/*取栈顶元素*/intIsEmpty(SeqStack*s);/*判断栈是否为空*/voidGhostLanage();/*魔王语言翻译函数*/函数间的调用关系：主程序调用魔王语言翻译函数，然后魔王语言翻译函数调用其它的函数（初始化栈，进栈，出栈，取栈顶元素，判断栈空），以此来实现整个程序的运行。//1.程序的头文件及全局变量的定义#includestdio.h#includestdlib.h#defineStackElementTypechar#defineStack_Size100//2.栈类型及其基本操作typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;voidInitStack(SeqStack*s);/*初始化栈*/voidPush(SeqStack*s,StackElementTypex);/*进栈操作*/voidPop(SeqStack*s,StackElementType*x);/*出栈操作*/voidGetTop(SeqStack*s,StackElementType*x);/*取栈顶元素*/intIsEmpty(SeqStack*s);/*判断栈是否为空*/voidGhostLanage();/*魔王语言翻译函数*///3.主函数intmain(){system(color1b);GhostLanage();printf(\n\t按任意键退出\n\n);}/*初始化栈*/voidInitStack(SeqStack*s){s-top=-1;}/*进栈操作*/voidPush(SeqStack*s,StackElementTypex){if(s-top==Stack_Size-1)printf(\n\t栈已满！);else{s-top++;s-elem[s-top]=x;}}/*出栈操作*/voidPop(SeqStack*s,StackElementType*x){if(s-top==-1)printf(\n\t栈为空！);else{*x=s-elem[s-top];s-top--;}}/*取栈顶元素*/voidGetTop(SeqStack*s,St