中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式報告

1、目錄1.課題分析111設(shè)計目的112主要內(nèi)容1121中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式1122后綴表達(dá)式求值213設(shè)計要求22.總體設(shè)計221數(shù)據(jù)類型的定義222主程序的流程33詳細(xì)設(shè)計（源代碼）54調(diào)試分析1441問題11442問題21543問題3155測試結(jié)果156心得體會167參考文獻(xiàn)161. 課題分析11設(shè)計目的（1）掌握?！昂筮M(jìn)先出”的特點(diǎn)。（2）掌握棧的典型應(yīng)用中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，并利用后綴表達(dá)式求值。（3）掌握串或者數(shù)組的相關(guān)操作。12主要內(nèi)容121中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式（1）定義一個運(yùn)算符棧，并輸入一個中綴表達(dá)式（運(yùn)算對象存在多位整數(shù)，運(yùn)算符為+、-、*、/、%及括號），然后從

2、中綴表達(dá)式中自左至右依次讀入各個字符。（2）如果是第一次讀入運(yùn)算對象，也是直接輸出到后綴表達(dá)式；如果不是第一次讀入運(yùn)算對象，并且前一個讀入的字符是運(yùn)算對象，也是直接輸出到后綴表達(dá)式；如果不是第一次讀入運(yùn)算對象，并且前一個讀入的字符是運(yùn)算符，則先輸出逗號作為分隔符，然后再將該運(yùn)算對象輸出到后綴表達(dá)式。（3）如果讀入的是運(yùn)算符，并且運(yùn)算符棧為空，則將該運(yùn)算符直接進(jìn)棧；如果棧不為空，則比較該運(yùn)算符和棧頂運(yùn)算符的優(yōu)先級。 若該運(yùn)算符高于棧頂運(yùn)算符的優(yōu)先級，則將該運(yùn)算符直接進(jìn)棧；若該運(yùn)算符低于或等于棧頂運(yùn)算符的優(yōu)先級，則將棧中高于或等于該運(yùn)算符優(yōu)先級的元素依次出棧，然后再將該運(yùn)算符進(jìn)棧。每出棧一個運(yùn)算符

3、時，先輸出一個逗號到后綴表達(dá)式作為分隔符，然后再將出棧運(yùn)算符輸出到后綴表達(dá)式。（4）如果讀入的是開括號“（”，則直接進(jìn)棧；如果讀入的是閉括號“）”，則一直出棧并輸出到后綴表達(dá)式，知道遇到一個開括號“（”為止。開括號“（”和閉括號“）”均不輸出到后綴表達(dá)式。（5）重復(fù)、步，知道中綴表達(dá)式結(jié)束，然后將棧中剩余的所有運(yùn)算符依次出棧。每出棧一個運(yùn)算符時，先輸出一個逗號到后綴表達(dá)式作為分隔符，然后再將出棧運(yùn)算符輸出到后綴表達(dá)式。（6）給后綴表達(dá)式加上0作為字符串結(jié)束標(biāo)志。122后綴表達(dá)式求值（1）定義一個double型的運(yùn)算數(shù)棧，將中綴表達(dá)式轉(zhuǎn)換得到的后綴表達(dá)式字符串自左向右依次讀入。（2）如果讀入的是

4、運(yùn)算對象，則將該運(yùn)算對象串（下一個逗號分隔符前的部分所構(gòu)成的數(shù)字字符串）轉(zhuǎn)換為對應(yīng)的多位整數(shù)值，然后將該整數(shù)值（將自動類型轉(zhuǎn)換為double型）直接進(jìn)入運(yùn)算數(shù)棧。（3）如果讀入的是運(yùn)算符，則立即從運(yùn)算數(shù)棧中彈出兩個運(yùn)算數(shù)，計算兩個運(yùn)算數(shù)運(yùn)算后的值（運(yùn)算時先出棧的元素放在運(yùn)算符后面，后出棧的元素放在運(yùn)算符前面），并將計算結(jié)果存回運(yùn)算數(shù)棧。（4）重復(fù)、步，直到后綴表達(dá)式結(jié)束，最后棧中保存的那個數(shù)即為該后綴表達(dá)式的計算結(jié)果。（5）和手工計算的結(jié)果進(jìn)行比較，檢驗(yàn)程序運(yùn)行結(jié)果的正確性。假設(shè)輸入中綴表達(dá)式為：（123+32）/5*2-15*18/（2+4）/15-7。轉(zhuǎn)換后的后綴表達(dá)式為：123，32，+

