魔王语言 数据结构试验报告

题目：魔王语言解释[问题描述]有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α->β1β2……βm（2）（θδ1δ2……δn）—>θδnθδn-1……θδ1θ在这两种形式中，从左到右均表示解释。

试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话；[基本要求]用下述两条具体规则和上述规则形式（2）实现。

设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。

魔王语言可含人的词汇。

（1）B->tAdA（2）A->sae[测试数据]B（ehnxgz）B解释成tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。

[实现提示]将魔王的语言自右至左进栈，总是处理栈顶字符。

若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。

其他情形较简单，请读者思考应如何处理。

应首先实现栈和队列的基本操作。

[源代码]#include<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 100#define STACK_INCREMENT 10struct Stack{char* base;char* top;int stacksize;};void InitStack(struct Stack &s){//构造栈s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));s.top=s.base;s.stacksize=STACK_INIT_SIZE;}void Push(struct Stack &s,char e){//压入元素if(s.top-s.base>=STACK_INIT_SIZE){s.base=(char*)realloc(s.base,(s.stacksize+STACK_INCREMENT)*sizeof(char));s.top=s.base+s.stacksize;s.stacksize+=STACK_INCREMENT;}*(s.top)=e;s.top++;}void Pop(struct Stack &s,char &e){//取出元素e=*--s.top;}int StackEmpty(struct Stack s){//栈是否为空if(s.top==s.base){return 1;}else{return 0;}}void ClearStack(struct Stack &s){s.top=s.base;}struct Queue{char data;struct Queue* next;};struct LinkQueue{struct Queue* front;struct Queue* rear;};void InitQueue(struct LinkQueue &q){//构造队q.front=q.rear=(struct Queue*)malloc(sizeof(struct Queue));q.front->next=NULL;}void EnQueue(struct LinkQueue &q,char e){//元素入队struct Queue* p;p=(struct Queue*)malloc(sizeof(struct Queue));p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;}void DeQueue(struct LinkQueue &q,char &e){//元素出队struct Queue* p;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear==p){q.rear=q.front;}free(p);}int QueueEmpty(struct LinkQueue q){//队是否为空if(q.front==q.rear){return 1;}else{return 0;}}void InStack(char* ch,struct Stack &s){//把字符数组从右至左压入栈中int i,L=0;while(ch[L]!='\0'){L++;}for(i=L-1;i>=0;i--){Push(s,ch[i]);}}int main(){int i=0;char A[]="sae";char B[]="tsaedsae";char flag='0';//flag用来标记处理括号int mark=1;int f=0;struct Stack S;struct Stack temp;//用来处理括号外的元素InitStack(S);InitStack(temp);struct LinkQueue Q;InitQueue(Q);char MoWang[100]="\0";char e1,key,e2,e;printf("************************************************************** \n");printf("* * 欢迎光临广东工业大学**\n");printf("* **************************** *\n");printf("* * 魔王语言解释系统* *\n");printf("* **************************** *\n");printf("* 班级:计算机学院网络工程2007级4班*\n");printf("* 姓名: 黄文龙学号: 3107007087 *\n");printf("************************************************************** \n\n");printf("请输入你想要解释的魔王语言（最多含有一个括号）：\n");gets(MoWang);InStack(MoWang,S);//把要解释的魔王语言压入栈中while(!StackEmpty(S)){Pop(S,e1);if(e1=='('){if(StackEmpty(S)){printf("魔王语言错误!\n");mark=0;break;}while(!StackEmpty(S)){Pop(S,e1);if(e1==')'){f=1;break;}else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z')){ printf("魔王语言错误！\n");mark=0;break;}}if(mark==0){break;}if(f!=1){printf("魔王语言错误！\n");break;}}else if(e1==')'){printf("魔王语言错误！\n");mark=0;break;}else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z')){printf("魔王语言错误！\n");mark=0;break;}}if(mark==1&&f==1){ClearStack(S);InStack(MoWang,S);while(!StackEmpty(S)){//栈不空时Pop(S,e1);if(e1=='B'){Push(temp,e1);}else if(e1=='A'){Push(temp,e1);}else if(e1=='('){//用队存储括号中的元素Push(temp,flag);//有括号的话就用flag标记Pop(S,e1);while(e1!=')'){EnQueue(Q,e1);Pop(S,e1);}if(!QueueEmpty(Q)){DeQueue(Q,key);}}else{Push(temp,e1);f=0;}}while(!StackEmpty(temp)){//边处理边进栈Pop(temp,e1);if(e1!=flag){//把括号外的元素压入中Push(S,e1);}else{while(!QueueEmpty(Q)){//处理括号中的元素进栈DeQueue(Q,e2);Push(S,key);Push(S,e2);}if(f!=0){//最后还要压一个keyPush(S,key);}}}printf("解释后的语言为：\n");while(!StackEmpty(S)){//依次出栈输出处理后的元素Pop(S,e);EnQueue(Q,e);//元素进队是为了输出对应汉字if(e=='B'){printf("%s",B);}else if(e=='A'){printf("%s",A);}else{printf("%c",e);}}printf("\n");while(!QueueEmpty(Q)){//输出对应汉字DeQueue(Q,e);switch(e){case 't': printf("天");break;case 'd' : printf("地"); break;case 's' : printf("上"); break;case 'a' : printf("一只"); break;case 'e' : printf("鹅"); break;case 'z' : printf("追"); break;case 'g' : printf("赶"); break;case 'x' : printf("下"); break;case 'n' : printf("蛋"); break;case 'h' : printf("恨"); break;case 'B' : printf("天上一只鹅地上一只鹅");break;case 'A' : printf("上一只鹅");break;default : printf("*");break;}}printf("\n");}system("pause");return 0;}[读者手册]1、本程序的运行环境为dos操作系统，执行文件为“魔王解释语言.exe”。

