魔王語言解釋

1、. 實(shí)習(xí)報(bào)告 題目：編制一個魔王語言解釋的程序 班級：06052711 姓名：曹旭 學(xué)號：06057104 完成日期：2007.11.27一、 需求分析問題描述  有一個魔王總是使用自己的一種非常精練而抽象的語言講話，沒人能聽的懂。但他的語言是可以逐步解釋成人能懂得語言的，因?yàn)樗恼Z言是由以下兩種形式的規(guī)則由人的語言逐 步抽象上去的：     （1）->12.n（2）(12.n)->nn-1.1    在這兩種形式中，從左到右均表示解釋；從右到左表示抽象。試寫一個魔王解釋系統(tǒng)，把     他的話解釋成人能聽懂得話

2、。   基本要求     用下述兩條具體規(guī)則和上述規(guī)則形式（2）實(shí)現(xiàn)。設(shè)大寫字母表示魔王語言的詞匯；小寫字     母表示人的語言詞匯；希臘字母（a,b1,s,y1等）表示可以用大寫或小寫字母代換的變量。     魔王語言可含人的詞匯。     （1）B->tAdA       (2)   A->sae   測試數(shù)據(jù)     B（einxgz）B     解釋成     tsaedsa

3、eezegexeneietsaedsae                                           若將小寫字母與漢字建立下表所示的對應(yīng)關(guān)系，則魔王說的話是“天上一個鵝地上一個鵝     鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一個鵝地上一個鵝。”     t d s a e z G x n i     天 地 上

4、一個 鵝 追   趕 下 蛋 恨   實(shí)現(xiàn)提示     將魔王的語言自右至左進(jìn)棧，總是處理?xiàng)ｍ敗Ｈ羰情_括號，則逐一出棧，將字母順序入隊(duì)     列，直至閉括號出棧，并按規(guī)則要求逐一出隊(duì)列再處理后入棧。其他情形較簡單，請讀者     思考如何處理，應(yīng)首先實(shí)現(xiàn)棧和隊(duì)列的基本運(yùn)算二、 概要設(shè)計(jì) 為實(shí)現(xiàn)上述程序功能，應(yīng)以棧和隊(duì)列來表示。1. 設(shè)定棧的抽象數(shù)據(jù)類型定義為： ADT Stack 數(shù)據(jù)對象：D=ai | aiCharSet，I=1，2，.，n,n0 數(shù)據(jù)關(guān)系：R1=< ai-1，ai > |ai-1，

5、aiD,I=1，2，.，n 基本操作： ListInitiate (&S) 操作結(jié)果：構(gòu)造一個空棧S。StackEmpty（S）初始條件：棧S已經(jīng)存在。操作結(jié)果：若棧S為空棧，則返回TRUE，否則返回FALSE。Push（&S,e）初始條件：棧S已經(jīng)存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop（&S,&e）初始條件：棧S已經(jīng)存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。 ADT Stack2. 設(shè)定隊(duì)列的抽象數(shù)據(jù)類型定義為：ADTQueue 數(shù)據(jù)對象：D=ai | aiElemSet，I=1，2，.，n,n0 數(shù)據(jù)關(guān)系：R1=< ai-1，a

6、i > |ai-1，aiD,I=1，2，.，n 基本操作： ListInitiate (&Q) 操作結(jié)果：構(gòu)造一個空隊(duì)列Q。StackEmpty（Q）初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：若隊(duì)列Q為空棧，則返回TRUE，否則返回FALSE。EnQueue（&Q,e）初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue（&Q,&e）初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：刪除Q的對頭元素，并以e返回其值。 ADT Queue2. 程序包含四個模塊：1） 主程序模塊：Void main()初始化；For（）接受處理命令；接受處理；2） 棧

