魔王語言解釋

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

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

3、ezegexeneietsaedsae                                           若將小寫字母與漢字建立下表所示的對應關系，則魔王說的話是“天上一個鵝地上一個鵝     鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一個鵝地上一個鵝?！?    t d s a e z G x n i     天 地 上 一

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

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

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

7、塊實現棧的抽象數據類型；3） 隊列模塊實現隊列的抽象數據類型。4） 魔王語言解釋模塊定義線性表的結點結構。各模塊的之間的調用關系如下： 主程序模塊 魔王語言解釋模塊     棧模塊隊列模塊三、 詳細設計1. 站類型typedef structchar *base;char *top;int stacksize;stack;2. 隊列類型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隊列的基本操作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.求魔王語言解釋的偽碼算法：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("魔王要說的話是："); 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.主函數和其他函數的算法：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調用函數關系圖反映了演示程序的層次結構： main Initiate transmiteInitiate pop push EnQueue DeQueue Isempty四調試分析1.對&的用法明白了許多。原來有點看不懂標識符&，使調試程序時費了我不少的時間。通過本次實驗調試，讓我明白了&用法。2.函數調用。函數調用是語言中一塊十分重要部分，它可以把一個程序分成若干部分，然后進行配置，所以這塊內容一定要學好。3，棧和隊列問題比較簡單。4，由于考慮不周，如果同樣的字母出現時，