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

1、實(shí)習(xí)2、魔王語(yǔ)言解釋一、 需求分析1. 問題描述有一個(gè)魔王總是使用自己的一種非常精練而抽象的語(yǔ)言講話，沒人能聽的懂，但他的語(yǔ)言是可以逐步解釋成人能懂得語(yǔ)言的，因?yàn)樗恼Z(yǔ)言是由以下兩種形式的規(guī)則由人的語(yǔ)言逐 步抽象上去的：（1）-1 2 . n（2）( 1 2 . n) n n-1 . 1 在這兩種形式中，從左到右均表示解釋。試寫一個(gè)魔王解釋系統(tǒng)，把他的話解釋成人能聽懂得話。2. 基本要求 用下述兩條具體規(guī)則和上述規(guī)則形式（2）實(shí)現(xiàn)。設(shè)大寫字母表示魔王語(yǔ)言的詞匯；小寫字母表示人的語(yǔ)言詞匯；希臘字母表示可以用大寫或小寫字母代換的變量。魔王語(yǔ)言可含人的詞匯。 （1）BtAdA （2）Asae 3.

2、測(cè)試數(shù)據(jù)B（ehnxgz）B 解釋成tsaedsaeezegexenehetsaedsae若將小寫字母與漢字建立下表所示的對(duì)應(yīng)關(guān)系，則魔王說的話是“天上一個(gè)鵝地上一個(gè)鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一個(gè)鵝地上一個(gè)鵝”。 tdsaezgxnh天地上一 只鵝追趕下蛋恨4. 實(shí)現(xiàn)提示 將魔王的語(yǔ)言自右至左進(jìn)棧，總是處理?xiàng)ｍ斪址?。若是開括號(hào)，則逐一出棧，將字母順序入隊(duì)列，直至閉括號(hào)出棧，并按規(guī)則要求逐一出隊(duì)列再處理后入棧。其他情形較簡(jiǎn)單，請(qǐng)讀者思考如何處理。應(yīng)首先實(shí)現(xiàn)棧和隊(duì)列的基本操作。二、 概要設(shè)計(jì)1、 設(shè)定棧的抽象數(shù)據(jù)類型定義：ADT Stack 數(shù)據(jù)對(duì)象：D= ai| aiCharSet, i= 1

3、,2,n,. n0 數(shù)據(jù)關(guān)系：R1= | ai-1,aiD, ai-1ai ,i=1,2,n 基本操作： InitStack(*S) 操作結(jié)果：構(gòu)造一個(gè)空棧。 Push(*S,e) 初始條件：棧S已存在 操作結(jié)果：在棧頂插入新的元素。 Pop(*S,*e) 初始條件：棧S已存在 操作結(jié)果：刪除棧頂元素，并用e返回其值。 StackEmpty(S) 初始條件：棧S已存在 操作結(jié)果：若S為空棧，則返回1，否則返回0。ClearStack(*S) 初始條件：棧S已存在 操作結(jié)果：將棧S清空。InStack(char* ch,SqStack *s) 初始條件：棧S已存在 操作結(jié)果：把字符數(shù)組從右至左壓

4、入棧中。ADT StackADT Queue數(shù)據(jù)對(duì)象：D=ai | aiCharSet i= 1,2,n,. n0 數(shù)據(jù)關(guān)系：R1= |ai-1,aiD t i= 1,2,n 基本操作：InitQueue (*Q) 操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。EnQueue（*Q,e）初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue（*Q,*e）初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：刪除Q的對(duì)頭元素，并以e返回其值。QueueEmpty（Q）初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：若隊(duì)列Q為空棧，則返回1，否則返回0。ADT Queue三、 詳細(xì)設(shè)計(jì)（源代碼）（使用C語(yǔ)言）#incl

5、ude#include#define STACK_INIT_SIZE 100/存儲(chǔ)空間初始分配量#define STACKINCREMENT 10/存儲(chǔ)空間分配增量typedef struct char* base;/棧底指針 char* top;/棧頂指針 int stacksize;SqStack;typedef struct QNote char data; struct QNote *next;QNote,*QueuePtr;typedef struct QueuePtr front;/隊(duì)頭指針 QueuePtr rear;/隊(duì)尾指針LinkQueue;void InitStack(S

6、qStack *s)/構(gòu)造一個(gè)空棧 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+=STA

7、CKINCREMENT; *(s-top)=e; s-top+;void Pop(SqStack *s,char *e)/元素e出棧 *e=*-s-top;int StackEmpty(SqStack s)/判斷棧是否為空 if(s.top=s.base) return 1; else return 0;void ClearStack(SqStack *s)/清空棧 s-top=s-base;void InitQueue(LinkQueue *q)/構(gòu)造一個(gè)空隊(duì)列 q-front=q-rear=(QNote*)malloc(sizeof(QNote); q-front-next=NULL;vo

8、id EnQueue(LinkQueue *q,char e)/插入元素e為新的隊(duì)尾元素 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)/元素出隊(duì) 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)/判斷隊(duì)

