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

實習(xí)2、魔王語言解釋一、需求分析.問題描述有一個魔王總是使用自己的一種非常精練而抽象的語言講話，沒人能聽的情，但他的語言是可以逐步解釋成人能懂得語言的，因為他的語言是由以下兩種形式的規(guī)則由人的語言逐步抽象上去的：a->P1P2...Pn(06162...6n)一>96n06n-l...0610在這兩種形式中，從左到右均表示解釋。試寫?個魔王解釋系統(tǒng)，把他的話解釋成人能聽懂得話。.基本要求用下述兩條具體規(guī)則和上述規(guī)則形式(2)實現(xiàn)。設(shè)大寫字母表示魔王語言的詞匯；小寫字母表示人的語言詞匯；希臘字母表示可以用大寫或小寫字母代換的變量。魔王語言可含人的詞匯。B—>tAdAA—>sae.測試數(shù)據(jù)B(ehnxgz)B解釋成Isaedsaeezegexenehelsaedsae若將小寫字母與漢字建立下表所示的對應(yīng)關(guān)系，則魔王說的話是“天上一個鵝地上一個鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一個鵝地上一個鵝”。tdSaeZgXnh天地上-只鵝追趕下蛋恨.實現(xiàn)提示將魔王的語言自右至左進(jìn)棧，總是處理棧頂字符。若是開括號，則逐一出棧，將字母頓序入隊列，直至閉括號出棧，并按規(guī)則要求逐一出隊列再處理后入棧。其他情形較簡單，請讀者思考如何處理。應(yīng)首先實現(xiàn)棧和隊列的基本操作。二、概要設(shè)計1、設(shè)定棧的抽象數(shù)據(jù)類型定義：ADTStack{數(shù)據(jù)對象：D={a|aCharSet,i=1,2,n,.n20}數(shù)據(jù)關(guān)系:Rl={<a,a>|a,aGD,a<a,i=l,2,n}i-1ii-lii-li基本操作：InilStack(*S)操作結(jié)果：構(gòu)造一個空棧。Push(*S,e)初始條件：棧S已存在操作結(jié)果：在棧頂插入新的元素。Pop(*S,*e)初始條件：棧S已存在操作結(jié)果：刪除棧頂元素，并用e返回其值。StackEmpty(S)初始條件：棧S已存在操作結(jié)果：若S為空棧，則返回I,否則返回0。ClcarStack(*S)初始條件：棧S已存在操作結(jié)果：將棧S清空。InStack(char*ch,SqStack*s)初始條件：棧S已存在操作結(jié)果：把字符數(shù)組從右至左壓入棧中。}ADTStackADTQueue{數(shù)據(jù)對象:D={ai|aiCharSeti=1,2,n,.n20}數(shù)據(jù)關(guān)系：Rl={<ai-l,ai>|ai-l,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為空棧，則返網(wǎng)1,否則返回0。}ADTQueue三、詳細(xì)設(shè)計(源代碼)(使用C語言)#include<stdio.h>#include<stdlib.h>#defineSTACK_INIT_SIZE100〃存儲空間初始分配量#defineSTACKINCREMENT10〃存儲空間分配增量typedefstruct(char*base;〃棧底指針char*top;〃棧頂指針intstacksize;}SqStack;typedefstructQNotechardata;structQNote*next;jQNote/QueuePtr;typedefstruct(QueuePtrfront;〃隊頭指針QueuePtrrear;〃隊尾指針}LinkQueue;voidlnitStack(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++;)voidPopfSqStack*s,char*e){〃元素e出棧*e=*-s->top;)intStackEmptyfSqStacks){〃判斷棧是否為空if(s.top==s.base)return1;elsereturn0;voidClearStack(SqStack*s){〃清空棧s->top=s->base;)voidInitQueuefLinkQueue*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;elsereturn0;}voidlnStack(char*chzSqStack*s){〃把字符數(shù)組從右至左壓入棧中inti,L=0;while(ch[L]!='\O')

L++;for(i=L-l;i>=0;i-)Push(s,ch[i]);)intmain()printf(M**************************************************************printf("*****************************printffprintf(printf(II*“**魔王語言解釋系統(tǒng)*****************************II**************************************************************，\n")；*\n")；*\n")；*\n")；\n")；intxunhuan=l;printf（"請輸入您想要解釋的魔王語言：\n"）；while(xunhuan==l)while(xunhuan==l)while(xunhuan==l)〃一個總循環(huán)控制整個程序的重登進(jìn)行charA[]="sae";charB[]="tsaedsae";charflag='O';charel,key,e2,e,i=0;intmark=l;intf=l;charMoWang[100]="\0";〃大寫字母作為字符數(shù)組名存放小寫字母while(xunhuan==l)〃一個總循環(huán)控制整個程序的重登進(jìn)行charA[]="sae";charB[]="tsaedsae";charflag='O';charel,key,e2,e,i=0;intmark=l;intf=l;charMoWang[100]="\0";〃大寫字母作為字符數(shù)組名存放小寫字母//flag用來標(biāo)記處理括號〃標(biāo)記輸入的魔王語言是否在允許的范圍之內(nèi)//判斷括號是否匹配〃定義一個魔王變量，存放待解釋的語言字符SqStackS;SqStacktemp;lnitStack(&S);lnitStack(&temp);LinkQueueQ;lnitQueue(&Q);gets(MoWang);lnStack(MoWang,&S);while(SStackEmpty(S))〃作為棧存儲元素，為后續(xù)操作和輸出做準(zhǔn)備〃用來處理括號外的元素〃變量MoWang存儲輸入的語言〃把要解釋的魔王語言壓入棧中〃把魔王語言進(jìn)行出棧，不符合語言的進(jìn)行提示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)〃判斷是否存在空括號(本程序設(shè)空括號為非法語言)f=0;break;)elseif(!(el>='a,&&el<='z,)&&!(el>=,A,&&el<=,Z')){printf("魔王語言錯誤!\n");mark=O;break;if(mark==O)break;if(f!=l)printf("魔王語言錯誤!\n");break;printf("魔王語言錯誤!\n");mark=O;break;elseif(!(el>='a'&&el<=,z')&&!(el>='A,&&el<=,Z'))printf("魔王語言錯誤!\n");mark=O;break;if(mark==l&&f==l)if(mark==l&&f==l)if(mark==l&&f==l)〃對符合語言規(guī)則的魔王語言進(jìn)行規(guī)則處理ClearStack(&S);if(mark==l&&f==l)〃對符合語言規(guī)則的魔王語言進(jìn)行規(guī)則處理ClearStack(&S);lnStack(MoWang,&S);while(!StackEmpty(S))ClearStack(&S);lnStack(MoWang,&S);while(!StackEmpty(S))ClearStack(&S);lnStack(MoWang,&S);while(!StackEmpty(S))〃把魔王語言從右至左壓棧存放〃棧不空時，用棧temp進(jìn)行存儲不帶括號內(nèi)元素的元素的元素Pop(&S,&el);

