魔王語(yǔ)言解釋

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

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

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

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

5、iD,I=1，2，.，n 基本操作： ListInitiate (&S) 操作結(jié)果：構(gòu)造一個(gè)空棧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ù)類(lèi)型定義為：ADTQueue 數(shù)據(jù)對(duì)象：D=ai | aiElemSet，I=1，2，.，n,n0 數(shù)據(jù)關(guān)系：R1=< ai-1，ai

6、 > |ai-1，aiD,I=1，2，.，n 基本操作： ListInitiate (&Q) 操作結(jié)果：構(gòu)造一個(gè)空隊(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的對(duì)頭元素，并以e返回其值。 ADT Queue2. 程序包含四個(gè)模塊：1） 主程序模塊：Void main()初始化；For（）接受處理命令；接受處理；2） 棧模

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

8、r;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.stac

9、ksize+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) LinkQueu

11、eNode 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.求魔王語(yǔ)言解釋的偽碼算法：void transmite(stack S) LinkQueue Q; initQueue(Q); char c,e,ch; char A3='s','a','e' char B8='t','s','a

12、','e','d','s','a','e' printf("魔王要說(shuō)的話是："); 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); pus

13、h(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); p

14、rintf("n");6.主函數(shù)和其他函數(shù)的算法：void main() bool flag=1; char str,c; while(flag=1) stack S; Initstack(S); char a100; printf("魔王說(shuō)話了："); int i=0; cin>>a; while(ai)i+; for(int k=i;k>=0;k-) push(S,ak); transmite(S);printf("n是否需要繼續(xù)？是的話請(qǐng)按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.對(duì)&的用法明白了許多。原來(lái)有點(diǎn)看不懂標(biāo)識(shí)符&，使調(diào)試程序時(shí)費(fèi)了我不少的時(shí)間。通過(guò)本次實(shí)驗(yàn)調(diào)試，讓我明白了&用法。2.函數(shù)調(diào)用。函數(shù)調(diào)用是語(yǔ)言中一塊十分重要部分，它可以把一個(gè)程序分成若干部分，然后進(jìn)行配置，所以這塊內(nèi)容一定要學(xué)好。3，棧和隊(duì)列問(wèn)題比較簡(jiǎn)單。4，由于考慮不周，如果同樣的字母出現(xiàn)時(shí)，