9、列是否為空 if(q.front=q.rear) return 1; else return 0;void InStack(char* ch,SqStack *s)/把字符數(shù)組從右至左壓入棧中 int i,L=0; while(chL!=0) L+; for(i=L-1;i=0;i-) Push(s,chi);int main() printf(*n); printf(* * *n); printf(* * 魔王語(yǔ)言解釋系統(tǒng) * *n); printf(* * *n); printf(*n); int xunhuan=1; printf(請(qǐng)輸入您想要解釋的魔王語(yǔ)言：n); while (xun

10、huan=1) /一個(gè)總循環(huán)控制整個(gè)程序的重復(fù)進(jìn)行 char A=sae; /大寫字母作為字符數(shù)組名存放小寫字母 char B=tsaedsae; char flag=0; /flag用來標(biāo)記處理括號(hào) char e1,key,e2,e,i=0; int mark=1; /標(biāo)記輸入的魔王語(yǔ)言是否在允許的范圍之內(nèi) int f=1; / 判斷括號(hào)是否匹配 char MoWang100=0; /定義一個(gè)魔王變量，存放待解釋的語(yǔ)言字符 SqStack S; /作為棧存儲(chǔ)元素，為后續(xù)操作和輸出做準(zhǔn)備 SqStack temp; /用來處理括號(hào)外的元素 InitStack(&S); InitStack(&t

11、emp); LinkQueue Q; InitQueue(&Q); gets(MoWang); /變量MoWang存儲(chǔ)輸入的語(yǔ)言 InStack(MoWang,&S); /把要解釋的魔王語(yǔ)言壓入棧中 while(!StackEmpty(S) /把魔王語(yǔ)言進(jìn)行出棧，不符合語(yǔ)言的進(jìn)行提示 Pop(&S,&e1); if(e1=() if(StackEmpty(S) printf(魔王語(yǔ)言錯(cuò)誤!n); mark=0;f=0; break; while(!StackEmpty(S) Pop(&S,&e1); if(e1=) if(i=0)/判斷是否存在空括號(hào)（本程序設(shè)空括號(hào)為非法語(yǔ)言） f=0; br

12、eak; else if(!(e1=a&e1=A&e1=a&e1=A&e1=Z) printf(魔王語(yǔ)言錯(cuò)誤！n); mark=0; break; if(mark=1&f=1) /對(duì)符合語(yǔ)言規(guī)則的魔王語(yǔ)言進(jìn)行規(guī)則處理 ClearStack(&S); InStack(MoWang,&S); /把魔王語(yǔ)言從右至左壓棧存放 while(!StackEmpty(S) /棧不空時(shí)，用棧temp進(jìn)行存儲(chǔ)不帶括號(hào)內(nèi)元素的元素 Pop(&S,&e1); if(e1=B|e1=A) Push(&temp,e1); else if(e1=() /用隊(duì)存儲(chǔ)括號(hào)中的元素 Push(&temp,flag); /有括號(hào)的

13、話就用flag標(biāo)記 Pop(&S,&e1); while(e1!=) /把括號(hào)中的元素存入隊(duì)列中 EnQueue(&Q,e1); Pop(&S,&e1); if(!QueueEmpty(Q) DeQueue(&Q,&key); /將隊(duì)頭的元素賦值給key else Push(&temp,e1); while(!StackEmpty(temp) /將魔王說的語(yǔ)言規(guī)則地壓入棧s中 Pop(&temp,&e1); if(e1!=flag) Push(&S,e1); /把括號(hào)外的元素壓入棧s中 else while(!QueueEmpty(Q) /處理括號(hào)中的元素進(jìn)棧 DeQueue(&Q,&e2);

14、 Push(&S,key); Push(&S,e2); Push(&S,key); /最后還要壓一個(gè)key printf(解釋后的語(yǔ)言為：n); while(!StackEmpty(S) /依次出棧輸出處理后的元素 Pop(&S,&e); EnQueue(&Q,e); /元素進(jìn)隊(duì)是為了輸出對(duì)應(yīng)漢字 if(e=B) printf(%s,B); else if(e=A) printf(%s,A); else printf(%c,e); printf(n); while(!QueueEmpty(Q) /翻譯成對(duì)應(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 : printf(鵝); break; case z : printf(追); break; case g : printf(趕); break; case x : printf(下); break; case n : printf(