魔王語言解釋-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

....,.,.實習(xí)2、魔王語言解釋一、需求分析問題描述步抽象上去的：（1）α->β1β2...βn（2）(θ δ1δ2...δn)—>θ δnθ δn-1...θ δ1θ聽懂得話。基本要求用下述兩條具體規(guī)則和上述規(guī)則形式B—>tAdAA—>sae測試數(shù)據(jù)B（ehnxgz）B解釋成tsaedsaeezegexenehetsaedsae若將小寫字母與漢字建立下表所示的對應(yīng)關(guān)系鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一個鵝地上一個鵝”。tdsaezgxnh天地上—只鵝追趕下蛋恨實現(xiàn)提示將魔王的語言自右至左進棧，總是處理棧頂字符。若是開括號，則逐一出棧讀者思考如何處理。應(yīng)首先實現(xiàn)棧和隊列的基本操作。二、概要設(shè)計1、設(shè)定棧的抽象數(shù)據(jù)類型定義：ADTStack{數(shù)據(jù)對象：D={a|a∈CharSet,i=1,2,……n,.n≥0}i i數(shù)據(jù)關(guān)系<a ,a>|a ,a∈D,a <a,i=1,2……,n}基本操作：InitStack(*S)

i-1

i-1

i-1 i操作結(jié)果：構(gòu)造一個空棧。Push(*S,e)初始條件：棧S已存在操作結(jié)果：在棧頂插入新的元素。Pop(*S,*e)初始條件：棧S已存在操作結(jié)果：刪除棧頂元素，并用e返回其值。StackEmpty(S)初始條件：棧S已存在操作結(jié)果：若S1ClearStack(*S)初始條件：棧S已存在操作結(jié)果：將棧SInStack(char*ch,SqStack*s)初始條件：棧S已存在操作結(jié)果：把字符數(shù)組從右至左壓入棧中。}ADTStackADTQueue{數(shù)據(jù)對象：D={ai|ai∈CharSeti=1,2,……n,.n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈Dti=1,2,……n}基本操作：InitQueue(*Q)操作結(jié)果：構(gòu)造一個空隊列Q。EnQueue（*Q,e）初始條件：隊列Q已經(jīng)存在。操作結(jié)果：插入元素e為Q的新的隊尾元素。DeQueue（*Q,*e）初始條件：隊列Q已經(jīng)存在。操作結(jié)果：刪除Q的對頭元素，并以e返回其值。QueueEmpty（Q）初始條件：隊列Q已經(jīng)存在。操作結(jié)果：若隊列Q為空棧，則返回1，否則返回0。}ADTQueue三、詳細設(shè)計（源代碼）（使用C語言）#include<stdio.h>#include<stdlib.h>#defineSTACK_INIT_SIZE存儲空間初始分配量#defineSTACKINCREMENT存儲空間分配增量typedefstruct{char*base;//棧底指針char*top;//棧頂指針intstacksize;}SqStack;typedefstructQNote{chardata;structQNote*next;}QNote,*QueuePtr;typedefstruct{QueuePtr隊頭指針QueuePtr隊尾指針}LinkQueue;voidInitStack(SqStack*s){//構(gòu)造一個空棧s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));s->top=s->base;s->stacksize=STACK_INIT_SIZE;}voidPush(SqStack*s,chare){//插入元素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+=STACKINCREMENT;}*(s->top)=e;s->top++;}voidPop(SqStack*s,char*e){//元素e出棧*e=*--s->top;}intStackEmpty(SqStacks){//判斷棧是否為空if(s.top==s.base)return1;elsereturn0;}voidClearStack(SqStack*s){//清空棧s->top=s->base;}voidInitQueue(LinkQueue*q){//構(gòu)造一個空隊列q->front=q->rear=(QNote*)malloc(sizeof(QNote));q->front->next=NULL;}voidEnQueue(LinkQueue*q,chare){//插入元素e為新的隊尾元素QNote*p;p=(QNote*)malloc(sizeof(QNote));p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;}voidDeQueue(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);}intQueueEmpty(LinkQueueq){//判斷隊列是否為空if(q.front==q.rear)return1;else}