if(el=='B'||el=='A')Push(&temp,el);elseif(el=='(')〃用隊存儲括號中的元素的元素Pop(&S,&el);(Push(&temp,flag);〃有括號的話就用flag標(biāo)記Pop(&S,&el);while(el!=')')〃把括號中的元素存入隊列中(EnQueue(&Cbel);Pop(&S,&el);)if(!QueueEmpty(Q))DeQueue(&Q,&key);//將隊頭的元素賦值給key)elsePush(&temp,el);)while(!StackEmpty(temp))〃將魔王說的語言規(guī)則地壓入棧s中{

Pop(&temp,&el);

if(el!=flag)

Push(&S,el);〃把括號外的元素壓入棧s中elsewhile(!QueueEmpty(Q))〃處理括號中的元素進(jìn)棧

{

DeQueue(&Ct&e2);

Push(&S,key);

Push(&S,e2);

)

Push(&S,key);〃最后還要壓?個key

)

)

printf("解釋后的語言為：\n");

while(!StackEmpty(S))〃依次出棧輸出處理后的元素{Pop(&S,&e);EnQUeue(&(Xe);〃元素進(jìn)隊是為了輸出對應(yīng)漢字〃翻譯成對應(yīng)的漢字if(e=='B')printf("%s"zB);elseif(e==,A')printf("%s",A);elseprintf("%c"ze);)printf("\n");while(!QueueEmpty(Q))DeQueue（&Q,&e）;〃翻譯成對應(yīng)的漢字switch（e）{case'f: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;caseB:printf（“天上一只鵝地上一只鵝”）;break;case'A':printf（"上一只鵝，break;default:printf（"（對不起此處為非法字符或詞匯!）"）;break;））printf（"\n"）;）printf（"再次輸入魔王語言（按數(shù)字鍵0退出）\n”）；scanf（"%d",&xunhuan）;）return0;）四、調(diào)試分析編譯環(huán)境為CodeBlockSo魔干語言解釋系統(tǒng)請輸入您想要解釋的魔王語言：B<ehnxgz>B解釋后的語言為，tcaodGaeoNegoxc