魔王语言解释-数据结构课程设计.docx

《魔王语言解释-数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《魔王语言解释-数据结构课程设计.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实习2、魔王语言解释一、需求分析.问题描述有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的情，但他的语言 是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象 上去的：(1) a-P 1 P2 . Pn(2) (0 6 16 2. 6 n) 一9 6 n 0 6 n-l . 0 6 1 0在这两种形式中，从左到右均表示解释。试写个魔王解释系统，把他的话解释成人能听懂 得话。1 .基本要求用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇；小 写字母表示人的语言词汇；希腊字母表示可以用大写或小写字母代换的变量。魔王语言可含人

2、的词汇。(1) BtAdA(2) Asae.测试数据B (ehnxgz) B 解释成Isaedsaeezegexenehelsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅 鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅”。tdSaeZgXnh天地上-只鹅追赶下蛋恨.实现提示将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顿序 入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思 考如何处理。应首先实现栈和队列的基本操作。二、概要设计1、设定栈的抽象数据类型定义：ADT Stack 数据对象：D=

3、 a | a CharSet, i= 1,2,n,.n20 数据关系:Rl= | a ,a GD, a a ,i=l,2,ni-1 i i-l i i-l i基本操作：InilStack(*S)操作结果：构造一个空栈。Push(*S,e)初始条件：栈S已存在操作结果：在栈顶插入新的元素。Pop(*S,*e)初始条件：栈S已存在操作结果：删除栈顶元素，并用e返回其值。StackEmpty(S)初始条件：栈S已存在操作结果：若S为空栈，则返回I,否则返回0。ClcarStack(*S)初始条件：栈S已存在操作结果：将栈S清空。InStack(char* ch,SqStack *s)初始条件：栈S已

4、存在操作结果：把字符数组从右至左压入栈中。ADT StackADT Queue 数据对象:D=ai | ai CharSet i= 1,2,n,.n20 数据关系：Rl= |ai-l,aiD t i= 1,2,n基本操作：InitQueue (*Q)操作结果：构造一个空队列Q。EnQueue (*Q,e)初始条件：队列Q已经存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue (*Q,*e)初始条件：队列Q已经存在。操作结果：删除Q的对头元素，并以e返何其值。QueueEmpty (Q)初始条件：队列Q已经存在。操作结果：若队列Q为空栈，则返网1,否则返回0。ADT Queue三、详细

5、设计(源代码)(使用C语言)#include#include#define STACK_INIT_SIZE 100存储空间初始分配量#define STACKINCREMENT 10存储空间分配增量typedef struct(char* base;栈底指针char* top;栈顶指针int stacksize;SqStack;typedef struct QNotechar data;struct QNote *next;jQNote/QueuePtr;typedef struct (QueuePtr front;队头指针QueuePtr rear; 队尾指针LinkQueue;void l

6、nitStack(SqStack *s)构造一个空栈s-base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);s-top=s-base;s-stacksize=STACK_INIT_SIZE;)void Push(SqStack *s,char e)插入元素e为新的栈顶元素if(s-top-s-base=STACK_INIT_SIZE)(s-base=(char*)realloc(s-base/(s-stacksize+STACKINCREMENT)*sizeof(char); s-top=s-base+s-stacksize;s-stacksize+

7、=ST ACKINCREMENT;)*(s-top)=e;s-top+;)void PopfSqStack *s,char *e)元素e出栈*e=*-s-top;)int StackEmptyfSqStack s)判断栈是否为空if(s.top=s.base)return 1;else return 0;void ClearStack(SqStack *s)清空栈s-top=s-base;)void InitQueuefLinkQueue *q)构造一个空队列q-front=q-rear=(QNote*)malloc(sizeof(QNote); q-front-next=NULL;)void

8、 EnQueue(LinkQueue *q,char e)插入元素e为新的队尾元素QNote*P；p=(QNote*)malloc(sizeof(QNote);p-data=e;p-next=NULL;q-rear-next=p;q-rear=p;)void DeQueue(LinkQueue *q,char *e)元素出队QNote *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(LinkQueue q)判断队列是否为空if(q.front=q

9、.rear)return 1;elsereturn 0;void lnStack(char* chzSqStack *s)把字符数组从右至左压入栈中int i,L=0;while(chL!=O)L+;for(i=L-l;i=0;i-)Push(s,chi);) int main()printf(M*printf(*printff printf( printf(II*“*魔王语言解释系统*II*，n)；*n)；*n)；*n)；n)；int xunhuan=l;printf（请输入您想要解释的魔王语言：n）；while (xunhuan=l)while (xunhuan=l)一个总循环控制整个程序