return0;voidInStack(char*ch,SqStack*s){//把字符數(shù)組從右至左壓入棧中inti,L=0;while(ch[L]!='\0')L++;for(i=L-1;i>=0;i--)Push(s,ch[i]);}intmain(){printf("* **************************** *\n");printf("* * 魔王語言解釋系統(tǒng)* *\n");printf("* **************************** *\n");intxunhuan=1;printf("請輸入您想要解釋的魔王語言：\n");while(xunhuan==1) //一個總循環(huán)控制整個程序的重復(fù)進行{charA[]="sae"; //charB[]="tsaedsae";charflag='0'; //flag用來標記處理括號chare1,key,e2,e,i=0;intmark=1; //標記輸入的魔王語言是否在允許的范圍之內(nèi)intf=1; //判斷括號是否匹配charMoWang[100]="\0"; //定義一個魔王變量，存放待解釋的語言字SqStackS; //作為棧存儲元素，為后續(xù)操作和輸出做準備SqStacktemp; //用來處理括號外的元素InitStack(&S);InitStack(&temp);LinkQueueQ;InitQueue(&Q);gets(MoWang); //MoWang存儲輸入的語言InStack(MoWang,&S); //把要解釋的魔王語言壓入棧中while(!StackEmpty(S)) //把魔王語言進行出棧，不符合語言的進行提{Pop(&S,&e1);if(e1=='('){if(StackEmpty(S)){!\n");mark=0;f=0;break;}while(!StackEmpty(S)){Pop(&S,&e1);if(e1==')'){if(i==0)//判斷是否存在空括號（本程序設(shè)空括號為非法語言）f=0;break;}elseif(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z')){}i++;}

printf("魔王語言錯誤！\n");mark=0;break;if(mark==0)break;if(f!=1){printf("魔王語言錯誤！\n");break;}}elseif(e1==')'){printf("魔王語言錯誤！\n");mark=0;break;}elseif(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z')){printf("魔王語言錯誤！\n");mark=0;break;}}if(mark==1&&f==1) //對符合語言規(guī)則的魔王語言進行規(guī)則處理{的元素

ClearStack(&S);InStack(MoWang,&S); //把魔王語言從右至左壓棧存放while(!StackEmpty(S)) //棧不空時，用棧temp進行存儲不帶括號內(nèi)元{Pop(&S,&e1);if(e1=='B'||e1=='A')Push(&temp,e1);elseif(e1=='(') //用隊存儲括號中的元素{Push(&temp,flag); //flagPop(&S,&e1);while(e1!=')') //把括號中的元素存入隊列中{EnQueue(&Q,e1);Pop(&S,&e1);}}else

if(!QueueEmpty(Q))DeQueue(&Q,&key);//將隊頭的元素賦值給keyPush(&temp,e1);}while(!StackEmpty(temp)) //將魔王說的語言規(guī)則地壓入棧s中{Pop(&temp,&e1);if(e1!=flag)Push(&S,e1); //s中else{

while(!QueueEmpty(Q)) //處理括號中的元素進棧{DeQueue(&Q,&e2);Push(&S,key);Push(&S,e2);}Push(&S,key);//最后還要壓一個key}}printf("解釋后的語言為：\n");while(!StackEmpty(S)) //依次出棧輸出處理后的元素{Pop(&S,&e);EnQueue(&Q,e); //if(e=='B')printf("%s",B);elseif(e=='A')printf("%s",A);elseprintf("%c",e);}printf("\n");while(!QueueEmpty(Q)) //翻譯成對應(yīng)的漢字{DeQueue(&Q,&e);switch(e){case't':printf("天");break;case'd':printf("地");break;case's':printf("上");break;case'a':printf("一只");break;case'e':鵝");break;case'z':追");break;case'g':趕");break;case'x':下");break;case'n'