数据结构与算法实验报告姓名院系学号任课教师指导教师实验地点软件学院实验时间2011年10月29 日实验名称数据结构实验一栈和队列同组人无预习报告(对实验主要内容的认识) 得分实验内容（问题，思路，程序，结果）得分1.题目：魔王语言2.问题描述：有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听得懂,但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的；α→β1β2…βm(θδ1δ2…δn)→δnθδn-1θ…δ2θδ1在这两种形式中，从左到右均表示解释。

试写一个魔王语言的解释系统，把他的话解释成人能听得懂得话。

3.算法思想描述（1）算法的思想①我将设置三个堆栈和两个队列处理这个问题，首先将魔王语言自右向左压入堆栈*2(一个用来测试S_3另一个用来操作S_1)，然后判断此句话中是否有括号，若无则直接将操作堆栈弹出到队列中然后输出；②若有括号则先弹出操作堆栈S_1到队列Q_1中,遇到"("时跳过这个括号然后将括号后面的第一个字母标记（记作A ），将除第一个字母外的其他字母弹出到队列Q_2中，直到遇到")"为止，将“）”弹出；③将Q_2的元素每后面一个加原来的第一个元素A 压入堆栈S_2;④将堆栈S_2的元素弹出到Q_1中，然后将S_1中剩余的元素弹出到Q_!; ⑤按照对应的字母翻译即可。