10、的重登进行char A=sae;char B=tsaedsae;char flag=O;char el,key,e2,e,i=0;int mark=l;int f=l;char MoWang100=0;大写字母作为字符数组名存放小写字母/flag用来标记处理括号标记输入的魔王语言是否在允许的范围之内/判断括号是否匹配定义一个魔王变量，存放待解释的语言字符SqStack S;SqStack temp; lnitStack(&S); lnitStack(&temp); LinkQueue Q; lnitQueue(&Q); gets(MoWang); lnStack(MoWang,&S); whi

11、le( SStackEmpty(S)作为栈存储元素，为后续操作和输出做准备 用来处理括号外的元素变量MoWang存储输入的语言把要解释的魔王语言压入栈中把魔王语言进行出栈，不符合语言的进行提示Pop(&S,&el);if(el=()(if(StackEmpty(S)printf(魔王语言错误!n”);mark=0;f=0;break;)while(!StackEmpty(S)Pop(&S,&el);if(el=)if(i=O)判断是否存在空括号(本程序设空括号为非法语言) f=0;break;)else if(!(el=a,&el=,A,&el=a&el=A,&el=,Z)printf(魔王语

12、言错误! n);mark=O;break;if(mark=l&f=l)if(mark=l&f=l)对符合语言规则的魔王语言进行规则处理ClearStack(&S);lnStack(MoWang,&S);while(!StackEmpty(S)ClearStack(&S);lnStack(MoWang,&S);while(!StackEmpty(S)把魔王语言从右至左压栈存放栈不空时，用栈temp进行存储不带括号内元素的元素的元素Pop(&S,&el);if(el=B|el=A) Push(&temp,el); else if(el=()用队存储括号中的元素( Push(&temp,flag);

13、有括号的话就用flag标记Pop(&S,&el); while(el!=)把括号中的元素存入队列中( EnQueue(&Cbel); Pop(&S,&el); ) if(!QueueEmpty(Q) DeQueue(&Q,&key); /将队头的元素赋值给key ) else Push(&temp,el); ) while(!StackEmpty(temp)将魔王说的语言规则地压入栈s中Pop(&temp,&el);if(el!=flag)Push(&S,el);把括号外的元素压入栈s中elsewhile(!QueueEmpty(Q) 处理括号中的元素进栈DeQueue(&Ct&e2);Pus

14、h(&S,key);Push(&S,e2);)Push(&S,key); 最后还要压个key)printf(解释后的语言为：n);while(!StackEmpty(S)依次出栈输出处理后的元素 Pop(&S,&e); EnQUeue(&(Xe);元素进队是为了输出对应汉字翻译成对应的汉字if(e=B) printf(%szB); else if(e=,A) printf(%s,A); else printf(%cze); ) printf(n); while(!QueueEmpty(Q)DeQueue（&Q,&e）;switch（e） case f: printf（）;break;cased

15、: 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（对不起此

16、处为非法字符或词汇! ）;break;）printf（n）;）printf（再次输入魔王语言（按数字键0退出）n”）； scanf（%d,&xunhuan）;）return 0;）四、调试分析编译环境为CodeBlockSo魔干语言解释系统请输入您想要解释的魔王语言：BB解释后的语言为，tcaodGaeoNegoxcnehotGaedsao天上二区番地上二嘤醺鹅赶期F鹅蛋瑞恨鹅天上一只鹅地上一只解 再次输入费王语言G瓣铤味迅）AA解释后的语言为.晾献奋上二圭第鬻牖1后只鹅sactsAcdaacdacItdsaae解释后的语言为，tdsaqe区单上丁旦对不.起亚律为非法于符或词汇！）鹅 再次输入廉王语言按敬字铤褪出）魔王语言错误，再次输入魔工语言按数字键。退出AO魔王询错世误！再茨城X魔王语m按数字铤喔出、魔王语言错误！再次输入魔王语言（按数字铤鳍出）iucess returned 0 execuliun tiinc ： 113.160 sress any key to continue.in