5、，5，/，2，*，15，18，*，2，4，+，/，15，/，-，7，-。后綴表達(dá)式求得的值為：52。13設(shè)計要求（1）運(yùn)算對象存在多位整數(shù)。（2）遇到除數(shù)為0的情況，應(yīng)能給出相應(yīng)提示，并提醒重新輸入中綴表達(dá)式。（3）%運(yùn)算符左右遇到非整數(shù)時，應(yīng)能自動對其進(jìn)行取整；%運(yùn)算符左右遇到負(fù)數(shù)時，應(yīng)能給出相應(yīng)提示，并提醒重新輸入中綴表達(dá)式。（4）如果有兩個同學(xué)同時完成該課題，要求分別采用順序和鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)其棧。2.總體設(shè)計21數(shù)據(jù)類型的定義calcolate（）：依次掃描string2中的字符，遇到數(shù)字則將其轉(zhuǎn)化為整型數(shù)據(jù)存入棧中，遇運(yùn)算符則將棧中棧頂?shù)膬蓚€元素取出參與運(yùn)算，并將計算結(jié)果放入棧中，如此直

6、到運(yùn)算符全部用完，最后一次運(yùn)算結(jié)果即為后綴表達(dá)式的計算結(jié)果。end輸出運(yùn)算結(jié)果后綴表達(dá)式結(jié)果的計算calcolate（）String2中存放轉(zhuǎn)化好的后綴表達(dá)式zi+先向string2中存入一個空格，再判斷該字符類型。為減價乘除號，判斷棧頂元素優(yōu)先級，比其高，先將棧頂元素出棧到string2 中，再將其入棧。為開闊號，直接進(jìn)棧。為閉括號，將棧頂元素依次彈出存入string2 中，直至遇到開闊號。直接存入字符串string2中String1i是否為數(shù)字string1i?=0;讀入字符串string1,i=0start22主程序的流程 先把算術(shù)表達(dá)式轉(zhuǎn)化成后綴表達(dá)式，在對后綴表達(dá)式進(jìn)行計算。首先建立

7、一個符號棧，用于存放字符和字符的優(yōu)先級別；然后在建立一個數(shù)棧，用于輔助后綴表達(dá)式的計算；最后在定義一個字符串?dāng)?shù)組，用于存放后綴表達(dá)式。建立一個計算的函數(shù)，該函數(shù)用于兩個數(shù)的計算，在調(diào)用這個函數(shù)的時候，傳入三個參數(shù)，兩個浮點(diǎn)型參數(shù)和一個字符型參數(shù)，根據(jù)不同的符號進(jìn)行不同的計算。定義一個判斷優(yōu)先級別的函數(shù)，用于判斷兩個操作符的優(yōu)先級別，在根據(jù)優(yōu)先級的不同決定不同的操作。后綴表達(dá)式的取得，對算術(shù)表達(dá)式字符串進(jìn)行挨個的掃描，如果是數(shù)字或者是小數(shù)點(diǎn)，則將數(shù)字或者小數(shù)點(diǎn)存放到字符數(shù)組中，每取完一個數(shù)字，則在后面用“|”隔開，如果是操作符，則和棧中得操作符進(jìn)行比較，若掃描到的符號優(yōu)先級比棧里的符號優(yōu)先級低，

8、則棧中元素出棧并存放到字符數(shù)組中。每出一個字符到字符數(shù)組中就在后面加“|”分隔。繼續(xù)檢查棧頂比較優(yōu)先級，直到棧中元素優(yōu)先級比掃描到的符號優(yōu)先級低或者符號棧為空，則將此操作符入棧。若是“（”則無條件入字符棧，若是“）”則從字符棧中出字符直到遇到“（”為止。當(dāng)字符數(shù)組掃描到最后的時候，計算并沒有結(jié)束。然后得進(jìn)行字符棧的判斷，看是否已經(jīng)為空棧，若不是空棧，則出棧字符，將字符存放到數(shù)組中。最后字符串?dāng)?shù)組中存放的就是后綴表達(dá)式。得到后綴表達(dá)式后，要用數(shù)棧進(jìn)行后綴表達(dá)式的計算，后綴表達(dá)式的計算中，對新的數(shù)組進(jìn)行從道到尾的掃描，如果遇到數(shù)字，以“|”為標(biāo)記取出完整的操作數(shù)，用輔助數(shù)組存放，然后轉(zhuǎn)化成浮點(diǎn)數(shù)存