（2）算法流程图开始 是否有括号 直接将堆栈中的弹出入队列翻译输出 将魔王语言自右向左压入堆栈S_1 NO YES 将堆栈S_1中的元素弹出到Q_1 弹出元素为"(" YES NO 弹出（后第一个元素记为A 将剩余元素弹入队列Q_2中 NO弹出元素为）YES将Q_2元素每个加A压入栈S_2将S_2中的元素弹出到Q_1中将S_1中剩余元素弹出到Q_1中翻译后输出结果结束4.数据结构描述（描述解决问题用到的数据结构）（1）所用数据结构的描述S_1堆栈负责自右向左存放魔王语言S_2堆栈存放处理过的括号里的语言S_3堆栈负责判断是否有括号Q_1队列存放处理后的语言Q_2队列负责存放括号中的语言（2）函数功能说明及函数的实现源代码①堆栈实现#ifndef STACK_H_INCLUDED#define STACK_H_INCLUDED#include<stdio.h>#include<math.h>#include<stdlib.h>#include<string.h>#define MAXSIZE 100#define STACK_INIT_MAX 100#define STACKINCREMENT 10#define ERROR 0#define OK 1#define FALSE 0#define TRUE 1typedef int Status;typedef struct{ //顺序栈类型定义char *top;char *base;int stacksize;}SqStack;Status InitStack(SqStack &s){ //构造一个空栈ss.base=(char *)malloc(STACK_INIT_MAX*sizeof(char)); if(!s.base) exit(OVERFLOW); //存储分配失败s.top = s.base;s.stacksize = STACK_INIT_MAX;return OK;}Status Pop(SqStack &s,char &e){ //删除s的栈顶元素，并以e返回其值if(s.top == s.base) return FALSE;s.top--;e = *(s.top);return TRUE;}Status Push(SqStack &s,char e){ //在栈s的栈顶插入新的栈顶元素e if((s.top-s.base) >= s.stacksize){s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT) * sizeof(char));if(!s.base) exit(OVERFLOW); //存储分配失败s.top = s.base + s.stacksize;s.stacksize += STACKINCREMENT;}*s.top = e;s.top++;return OK;}Status DestroyStack(SqStack &s){ //销毁栈sfree(s.base);s.stacksize = 0;return OK;}void InStack(char* ch,SqStack &s){//把字符数组从右至左压入栈中int i,L=0;while(ch[L]!='\0'){L++;}for(i=L-1;i>=0;i--){Push(s,ch[i]);}}Status StackEmpty(SqStack s){//栈是否为空if(s.top==s.base){return 1;}else{return 0;}}#endif // STACK_H_INCLUDED②队列实现#ifndef QUEUE_H_INCLUDED #define QUEUE_H_INCLUDED #include<stdio.h>#include<math.h>#include<stdlib.h>#include<string.h>#define MAXSIZE 100#define ERROR 0#define OK 1#define FALSE 0#define TRUE 1typedef struct{ //循环队列类型定义char *base;int front;int rear;}SqQueue;Status InitQueue(SqQueue &q){ //构造一个空队列qq.base = (char *)malloc(MAXSIZE*sizeof(char));if(!q.base) exit(OVERFLOW); //存储分配失败q.front = q.rear = 0;return OK;}Status EnQueue(SqQueue &q,char e){ //插入元素e为q的新的队尾元素if((q.rear+1) % MAXSIZE == q.front) return ERROR;q.base[q.rear] = e;q.rear = (q.rear + 1) % MAXSIZE;return OK;}Status DeQueue(SqQueue &q,char &e){ //若队列不空，则删除q的对头元素，用e返回其值，//并返回OK；否则返回ERRORif(q.front == q.rear) return ERROR;e = q.base[q.front];q.front = (q.front + 1) % MAXSIZE;return OK;}Status DestroyQueue(SqQueue &q){ //销毁队列q，q不再存在free(q.base);return OK;}#endif // QUEUE_H_INCLUDED③main函数实现#include <iostream>#include"Stack.h"#include"Queue.h"int main(){int length,i,mark; //length表示魔王语言的长度，mark为"("数mark=0;char e,str,j; //e为插入值或删除值，str为重复打印的字符，j为检测符char MoWang[100];//用来储存魔王的语言SqStack S_1;SqStack S_2;SqStack S_3;//检测栈InitStack(S_1);//初始化堆栈InitStack(S_2);InitStack(S_3);SqQueue Q_1;SqQueue Q_2;InitQueue(Q_1);//初始化队列InitQueue(Q_2);printf("请输入魔王的语言:\n");scanf("%s",&MoWang);//将魔王语言存入数组中length=strlen(MoWang);//魔王语言的长度包括括号i=0;InStack(MoWang,S_1);//将魔王语言自右向左入栈InStack(MoWang,S_3);//检测魔王语言while(!StackEmpty(S_3)){Pop(S_3,j);if(j=='('){mark=1;}}if(mark==1){while(e!=')'){//处理")"之前的元素Pop(S_1,e);if(e=='('){Pop(S_1,str);//记录需要重复打印的字符while(e!=')'){Pop(S_1,e);EnQueue(Q_2,e);//将括号内的元素入队列i++;}break;}EnQueue(Q_1,e);//将"("外的元素存入第一个队列中}for(;i>2;i--)//将括号内除了第一个和最后一个元素，其他元素连同第一个元素分次入栈{DeQueue(Q_2,e);//将队列中的第一个元素弹出存入ePush(S_2,e);//将e压入s_2中Push(S_2,str);//将str压入s_2中}DeQueue(Q_2,e);//将括号中的最后一个元素弹出存入ePush(S_2,e);//将e压入s_2中//将s_2堆栈中的元素弹出到队列Q_1中while(!StackEmpty(S_2)){Pop(S_2,e);EnQueue(Q_1,e);}while(!StackEmpty(S_1))//将魔王语言")"后的读入到Q_1中{Pop(S_1,e);EnQueue(Q_1,e);}}else{//若无括号直接输入while(!StackEmpty(S_1)){Pop(S_1,e);EnQueue(Q_1,e);}}while(Q_1.front!=Q_1.rear){DeQueue(Q_1,e); //删除队首元素switch(e) //判断并打印翻译后的语言{case 't': printf("天");break;case 'd': printf("地");break;case 's': printf("上");break;case 'a': printf("一只");break;case 'w': printf(",");break;case 'e': printf("鹅");break;case 'z': printf("追");break;case 'g': printf("赶");break;case 'x': printf("下");break;case 'n': printf("蛋");break;case 'i': printf("恨");break;case 'A': printf("上一只鹅");break;case 'B': printf("天上一只鹅地上一只鹅");break;default: printf("error!!!");}}printf("\n"); //换行DestroyQueue(Q_1);DestroyQueue(Q_2); //释放队列qDestroyStack(S_1); //释放栈s DestroyStack(S_2);return 0;}5.测试结果翻译成功结果如下图：实验结论得分成功利用堆栈和数组完成魔王语言的翻译教师评价总分实际得分。