7、模塊實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型；3） 隊(duì)列模塊實(shí)現(xiàn)隊(duì)列的抽象數(shù)據(jù)類型。4） 魔王語言解釋模塊定義線性表的結(jié)點(diǎn)結(jié)構(gòu)。各模塊的之間的調(diào)用關(guān)系如下： 主程序模塊 魔王語言解釋模塊     棧模塊隊(duì)列模塊三、 詳細(xì)設(shè)計(jì)1. 站類型typedef structchar *base;char *top;int stacksize;stack;2. 隊(duì)列類型typedef struct QNodechar data;struct QNode *next;QNode,*LinkQueueNode;typedef structLinkQueueNode front;LinkQueueNode re

8、ar;LinkQueue;3.棧的基本操作int Initstack(stack &s) s.base=(char*)malloc(100*sizeof(char); if(!s.base)exit(0); s.top=s.base; s.stacksize=100; return 1;int IsEmpty(stack s) if(s.top=s.base)return 1;return 0;void push(stack &s,char e)if(s.top-s.base>=s.stacksize)s.base=(char*)realloc(s.base,(s.sta

9、cksize+10)*sizeof(char);if(!s.base)exit(0);s.top=s.base+s.stacksize;s.stacksize+=10;*s.top+=e;int pop(stack &s,char &e)if(s.top=s.base)exit(0);e=*-s.top;return 1;4隊(duì)列的基本操作int initQueue(LinkQueue &Q)Q.front=Q.rear=(LinkQueueNode)malloc(sizeof(LinkQueueNode);if(!Q.front)exit(-1);Q.front->

10、;next=NULL;return 1;int Isempty(LinkQueue Q)if(Q.front=Q.rear)return 1;return 0;int EnQueue(LinkQueue &Q,char e)LinkQueueNode p;p=(LinkQueueNode)malloc(sizeof(QNode);if(!p)exit(-1);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return 1;char DeQueue(LinkQueue &Q,char &e) LinkQue

11、ueNode p;if(Q.front=Q.rear)return 0;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;free(p);return e;5.求魔王語言解釋的偽碼算法：void transmite(stack S) LinkQueue Q; initQueue(Q); char c,e,ch; char A3='s','a','e' char B8='t','s','

12、a','e','d','s','a','e' printf("魔王要說的話是："); while(!IsEmpty(S) pop(S,e); if(e='B') printf("tsaedsae"); else if(e='A') printf("sae"); else if(e='(') while(pop(S,e)&&e!=')') EnQueue(Q,e); pu

13、sh(S,e); DeQueue(Q,c); while(!Isempty(Q) DeQueue(Q,e); push(S,c); push(S,e); push(S,c); while(!IsEmpty(S) pop(S,e); if(e=')')break; else if(e='B')printf("tsaedsae");else if(e='A') printf("sae");else printf("%c",e); else printf("%c",e);

14、printf("n");6.主函數(shù)和其他函數(shù)的算法：void main() bool flag=1; char str,c; while(flag=1) stack S; Initstack(S); char a100; printf("魔王說話了："); int i=0; cin>>a; while(ai)i+; for(int k=i;k>=0;k-) push(S,ak); transmite(S);printf("n是否需要繼續(xù)？是的話請按y: ");scanf("%c",&str

15、);if(str='y')flag=1;else flag=0;c=getchar(); 7調(diào)用函數(shù)關(guān)系圖反映了演示程序的層次結(jié)構(gòu)： main Initiate transmiteInitiate pop push EnQueue DeQueue Isempty四調(diào)試分析1.對&的用法明白了許多。原來有點(diǎn)看不懂標(biāo)識符&，使調(diào)試程序時費(fèi)了我不少的時間。通過本次實(shí)驗(yàn)調(diào)試，讓我明白了&用法。2.函數(shù)調(diào)用。函數(shù)調(diào)用是語言中一塊十分重要部分，它可以把一個程序分成若干部分，然后進(jìn)行配置，所以這塊內(nèi)容一定要學(xué)好。3，棧和隊(duì)列問題比較簡單。4，由于考慮不周，如果同樣的字母出現(xiàn)時，規(guī)則