9、放到數(shù)棧中，遇到“|”則直接將數(shù)組下標(biāo)往后走。遇到字符，則從數(shù)棧取出兩個數(shù)進(jìn)行計算，將計算的結(jié)果從新存放到數(shù)棧中，循環(huán)直到接到結(jié)束。最后存放在數(shù)棧中的數(shù)就是計算的結(jié)果。最后在主函數(shù)中調(diào)用此函數(shù)，進(jìn)行結(jié)果的輸出。3詳細(xì)設(shè)計（源代碼）#include#include#include#include#define MAX 60#define DEMAX 15#define NULL 0char string1MAX;char string2MAX;int j=0;struct node char data;int num;struct node *next;struct node *Initiali

10、zation()/初始化棧鏈,鏈棧不帶頭結(jié)點(diǎn)struct node *top;top=(struct node *)malloc(sizeof(struct node);top-data=;top-num=0;top-next=NULL;return top;struct node *assort(struct node *s)/輸入字符串struct node *p,*top;int i;top=s;int m;char a;gets(string1);m=strlen(string1); for(i=0;i=m;i+)a=string1i;if(0=string1i&string1idat

11、a=a;p-next=top; top=p; break; case *: case /:string2j= ;j+;if(top-data=*)|(top-data=/)string2j=top-data;j+; /比其高，現(xiàn)將棧頂運(yùn)算符出棧，再進(jìn)棧。top-data=a;break;elsep=(struct node *)malloc(sizeof(struct node);/否，直接進(jìn)棧p-data=a;p-next=top;top=p;break; case +: case -:string2j= ;j+;if(top-data=+|top-data=-|top-data=*|top

12、-data=/)string2j=top-data;j+;top-data=a;break;else p=(struct node *)malloc(sizeof(struct node);p-data=a;p-next=top;top=p;break; case ):string2j= ;j+;if(top-data=)printf(input error);break;while(top-data!=()string2j=top-data;j+;p=top;top=top-next;free(p); p=top;top=top-next;free(p);break;while(top-da

13、ta!=)string2j=top-data;j+;p=top;top=top-next;free(p);string2j=#; printf(轉(zhuǎn)化后的后綴表達(dá)式為:%sn,string2);return top;struct node *calcolate(struct node *s)struct node *top,*p;char *q;int x,y,a;int i,n;top=s;/指向棧頂?shù)闹羔榝or(i=0;i=0&string2i=0&string2nnum=a;p-next=top;top=p;i=n-1;elseif(string2i=#) /遇#號結(jié)束標(biāo)志，輸出棧中的最后

14、計算結(jié)果printf(計算結(jié)果為:%dn,top-num);elseif(string2i= )elsey=top-num;p=top;top=top-next;free(p);x=top-num;p=top;top=top-next;free(p);switch(string2i)case +:a=x+y; p=(struct node *)malloc(sizeof(struct node); p-num=a;p-next=top;top=p; break; case -:a=x-y; p=(struct node *)malloc(sizeof(struct node ); p-num=

15、a;p-next=top;top=p; break; case *:a=x*y; p=(struct node *)malloc(sizeof(struct node ); p-num=a;p-next=top;top=p; break; case /:a=(float)x/y; p=(struct node *)malloc(sizeof(struct node ); p-num=a;p-next=top;top=p; break;return 0;main()struct node *top,*head;int m;top=Initialization();/建立一個鏈棧，并返回棧頂指針p

16、rintf(請輸入表達(dá)式：);head=assort(top);/中綴轉(zhuǎn)化為后綴表達(dá)式calcolate(head);/后綴表達(dá)式的計算4調(diào)試分析41問題1l 從字符數(shù)組中截取出數(shù)字的操作，并轉(zhuǎn)化成浮點(diǎn)型的數(shù)不正確。計算的結(jié)果有時候是一個意想不到的很大的數(shù)。解決方法：從字符數(shù)數(shù)組中將數(shù)字截取出來就是為了能進(jìn)行計算，而數(shù)字是單個字符的形式存在，必須把一個完整的數(shù)從算術(shù)表達(dá)式中截取出來，如果遇到數(shù)字的字符就是一個數(shù)字的入口，然后循環(huán)取出直到遇到不是數(shù)字或者小數(shù)點(diǎn)為止。而這些取出的數(shù)字是一堆離散的數(shù)字字符。這時候就需要建立一個輔助的數(shù)組來存放這些數(shù)字字符以組成一個數(shù)字的字符。用一個輔助的索引將數(shù)字的

17、組成字符一個一個從數(shù)組中取出來，存放到新的數(shù)組中，以得到一個字符串的數(shù)字。從數(shù)組中截取出一個數(shù)后，將取出的數(shù)用atof 函數(shù)進(jìn)行轉(zhuǎn)化成浮點(diǎn)型的數(shù)。在把浮點(diǎn)型的數(shù)存放到數(shù)棧中，在后面的計算中取出。在調(diào)試中第一個取出的浮點(diǎn)型數(shù)是正確的，當(dāng)遇到后面截取的數(shù)的長度比第一個數(shù)短的時候，發(fā)現(xiàn)取出的數(shù)和第一個數(shù)的位數(shù)相同了。經(jīng)過分析，每次截取完數(shù)字后并沒有對輔助數(shù)組進(jìn)行重新的初始化，數(shù)組中宗存放著前一個字符，一旦遇到數(shù)字比前面的數(shù)字短的的情況，后面的數(shù)字只覆蓋了前面的數(shù)字的前幾位，后面的幾位都是原先的數(shù)字。造成取出的結(jié)果是錯誤的。解決問題的方法可以在每次存放數(shù)字之前，把輔助數(shù)組進(jìn)行初始化，結(jié)果能正確計算表達(dá)

18、式。42問題2l 如何生成后綴表達(dá)式，將數(shù)與字符存放在一個字符串中。解決方法：想把數(shù)字從字符數(shù)組中取出來，然后再存入后綴表達(dá)式中，從字符數(shù)組中取出是很容易的，但是在把這些數(shù)字和操作符進(jìn)行存入一個后綴表達(dá)式數(shù)的時候出現(xiàn)了問題，因?yàn)閏 語言中沒有這樣的字符數(shù)組，所以取出的數(shù)字根本沒法和操作符一塊存到一個數(shù)組中去。改變一種想問題的方法，就是不把字符數(shù)組的數(shù)字都截取出來，而是把數(shù)字進(jìn)行一個分割，讓數(shù)字還依舊存放在數(shù)組中，只是在每個數(shù)字的后面都加上一個分割符號“|”，然后要是遇到操作符也將操作符存放到這個數(shù)組中并且也加入分隔符，這樣就組成了一個全新的數(shù)組，也即是后綴表達(dá)式。這里的修改是遇到數(shù)字，邊走邊存

19、，一個數(shù)字取完后就在數(shù)字的后面加分隔符。如果是操作符，則進(jìn)行優(yōu)先級的判斷，根據(jù)判斷的結(jié)果把操作符加入到數(shù)組中，以生成后綴表達(dá)式。對新生成的后綴表達(dá)式數(shù)組在進(jìn)行計算，在后綴表達(dá)式中將數(shù)字截取出來，這樣子做的效果比原先就截取出來好實(shí)現(xiàn)。通過掃面后綴表達(dá)式，根據(jù)分隔符可以很簡單的就截取出一個數(shù)字字符串，再把字符串?dāng)?shù)字轉(zhuǎn)化成浮點(diǎn)數(shù)存放到數(shù)棧中，遇到操作符就計算，從數(shù)棧中取出兩個數(shù)字，連同操作一起調(diào)用函數(shù)進(jìn)行計算。循環(huán)掃描，直到掃描到“0”，最后將結(jié)果從數(shù)棧中取出作為結(jié)果返回給主函數(shù)。43問題3l 問題3：如何解決除數(shù)是零的問題解決方法：在進(jìn)行除法運(yùn)算的時候，遇到除數(shù)為 0 的情況肯定是特殊處理的，但是該如何讓程序在遇到這個問題的時候退出程序，并輸出提示錯