课程实验报告实习报告一：需求分析(1)以一维数组demon[ i ]表示魔王语言．(2)魔王语言由用户输入,初始保存在demon[ i ]中．(3)魔王语言与人类语言对应关系固化在程序中．(4)实现过程：A：初始，魔王语言接收后存放在demon[ i ]中．B：初次遍历数组，将数组中括号内的元素入栈，同时插入相应首字母；C：再次遍历数组，将数组元素依次入队。

（小写字母直接入队；大写字母经翻译成相应字符后入队；遇到括号，将栈中保存的元素依次出栈入队）在翻译过程中，如果依旧包含大写字母，则置flag为1，否则为0。

D：将队列中元素赋值给demon[ i ]。

如果此时flag=1，则再次重复C过程。

直至所有元素为人类语言。

E：输出demon[ i ]。

此时数组中元素为对应的人类语言。

注：如果程序中没有相应的对应关系，则翻译成“???”。

二：概要设计：1：设定栈的抽象数据类型定义：ADT stack｛数据对象：D＝｛ai|ai∈CharSet,i＝1,2,…,n,n>=0｝数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i＝2,…,n}基本操作：initstack (＆s)操作结果:构造一个空栈s.push (＆s,e)初始条件:栈s已存在.操作结果:在栈s的栈顶插入新的栈顶元素e.pop(＆s,＆e)初始条件:栈s已存在.操作结果:删除s的栈顶元素,并以e返回其值.}ADT stack2:设定队列的抽象数据类型:ADT queue{数据对象：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返回其值. }ADT queue3:本程序包含四个模块:1)主函数模块.其中主函数为:status main(){初始化栈;初始化队列;接收魔王语言输入到数组demon[i ];遍历数组将括号中元素进栈;while(数组demon[i ]中元素有大写字母){ 翻译排序处理后入队列;将对列元素保存在数组demon[i ];}输出人类语言(数组demon[ i]);}2)括号内元素入栈处理模块.tempstack(&temps)将括号内元素入栈,依次插入首字符.举例：(abcd)－>adacaba.3)排序入队列模块.sort(&s,&q){遍历数组;{遇到小写字母,直接入队列;遇到大写字母,翻译大写后入队列;遇到括号,将栈中保存的元素依次出栈入队列;}}4)翻译大写处理模块.spenqueue(&*q,key){switch(key){找到各个大写字母对应的字符串. 没有相应的则解释为’???’}}各模块之间调用关系:主函数模块{括号内元素入栈处理模块;排序入队模块{翻译大写处理模块;}}三:详细设计1.定义全局变量#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW -2#define MAXSIZE 100#define stack_init_size 100#define stackincrement 10typedef char selemtype;typedef char qelemtype;typedef char elemtype;typedef int status;char e;char demon[MAXSIZE];2.栈类型及其基本操作typedef struct{selemtype *base;selemtype *top;int stacksize;}sqstack;status initstack (sqstack *s){s->base=(selemtype *)malloc(stack_init_size*sizeof(selemtype));if(!s->base) exit (OVERFLOW);s->top=s->base;s->stacksize=stack_init_size;return OK;}/*创建栈*/status push (sqstack *s,selemtype e){if(s->top-s->base>=s->stacksize){s->base=(elemtype *) realloc(s->base,(s->stacksize+stackincrement)*sizeof(elemtype)); if(!s->base) exit(OVERFLOW);s->top=s->base+s->stacksize;s->stacksize+=stackincrement;}*(s->top++)=e;return OK;}/*入栈*/status pop(sqstack *s,selemtype *e){if(s->top==s->base) return ERROR;*e=*(--(s->top));return OK;}/*出栈*/3.队列类型及其基本操作typedef struct qnode{qelemtype data;struct qnode *next;}qnode,*queueptr;typedef struct{queueptr front;queueptr rear;}linkqueue;status initqueue(linkqueue *q){q->front=q->rear=(queueptr)malloc(sizeof(qnode));if(!q->front) exit(OVERFLOW);q->front->next=NULL;return OK;}/*创建队列*/status enqueue(linkqueue *q,qelemtype e){queueptr p;p=(queueptr)malloc(sizeof(qnode));if(!p) exit(OVERFLOW);p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;return OK;}/*入队*/status dequeue(linkqueue *q,qelemtype *e){queueptr p;if(q->front==q->rear) return ERROR;p=q->front->next;*e=p->data;q->front->next=p->next;if(q->rear==p){q->rear=q->front;}free(p);return OK;}/*出队*/4.括号内元素入栈处理函数void tempstack(sqstack *temps){int i=0;char t;char c;c=demon[i ];for(i=0;c!='#';i++)/*遍历数组*/{c=demon[i ];if(c=='(')/*遇到开括号*/{t=demon[i+1];/*取括号中的首字母*/push(temps,t);/*入栈*/i++;/*指向首字母*/do{i++;c=demon[i ];push(temps,c)/*第一次循环将次字母入栈*/; push(temps,t);/*再将首字母进栈*/}while(c!=')');/*直到括号中元素全部进栈*/pop(temps,&t);/*将多余进栈的首字母t出栈*/pop(temps,&t); /*将多余进栈的’)’出栈*/ } } }/*临时栈*/5.特殊入队函数void spenqueue(linkqueue *q,char key){int j=0;char a[5];switch(key) /*判断大写字母对应的字符串*/{case'A':strcpy(a,"sae");break;case'B':strcpy(a,"tAdA");break;case'C':strcpy(a,"abc");break;case'D':strcpy(a,"def");break;case'E':strcpy(a,"ghi");break;case'F':strcpy(a,"klm");break;case'H':strcpy(a,"mop");break;default:strcpy(a,"???"); /*不能翻译的魔王语言以”???”输出*/}while(a[j]!='\0') /*如果数组还有字母*/{enqueue(q,a[j]);/*进队*/j++;}}/*特殊入队*/6.排序入队处理函数status sort(sqstack *s,linkqueue *q){ qnode b;int flag=0;/*大写字母监视哨置零*/int i;for(i=0;demon[ i]!='#';i++)/*遍历数组*/{b.data=demon[ i];if( ('a'<=b.data&&b.data<='z') || b.data=='?') /*如果是小写字母或者’?’则直接入队*/ { enqueue(q,b.data);}else{ if('A'<=b.data&&b.data<='Z') /*如果是大写字母,则调用特殊入队函数,*/{ spenqueue(q,b.data);flag=1; /*发现大写字母监视哨置1*/}else{ if(b.data=='(')/*如果是括号*/{ do{ pop(s,&e);enqueue(q,e);}while(!(s->top==s->base)); /*只要栈不为空,则出栈进队*/while (b.data!=')') /*只要还指向括号内元素,就继续往后移,保证原括号内的元素不再进栈*/{ i++;b.data=demon[ i]; }}}}}return flag;}/*排序*/status main(){ sqstack s1;linkqueue q1;int k=0;int flag=1;clrscr();printf("\n\n\n\t\t\tWELCOME!\n");printf("\t***************************************\n");printf("\tPlease Input The Demon's Words:\n\t");printf("!: Less Than 30 Letters: )\n\t");printf("!: Please Stop By '#': )\n\t");printf("***************************************\n\t");printf("The Demon's Words:\n\t");scanf("%s",demon);printf("\n\t***************************************");initstack(&s1); /*创建栈*/initqueue(&q1); /*创建队*/tempstack(&s1); /*调用函数*/while (flag==1) /*如果有大写字母*/{ k=0;flag=sort(&s1,&q1);while(q1.front!=q1.rear) /*重写demon[i ]*/{dequeue(&q1,&e);demon[k]=e;k++;}demon[k]='#';}demon[k]='\0';printf("\n\tThe Human's Words:\n\t%s",demon);printf("\n\n\t***************************************");printf("\n\t\t\tTHANK YOU!\n\t");printf("Please press any key to exit...");if(getch()) exit(1);}}/*主函数*/四:调试分析1. 函数调用比较多,因而得仔细对待数值和地址的传递.2. 由于魔王语言中’B’中仍然包含着大写字母(tAdA).所以考虑设置flag.3. 函数数组遍历.进栈出栈.入队出队中都要牵扯指针的移动,所以要仔细考虑一循环的条件以及进栈元素的个数.五:用户手册1. 本程序运行环境为DOS/WINDOWS操作系统,执行文件为:魔王语言解释.exe。

