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

魔王语言解释程序一、问题引入问题描述有一个魔王总是使用自已的一种格外精练而抽象的语言讲话，没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的逐步抽象上去的：〔1〕α→β1β2…βm〔2〕(θβ1β2…βm)→(θβm…β2θβ1θ)在这两种形式中，从左到右均表示解释。写一个魔王解释程序，将魔王的话解释成人能听懂的话。根本要求用下述两种规章和下述规章〔2〕实现。设大写字母表示魔王语言的词汇，小写字母表B→tAdAA→sae测试数据B(einxgz)B解释成tsaedsaeezegexeneietsaedsaet天d地t天d地s上a一只e鹅z追g赶x下n蛋h恨实现提示将魔王的语言自右至左进栈，总是处理栈顶字符。假设是开括号，则逐一出栈，将字母挨次入队列，直至闭括号出栈，并按规章要求逐一出队列在处理后入栈。本程序承受的是挨次栈。根本操作列表：(1)据括号的个数设一个标记。登记括号的位置。(2)依据标记来执行依次的操作。2输出人的语言。有括号，分为括号内的和括号外的的从左到右入栈，并且依次插入括号内的第一个字符。据翻译函数2出栈并且翻译。二、需求分析a’-‘z’写字母A和B。且允许消灭重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。魔王语言遵守如下规章：〔θδ1δ2δ3…δn〕θδnθδn-1…θδ1θBtAdAAsae演示程序以用户和计算机对话的形式进展，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。程序的执行命令有：1〕选择操作 2〕任意键完毕数据测试B(ehnxgz)Btsaedsaeezegexenehetsaedsaet天d地st天d地s上a一只e鹅z追g赶x下n蛋h恨三、概要设计为实现上述功能，需要栈和队列两个抽象数据类型。栈抽象数据类型定义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的栈顶元素，并用eStackLenth(&s)初始条件：栈s操作结果：返回s的元素个数，即栈的长度。ClearStack(&s)初始条件：栈s已存在。操作结果：将sDestoryStack(&s)初始条件：栈s操作结果：栈sStackEmpty(&s)初始条件：栈s操作结果：假设是为空栈，则返回TRUE,否则返回FALSE。Traverse(&s,void(*visit))初始条件：栈s操作结果：依次遍历栈s中的元素，依次调用函数，一旦失败，则操作失败。}ADTstack队列抽象数据类型定义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为QQueueLenth(&q)初始条件：队列已存在。操作结果：返回Q的元素个数，即队列的长度。DeQueue(&q,&e)初始条件：队列已存在。操作结果：删除Q的队尾元素，并用eQueueEmpty(&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\telse{s->top++;s->elem[s->top]=x;}}/*出栈操作*/voidPop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse{*x=s->elem[s->top];s->top--;}}/*取栈顶元素*/voidGetTop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse*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->tAdA A->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\twhile(IsEmpty(&M)){Pop(&M,&ch);printf(“%c“,ch);}printf(“\n\n\t是否连续翻译为汉语〔10scanf(“%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;}模块间的关系是：主程序主程序栈模块翻译函数12四、具体设计本程序中的主要函数有：voidInitStack(SeqStack*s);/*初始化栈*/voidPush(SeqStack*s,StackElementTypex);/*进栈操作*/voidPop(SeqStack*s,StackElementType*x);/*出栈操作*/voidGetTop(SeqStack*s,StackElementType*x);/*取栈顶元素*/intIsEmpty(SeqStack*s);/*推断栈是否为空*/voidGhostLanage;/*魔王语言翻译函数*/〔初始化栈，进栈，出栈，取栈顶元素，推断栈空，以此来实现整个程序的运行。//1.程序的头文件及全局变量的定义#include<stdio.h>#include<stdlib.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\telse{s->top++;s->elem[s->top]=x;}}/*出栈操作*/voidPop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse{*x=s->elem[s->top];s->top--;}}/*取栈顶元素*/voidGetTop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse*x=s->elem[s->top];}/*推断栈是否为空*/intIsEmpty(SeqStack*s){if(s->top==-1)return(0);elsereturn(1);}//4.魔王语言翻译函数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(“\t\t*************魔王语言翻译程序***************\n“);printf(“\t\t*********\t\t\t************\t\n“);printf(“\t\t*********\t\t\t************\t\n“);printf(“\t\t*********\t\t\t************\t\n“);Push(&B,”t”);Push(&B,”A”);Push(&B,”d”);Push(&B,”A”);Push(&A,”s”);Push(&A,”a”);Push(&A,”e”);printf(“\n\t\t\tscanf(“%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);}M=r;

}elsePush(&r,ch);printf(“\n\n\twhile(IsEmpty(&M)){Pop(&M,&ch);printf(“%c“,ch);}printf(“\n\n\t是否连续翻译为汉语〔10scanf(“%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;}五、调试分析结果。所以进展调试，觉察应当从右到左入栈，依据出栈的挨次，先进后出，正好可以到达相应的结果。11，结果未相反。与规章11不会重复第一个字符的输出。以，经过调试，也生疏了这两个符号的用法。六、用户手册第一步：启动魔王语言.exe应用程序，进入程序界面，如下：其次步：输入要翻译的魔王语言后按Enter键确认，结果如下：第三步：程序将输入翻译为魔王语言后会再次询问要不要翻译为汉语，假设要翻译为汉语，1，按Enter第四步：翻译完毕后按任意键退出程序。七、测试结果输入的魔王语言为：B(ehnxgz)B翻译的结果为：tsaedsaeezegexenehetsaedsae翻译为汉语的结果为：天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅结论：此程序能够依据给定的翻译规章解释魔王语言。八、完毕语通过这个试验。特别是试验中对栈的应用，让我更深入的了解了栈的特性，更加了解了缺乏，期望在今后的学习中，不断努力，使程序更加的完善。九、附录程序源代码如下：#include<stdio.h>#include<stdlib.h>#defineStackElementTypechar#defineStack_Size100typedefstruct{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;/*魔王语言翻译函数*//*主函数*/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\telse{s->top++;s->elem[s->top]=x;}}/*出栈操作*/voidPop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse{*x=s->elem[s->top];s->top--;}}/*取栈顶元素*/voidGetTop(SeqStack*s,StackElementType*x){if(s->top==-1)printf(“\n\telse*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(“\t\t*************魔王语言解释程序***************\n“);printf(“\t\t*********\t\t************\t\n“);printf(“\t\t*********\t\t********\t\n“);printf(“\t\t*********\t\t**************\t\n“);Push(&B,”t”);Push(&B,”A”);Push(&B,”d”);Push(&B,”A”);Push(&A,”s”);Push(&A,”a”);Push(&A,”e”);printf(“\n\t\tscanf(“%s“,aa);for(i=0;aa[i]!=”\0”;i++)Push(&s,aa[i]);whil