魔王語言解釋程序一、問題引入問題描述有一個(gè)魔王總是使用自已的一種格外精練而抽象的語言講話，沒有人能聽得懂。但他的語言是可以逐步解釋成人能懂的語言的逐步抽象上去的：〔1〕α→β1β2…βm〔2〕(θβ1β2…βm)→(θβm…β2θβ1θ)在這兩種形式中，從左到右均表示解釋。寫一個(gè)魔王解釋程序，將魔王的話解釋成人能聽懂的話。根本要求用下述兩種規(guī)章和下述規(guī)章〔2〕實(shí)現(xiàn)。設(shè)大寫字母表示魔王語言的詞匯，小寫字母表B→tAdAA→sae測試數(shù)據(jù)B(einxgz)B解釋成tsaedsaeezegexeneietsaedsaet天d地t天d地s上a一只e鵝z追g趕x下n蛋h恨實(shí)現(xiàn)提示將魔王的語言自右至左進(jìn)棧，總是處理?xiàng)ｍ斪址?。假設(shè)是開括號(hào)，則逐一出棧，將字母挨次入隊(duì)列，直至閉括號(hào)出棧，并按規(guī)章要求逐一出隊(duì)列在處理后入棧。本程序承受的是挨次棧。根本操作列表：(1)據(jù)括號(hào)的個(gè)數(shù)設(shè)一個(gè)標(biāo)記。登記括號(hào)的位置。(2)依據(jù)標(biāo)記來執(zhí)行依次的操作。2輸出人的語言。有括號(hào)，分為括號(hào)內(nèi)的和括號(hào)外的的從左到右入棧，并且依次插入括號(hào)內(nèi)的第一個(gè)字符。據(jù)翻譯函數(shù)2出棧并且翻譯。二、需求分析a’-‘z’寫字母A和B。且允許消滅重復(fù)字符或非法字符，程序運(yùn)用時(shí)自動(dòng)過濾去，輸出的運(yùn)算結(jié)果中將不含重復(fù)字符和非法字符。魔王語言遵守如下規(guī)章：〔θδ1δ2δ3…δn〕θδnθδn-1…θδ1θBtAdAAsae演示程序以用戶和計(jì)算機(jī)對(duì)話的形式進(jìn)展，即在計(jì)算機(jī)終端中顯示提示信息之后，有用戶自行選擇下一步命令，相應(yīng)輸入數(shù)據(jù)和運(yùn)算結(jié)果在其后顯示。程序的執(zhí)行命令有：1〕選擇操作 2〕任意鍵完畢數(shù)據(jù)測試B(ehnxgz)Btsaedsaeezegexenehetsaedsaet天d地st天d地s上a一只e鵝z追g趕x下n蛋h恨三、概要設(shè)計(jì)為實(shí)現(xiàn)上述功能，需要棧和隊(duì)列兩個(gè)抽象數(shù)據(jù)類型。棧抽象數(shù)據(jù)類型定義ADTstack{數(shù)據(jù)對(duì)象：D={ai|ai∈Elemset,i=1,2,3,…n,n>=0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…n}根本操作：InitStack(&s)操作結(jié)果：構(gòu)造一個(gè)空棧s。Push(&s,e)初始條件：棧s操作結(jié)果：插入元素e為的棧頂元素。Pop(&s,&e)初始條件：棧s已存在且非空。操作結(jié)果：刪除棧s的棧頂元素，并用eStackLenth(&s)初始條件：棧s操作結(jié)果：返回s的元素個(gè)數(shù)，即棧的長度。ClearStack(&s)初始條件：棧s已存在。操作結(jié)果：將sDestoryStack(&s)初始條件：棧s操作結(jié)果：棧sStackEmpty(&s)初始條件：棧s操作結(jié)果：假設(shè)是為空棧，則返回TRUE,否則返回FALSE。Traverse(&s,void(*visit))初始條件：棧s操作結(jié)果：依次遍歷棧s中的元素，依次調(diào)用函數(shù)，一旦失敗，則操作失敗。}ADTstack隊(duì)列抽象數(shù)據(jù)類型定義ADTQueue{數(shù)據(jù)對(duì)象：D={ai|ai∈Elemset,i=1,2,3,…n,n>=0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…n}根本操作：InitQueue(&q)操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。EnQueue(&q,e)初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e為QQueueLenth(&q)初始條件：隊(duì)列已存在。操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長度。DeQueue(&q,&e)初始條件：隊(duì)列已存在。操作結(jié)果：刪除Q的隊(duì)尾元素，并用eQueueEmpty(&q)初始條件：隊(duì)列Q已存在。操作結(jié)果：假設(shè)Q為空隊(duì)列，則返回TRUE，否則返回FALSE.ClearQueue(&q)初始條件：隊(duì)列Q操作結(jié)果：清空隊(duì)列Q。DestoryQueue(&q)初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀。不再存在。QueueTraverse(&q,Status(*visit))初始條件：隊(duì)列Q操作結(jié)果：依次遍歷隊(duì)列Q的元素，依次調(diào)用函數(shù)，一旦失敗，則操作失敗。}ADTQueue流程圖如下:本程序主要包括以下幾個(gè)模塊：主程序模塊：intmain{GhostLanage;printf(“\n\t\n\n“);}各子程序模塊：/*初始化棧*/voidInitStack(SeqStack*s){s->top=-1;}/*進(jìn)棧操作*/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);}/*魔王語言翻譯函數(shù)*/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(“魔王語言的轉(zhuǎn)換形式：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是否連續(xù)翻譯為漢語〔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;}模塊間的關(guān)系是：主程序主程序棧模塊翻譯函數(shù)12四、具體設(shè)計(jì)本程序中的主要函數(shù)有：voidInitStack(SeqStack*s);/*初始化棧*/voidPush(SeqStack*s,StackElementTypex);/*進(jìn)棧操作*/voidPop(SeqStack*s,StackElementType*x);/*出棧操作*/voidGetTop(SeqStack*s,StackElementType*x);/*取棧頂元素*/intIsEmpty(SeqStack*s);/*推斷棧是否為空*/voidGhostLanage;/*魔王語言翻譯函數(shù)*/〔初始化棧，進(jìn)棧，出棧，取棧頂元素，推斷棧空，以此來實(shí)現(xiàn)整個(gè)程序的運(yùn)行。//1.程序的頭文件及全局變量的定義#include<stdio.h>#include<stdlib.h>#defineStackElementTypechar#defineStack_Size100//2.棧類型及其根本操作typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;voidInitStack(SeqStack*s);/*初始化棧*/voidPush(SeqStack*s,StackElementTypex);/*進(jìn)棧操作*/voidPop(SeqStack*s,StackElementType*x);/*出棧操作*/voidGetTop(SeqStack*s,StackElementType*x);/*取棧頂元素*/intIsEmpty(SeqStack*s);/*推斷棧是否為空*/voidGhostLanage;/*魔王語言翻譯函數(shù)*///3.主函數(shù)intmain{system(“color1b“);GhostLanage;printf(“\n\t\n\n“);}/*初始化棧*/voidInitStack(SeqStack*s){s->top=-1;}/*進(jìn)棧操作*/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.魔王語言翻譯函數(shù)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是否連續(xù)翻譯為漢語〔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;}五、調(diào)試分析結(jié)果。所以進(jìn)展調(diào)試，覺察應(yīng)當(dāng)從右到左入棧，依據(jù)出棧的挨次，先進(jìn)后出，正好可以到達(dá)相應(yīng)的結(jié)果。11，結(jié)果未相反。與規(guī)章11不會(huì)重復(fù)第一個(gè)字符的輸出。以，經(jīng)過調(diào)試，也生疏了這兩個(gè)符號(hào)的用法。六、用戶手冊(cè)第一步：啟動(dòng)魔王語言.exe應(yīng)用程序，進(jìn)入程序界面，如下：其次步：輸入要翻譯的魔王語言后按Enter鍵確認(rèn)，結(jié)果如下：第三步：程序?qū)⑤斎敕g為魔王語言后會(huì)再次詢問要不要翻譯為漢語，假設(shè)要翻譯為漢語，1，按Enter第四步：翻譯完畢后按任意鍵退出程序。七、測試結(jié)果輸入的魔王語言為：B(ehnxgz)B翻譯的結(jié)果為：tsaedsaeezegexenehetsaedsae翻譯為漢語的結(jié)果為：天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝結(jié)論：此程序能夠依據(jù)給定的翻譯規(guī)章解釋魔王語言。八、完畢語通過這個(gè)試驗(yàn)。特別是試驗(yàn)中對(duì)棧的應(yīng)用，讓我更深入的了解了棧的特性，更加了解了缺乏，期望在今后的學(xué)習(xí)中，不斷努力，使程序更加的完善。九、附錄程序源代碼如下：#include<stdio.h>#include<stdlib.h>#defineStackElementTypechar#defineStack_Size100typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;voidInitStack(SeqStack*s);/*初始化棧*/voidPush(SeqStack*s,StackElementTypex);/*進(jìn)棧操作*/voidPop(SeqStack*s,StackElementType*x);/*出棧操作*/voidGetTop(SeqStack*s,StackElementType*x);/*取棧頂元素*/intIsEmpty(SeqStack*s);/*推斷棧是否為空*/voidGhostLanage;/*魔王語言翻譯函數(shù)*//*主函數(shù)*/intmain{system(“color1b“);GhostLanage;printf(“\n\t\n\n“);}/*初始化棧*/voidInitStack(SeqStack*s){s->top=-1;}/*進(jìn)棧操作*/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);}/*魔王語言翻譯函數(shù)*/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