数据结构实验报告（魔王语言）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）魔王语言的解释规则：大写字母表示魔王语言的词汇，小写字母表示人的词汇语言,魔王语言中可以包含括号，魔王语言的产生式规则在程序中给定，当接收用户输入的合法的魔王语言时，通过调用魔王语言翻译函数来实现翻译。

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）抽象数据类型：typedef struct{StackElementType elem[Stack_Size];int top;}SeqStack;主程序模块：int main(){GhostLanage();printf("\n\t按任意键退出\n\n");}各子程序模块：/*初始化栈*/void InitStack(SeqStack *s){s->top=-1;}/*进栈操作*/void Push(SeqStack *s,StackElementType x){if(s->top==Stack_Size-1)printf("\n\t栈已满！ ");else {s->top++;s->elem[s->top]=x;}}/*出栈操作*/void Pop(SeqStack *s,StackElementType *x){if(s->top==-1)printf("\n\t栈为空！ ");else {*x=s->elem[s->top];s->top--;}}/*取栈顶元素*/void GetTop(SeqStack *s,StackElementType *x){if(s->top==-1)printf("\n\t栈为空！ ");else *x=s->elem[s->top];}/*判断栈是否为空*/int IsEmpty(SeqStack *s){if(s->top==-1) return(0);else return(1);}/*魔王语言翻译函数*/void GhostLanage(){SeqStack B,A,s,B1,A1,r,M;StackElementType ch,ch1,ch2,x;char aa[100];int choice,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); }}else Push(&r,ch1);}}else if(ch=='A'){A1=A;while(IsEmpty(&A1)) {Pop(&A1,&ch2); Push(&r,ch2); }}else if(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);}else Push(&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("天");else if(ch=='d') printf("地");else if(ch=='s') printf("上");else if(ch=='a') printf("一只");else if(ch=='e') printf("鹅");else if(ch=='z') printf("追");else if(ch=='g') printf("赶");else if(ch=='x') printf("下");else if(ch=='n') printf("蛋");else if(ch=='h') printf("恨");}printf("\n");}else ;}三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。