棧的應(yīng)用表達(dá)式求值

1、（鹽城工學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)） 棧的應(yīng)用表達(dá)式求值數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告棧的應(yīng)用：表達(dá)式求值的設(shè)計(jì)專業(yè)學(xué)生姓名班級(jí)學(xué)號(hào)指導(dǎo)教師徐燕萍完成日期棧的應(yīng)用：表達(dá)式求值的設(shè)計(jì)1設(shè)計(jì)內(nèi)容 .12設(shè)計(jì)分析2.1系統(tǒng)需求分析 .1系統(tǒng)目標(biāo) .1主體功能 .12.2系統(tǒng)概要設(shè)計(jì) 1.系統(tǒng)的功能模塊劃分 .1系統(tǒng)流程圖 23設(shè)計(jì)實(shí)踐3.1基本分析 .33.2中綴表達(dá)式求值 .43.3后綴表達(dá)式求值 .53.4中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式 .64測(cè)試方法4.1基本測(cè)試 .74.2拓展測(cè)試 .74.3容錯(cuò)測(cè)試 .85程序運(yùn)行效果 .76設(shè)計(jì)心得 .8棧的應(yīng)用：表達(dá)式求值的設(shè)計(jì)1 設(shè)計(jì)內(nèi)容設(shè)計(jì)一個(gè)表達(dá)式求值的程序。 該程

2、序必須可以接受包含 （，），+，- ， *，/ , %和八（求幕運(yùn)算符，aAb=ab）的中綴表達(dá)式，并求出結(jié)果。女口 果表達(dá)式正確，則輸出表達(dá)式的結(jié)果；如果表達(dá)式非法，則輸出錯(cuò)誤信 息。2 設(shè)計(jì)分析2.1 系統(tǒng)需求分析2.1.1 系統(tǒng)目標(biāo)利用棧設(shè)計(jì)一個(gè)程序， 該程序能夠用于表達(dá)式求值， 程序?qū)⒆x入的 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后讀取后綴表達(dá)式，輸出結(jié)果。輸入要求：程序從“ input.txt ”文件中讀取信息，在這個(gè)文件中 如果有多個(gè)中綴表達(dá)式， 則每個(gè)表達(dá)式獨(dú)占一行， 程序的讀取操作在文 件的結(jié)尾處停止。輸出要求：對(duì)于每一個(gè)表達(dá)式，將其結(jié)果放在“ output.txt ”文件 的每一行中

3、。這些結(jié)果可能是值（精確到小數(shù)點(diǎn)后兩位） ，也可能是錯(cuò) 誤信息“ ERROR IN INFIX NOTATIO”N。2.1.2 主體功能 能夠處理以字符序列的形式輸入的不含變量的實(shí)數(shù)表達(dá)式，正確處 理負(fù)數(shù)與小數(shù)， 判斷表達(dá)式是否語(yǔ)法正確 （包含分母不能為零的情況） ， 正確實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值， 能夠?qū)⒂?jì)算中遇到的問題 和結(jié)果以文件的形式予以存儲(chǔ)。2.2 系統(tǒng)概要設(shè)計(jì)系統(tǒng)的功能模塊劃分1. 判斷操作數(shù)的函數(shù) isnum（）判斷當(dāng)前所指字符是否屬于數(shù)字，是就返回 1'，不是就返回 0'。2. 求運(yùn)算符優(yōu)先級(jí)函數(shù) priority()為了方便判斷運(yùn)算符優(yōu)先級(jí)， 先利用

4、 switch 函數(shù)將不同的運(yùn)算符返 回不同的整型數(shù)字，在根據(jù)數(shù)字的大小判斷優(yōu)先級(jí)。 +'，- '優(yōu)先級(jí) 相同，返回?cái)?shù)字相同 ，*'，/ '也是。3. 表達(dá)式求值函數(shù) infix_value() 此函數(shù)是直接按照設(shè)計(jì)思路完成問題要求的函數(shù)，其中要調(diào)用到判 斷操作符的函數(shù) isnum() 和求運(yùn)算符優(yōu)先級(jí)的函數(shù) priority() 。循環(huán)結(jié) 束彈出棧 2 的數(shù)值，并返回。4. 主函數(shù) main() 定義一個(gè)數(shù)組存儲(chǔ)表達(dá)式整個(gè)字符串，將返回的數(shù)值直接賦值到浮 點(diǎn)型的 result ，輸出 result 。5. 兩個(gè)棧的函數(shù)設(shè)計(jì)：棧的初始化函數(shù) charInit_S

5、eqStack()Init_SeqStack()棧判空 Empty_SeqStack()char Empty_SeqStack()入棧函數(shù) Push_SeqStack()charPush_SeqStack()出棧函數(shù) Pop_SeqStack()charPop_SeqStack()取棧頂函數(shù) GetTop_SeqStack()charGetTop_SeqStack()銷毀棧 Destory_SeqStack()charDestory_SeqStack()2.2.2 系統(tǒng)流程圖圖1系統(tǒng)流程圖3設(shè)計(jì)實(shí)踐 3.1基本分析在計(jì)算機(jī)中，算術(shù)表達(dá)式的計(jì)算往往是通過使用棧來實(shí)現(xiàn)的。 所以, 本表達(dá)式求值程序

6、的最主要的數(shù)據(jù)結(jié)構(gòu)就是棧。 可以使用棧來存儲(chǔ)輸入 表達(dá)式的操作符和操作數(shù)。輸入的表達(dá)式是由操作數(shù)和運(yùn)算符以及改變運(yùn)算次序的圓括號(hào)連 接而成的式子。表達(dá)式求值是高級(jí)語(yǔ)言編譯中的一個(gè)基本問題，是棧的典型應(yīng)用實(shí)例。任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界 限符(delimiter) 組成的。操作數(shù)既可以是常數(shù)，也可以是被說明為變 量或常量的標(biāo)識(shí)符；運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符二類；基本界限符有左右括號(hào)和表達(dá)式結(jié)束符等。3.2中綴表達(dá)式求值中綴表達(dá)式：每個(gè)二目運(yùn)算符在兩個(gè)運(yùn)算量的中間，假設(shè)操作數(shù)是整型常數(shù)，運(yùn)算符只含加、減、乘、除等四種運(yùn)算符，界

7、限符有左右括 號(hào)和表達(dá)式起始、結(jié)束符“#”， 口：#(7+15)*(23-28/4)#。要對(duì)一個(gè)簡(jiǎn)單的算術(shù)表達(dá)式求值，首先要了解算術(shù)四則運(yùn)算的規(guī)則，即：(1) 從左到右；(2) 先乘除，后加減；(3) 先括號(hào)內(nèi)，后括號(hào)外。運(yùn)算符和界限符可統(tǒng)稱為算符，它們構(gòu)成的集合命名為 OPS根據(jù) 上述三條運(yùn)算規(guī)則，在運(yùn)算過程中，任意兩個(gè)前后相繼出現(xiàn)的算符B1和B 2之間的優(yōu)先關(guān)系必為下面三種關(guān)系之一：e 1<0 2,0 1的優(yōu)先權(quán)低于B 2。仁B 2,0 1的優(yōu)先權(quán)等于0 2。0 1> 0 2,0 1的優(yōu)先權(quán)高于0 2。實(shí)現(xiàn)算符優(yōu)先算法時(shí)需要使用兩個(gè)工作棧：一個(gè)稱作operator ,用以存放運(yùn)

8、算符；另一個(gè)稱作opera nd，用以存放操作數(shù)或運(yùn)算的中間 結(jié)果。算法的基本過程如下：首先初始化操作數(shù)棧opera nd和運(yùn)算符棧operator，并將表達(dá)式 起始符“#”壓入運(yùn)算符棧；依次讀入表達(dá)式中的每個(gè)字符，若是操作數(shù)則直接進(jìn)入操作數(shù)棧 opera nd ,若是運(yùn)算符，則與運(yùn)算符棧operator的棧頂運(yùn)算符進(jìn)行優(yōu)先 權(quán)比較，并做如下處理：(1) 若棧頂運(yùn)算符的優(yōu)先級(jí)低于剛讀入的運(yùn)算符，則讓剛讀入的運(yùn)算符進(jìn)operator棧；(2) 若棧頂運(yùn)算符的優(yōu)先級(jí)高于剛讀入的運(yùn)算符， 則將棧頂運(yùn)算符 退棧，送入0,同時(shí)將操作數(shù)棧opera nd退棧兩次，得到兩個(gè)操作數(shù)a、 b,對(duì)a、b進(jìn)行0運(yùn)算

9、后，將運(yùn)算結(jié)果作為中間結(jié)果推入 opera nd棧；(3) 若棧頂運(yùn)算符的優(yōu)先級(jí)與剛讀入的運(yùn)算符的優(yōu)先級(jí)相同，說明左右括號(hào)相遇，只需將棧頂運(yùn)算符(左括號(hào))退棧即可。operator棧的棧頂元素和當(dāng)前讀入的字符均為“ #”時(shí)，說明表達(dá)式起始符“ #”與 表達(dá)式結(jié)束符“ #”相遇，整個(gè)表達(dá)式求解結(jié)束。int ExpEvaluati on() /*讀入一個(gè)簡(jiǎn)單算術(shù)表達(dá)式并計(jì)算其值。*/In itStack (&opera nd);In itStack(&operator);PushStack(&operator,' #');printf( ” nn Pleas

10、e in put an expressi on (Ending with #): ” );ch二getchar();/*讀入表達(dá)式中的一個(gè)字符*/while(ch!二 #' |GetTop(operator)!二 #') if(!In(ch, OPS)/* 判斷 ch 是否運(yùn)算符 */ a=GetNumber(&ch); /*用ch逐個(gè)讀入操作數(shù)的各位數(shù)碼，并轉(zhuǎn)化為十進(jìn)制數(shù)a */PushStack (&opera nd,a);elseswitch(Compare(GetTop(operator),ch)case' < :PushStack(&am

11、p;operator,ch);ch=getchar();break;case'=:PopStack (&operator，& x);ch=getchar();break;case' > :PopStack(&operator,& op);PopStack(&opera nd, & b);PopStack (&opera nd, & a);v=Execute(a,op,b);PushStack (&opera nd,v);break;v=GetTop(opera nd);return(v);為了處理方便

12、，編譯程序常把中綴表達(dá)式首先轉(zhuǎn)換成等價(jià)的后綴表 達(dá)式，后綴表達(dá)式的運(yùn)算符在運(yùn)算對(duì)象之后。在后綴表達(dá)式中，不再引 入括號(hào)，所有的計(jì)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行，而不用 再考慮運(yùn)算規(guī)則和級(jí)別。中綴表達(dá)式“(a+b*c)-d/e ”的后綴表達(dá)式 為：“ abc*+de/ - ”。3.3后綴表達(dá)式求值計(jì)算一個(gè)后綴表達(dá)式，算法上比計(jì)算一個(gè)中綴表達(dá)式簡(jiǎn)單的多。這是因?yàn)楸磉_(dá)式中即無括號(hào)又無優(yōu)先級(jí)的約束。具體做法：只使用一個(gè)對(duì)象棧，當(dāng)從左向右掃描表達(dá)式時(shí)，每遇到一個(gè)操作數(shù)就送入棧中保存， 每遇到一個(gè)運(yùn)算符就從棧中取出兩個(gè)操作數(shù)進(jìn)行當(dāng)前的計(jì)算，然后把結(jié)果再入棧，直到整個(gè)表達(dá)式結(jié)束，這時(shí)送入棧頂?shù)闹稻褪?/p>

13、結(jié)果。下面是后綴表達(dá)式求值的算法，在下面的算法中假設(shè)，每個(gè)表達(dá)式 是合乎語(yǔ)法的，并且假設(shè)后綴表達(dá)式已被存入一個(gè)足夠大的字符數(shù)組A 中，且以 #'為結(jié)束字符，為了簡(jiǎn)化問題，限定運(yùn)算數(shù)的位數(shù)僅為一 位且忽略了數(shù)字字符串與相對(duì)應(yīng)的數(shù)據(jù)之間的轉(zhuǎn)換問題。double calcul_exp(char *A) /* 本函數(shù)返回由后綴表達(dá)式 A 表示的表 達(dá)式運(yùn)算結(jié)果 */ SeqStarck s;ch=*A+ ; InitStack(s);while(ch!= '#' ) if(ch!= 運(yùn)算符 ) PushStack(s, ch);else PopStack(s, &a);

14、PopStack(s, &b); /* 取出兩個(gè)運(yùn)算量 */ switch(ch) case ch= ' +'： c=a+b; break ; case ch= ' - '： c=a-b; break ; case ch= '* '： c=a*b; break ; case ch= '/ '： c=a/b; break ; case ch= '%'： c=a%b; break ;PushStack (s, c) ;ch=*A+ ;PopStack(s, result) ;return result ;3.4

15、 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式 將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式和前述對(duì)中綴表達(dá)式求值的方法 完全類似， 但只需要運(yùn)算符棧， 遇到運(yùn)算對(duì)象時(shí)直接放后綴表達(dá)式的存 儲(chǔ)區(qū)，假設(shè)中綴表達(dá)式本身合法且在字符數(shù)組 A 中，轉(zhuǎn)換后的后綴表達(dá) 式存儲(chǔ)在字符數(shù)組B中。具體做法：遇到運(yùn)算對(duì)象順序向存儲(chǔ)后綴表達(dá) 式的 B 數(shù)組中存放， 遇到運(yùn)算符時(shí)類似于中綴表達(dá)式求值時(shí)對(duì)運(yùn)算符的 處理過程，但運(yùn)算符出棧后不是進(jìn)行相應(yīng)的運(yùn)算，而是將其送入B中存放。讀者不難寫出算法，在此不在贅述。程序的整體算法分兩步：第一步，從 ”input.txt ”文件中讀取中綴表達(dá)式，并應(yīng)用運(yùn)算符棧 OpHolder 把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，

16、將輸出結(jié)果存放在一個(gè) temp 文件中。第二步，從temp文件中讀取中綴表達(dá)式，并應(yīng)用操作棧Opera nds 計(jì)算后綴表達(dá)式結(jié)果，將結(jié)果輸出到"output.txt ”文件中。4測(cè)試方法設(shè)計(jì)針對(duì)程序的input.txt文件，并將運(yùn)行結(jié)果與期望測(cè)試進(jìn)行比較。5程序運(yùn)行效果5.1基本測(cè)試：在in put文件中輸入表達(dá)式如下圖2：則輸出結(jié)果如下圖3：他謙眾結(jié)構(gòu)課程謨計(jì)俵達(dá)式求值Debuea達(dá)式求Press 呂ny key to continueKi圖45.2擴(kuò)展測(cè)試：在in put文件中輸入表達(dá)式如下圖5:則輸出結(jié)果如下圖6:55.3容錯(cuò)測(cè)試：在in put文件中輸入表達(dá)式如下圖7：則輸

17、出結(jié)果如下圖8 Output-txt記車本 匸叵區(qū)交件屯）扁輯 箱式査看0） 幫肪妁ErnorinInFixnotation.AErrorininFiwnotation.Errorininfixnotation.Errorininfixnotation.ErrorininFixnotation ErrorininFixnotation.Er rorinInfixnotatiofi.ErrorininfiHnotation ErrorininfiKnotation Errorininfixnotation.ErrorininFixnDtatinn.ErrorininfiKnotation Err

18、orininfixnotation Errorininfixnotation.Errorininfixnotat iuii.ErrorininFixnotation.ErrorininFixnotation.|jv6設(shè)計(jì)心得通過此次的課程設(shè)計(jì)，鞏固和加深了我對(duì)棧、隊(duì)列、字符串等理論 知識(shí)的理解；掌握現(xiàn)實(shí)復(fù)雜問題的分析建模和解決方法（；提高利用計(jì) 算機(jī)分析解決綜合性實(shí)際問題的基本能力。在細(xì)節(jié)問題的分析上，較以往有了很大的提高。在尋求最優(yōu)解的問 題上，也能夠找到多種解決方案來使自己的程序收放自如。如，在處理 實(shí)數(shù)的問題上，我采用的是每取得一個(gè)字符，就立刻對(duì)此字符進(jìn)行處理 的方法。其實(shí)，我們可以用一

19、個(gè)字符數(shù)組，來存儲(chǔ)連接著的一系列數(shù)字 字符，然后再通過atof函數(shù)，直接得到字符數(shù)組中所存儲(chǔ)的數(shù)字。再 如，對(duì)負(fù)數(shù)問題的處理上，我最初的想法是通過一個(gè)標(biāo)志mark來記錄前面的字符是否是負(fù)號(hào)（或減號(hào)），再在后面取到除符號(hào)外的數(shù)字時(shí)， 選擇是否添加負(fù)號(hào)。另外，與其他人不同的是，在我的課程設(shè)計(jì)中， Compare （）函數(shù)與其他有著很大的區(qū)別。通常情況下，同學(xué)們參照課 本，都會(huì)采用占用7*7=49個(gè)空間的數(shù)組來分別存儲(chǔ)對(duì)應(yīng)兩個(gè)字符的優(yōu) 先級(jí)符號(hào)，并對(duì)兩個(gè)字符進(jìn)行預(yù)算之后得到數(shù)組中的位置。 雖然 7*7 的 數(shù)組所占的空間并不是非常大， 但在我看來這也是一種浪費(fèi)， 并且空間 的浪費(fèi)并沒有換回時(shí)間一定的

20、節(jié)省。因此，我采用了一種常規(guī)的思路。 將各種運(yùn)算符按照數(shù)學(xué)邏輯上的優(yōu)先順序進(jìn)行排序， 并得到兩個(gè)字符之 間的優(yōu)先級(jí)關(guān)系。這樣一來，我們將不再需要那 7*7 的數(shù)組，且時(shí)間復(fù) 雜度并不大幅增漲。在這個(gè)課程設(shè)計(jì)中，運(yùn)用到的數(shù)據(jù)結(jié)構(gòu)的知識(shí)主要是棧的知識(shí)。棧 在各種軟件系統(tǒng)中，應(yīng)用非常廣泛。棧的的存儲(chǔ)特性 （LIFO 先進(jìn)后出 ）， 使得在用棧來編程時(shí)，思路清晰明了。在使用遞歸算法時(shí)，棧也是一種 很好的選擇。此外，這次的課程設(shè)計(jì)進(jìn)一步加強(qiáng)了我們運(yùn)用 C 語(yǔ)言進(jìn)行編程，調(diào) 試，處理問題的能力，加深了我們對(duì)算法及數(shù)據(jù)結(jié)構(gòu)的認(rèn)識(shí)。同時(shí)我也 意識(shí)到， 開發(fā)程序的早期計(jì)劃要做的充分， 以免出現(xiàn)程序完成后發(fā)現(xiàn)不

21、足而帶來的修改麻煩。 雖然這只是一個(gè)小小的軟件， 但對(duì)我們之后的影 響確實(shí)很大的。7 附：源程序清單#include <stdio.h> #include <stdlib.h>#include <math.h>int PrintError = 0;/* 全局變量， 0代表正常， 1代表表達(dá)式出錯(cuò) */*char 類型鏈表式堆棧，用來存放運(yùn)算符號(hào)，以及用在中綴表達(dá)式轉(zhuǎn)換等時(shí)候 */ typedef struct Node *PtrToNode;typedef PtrToNode Stack;int IsEmpty(Stack S);void MakeEmpty

22、(Stack S);void Push(char X,Stack S);char Top(Stack S);void Pop(Stack S);typedef struct Nodechar Element;PtrToNode Next;/*float 類型鏈表式堆棧，用來存放操作數(shù) */ typedef struct FNode *Ptr_Fn;typedef Ptr_Fn FStack;int FisEmpty(FStack S);void FPush(float X,FStack S);float FTop(FStack S);void FPop(FStack S);typedef st

23、ruct FNodefloat Element;Ptr_Fn Next;void ConvertToPost(FILE *In, Stack Whereat,FILE *Temp); void Reverse(Stack Rev);void Calculate(FILE *Change, Stack Whereat,FILE *Temp);主函數(shù) */* 初始化變量 */*打開文件 */*給Whereat分配空間*/*錯(cuò)誤處理 */*生成Temp文件*/* put back sample 字符 */int main()FILE *InputFile, *OutputFile,*Temp;Sta

24、ck Whereat;char sample;InputFile = fopen("Input.txt","r");OutputFile = fopen("Output.txt","w");Whereat = malloc(sizeof(struct Node);Whereat->Next = NULL;if (!InputFile | !OutputFile) printf("intput or output file(s) do not exist.n"); return(1);sam

25、ple = getc(InputFile);while ( sample != EOF)Temp = fopen("Temp.txt","w+");ungetc(sample,InputFile);ConvertToPost(InputFile,Whereat,Temp);if (PrintError)fprintf(OutputFile,"Error in infix notation.");/*中綴變后綴 */*錯(cuò)誤處理*/fscanf(InputFile,"n",&sample);PrintError

26、 = 0;int IsEmpty(Stack S)return(S->Next=NULL);else if (IsEmpty(Whereat) = 1)*/else if (IsEmpty(Whereat) != 1) Reverse(Whereat); if (Top(Whereat) = 'B')PrintError = 1;操作數(shù)而不是運(yùn)算符號(hào) */ fclose(Temp); Temp = fopen("Temp.txt","r+"); Calculate(OutputFile, Whereat,Temp); fclose(

27、Temp);MakeEmpty(Whereat); putc('n',OutputFile); sample = getc(InputFile);free(Whereat); fclose(InputFile); fclose(OutputFile); remove("Temp.txt");return 1;/*跳過在in put文件中的空格/*錯(cuò)誤處理， */*A表示操作數(shù)B表示運(yùn)算符*/* 后綴表達(dá)式第一個(gè)元素應(yīng)是/*計(jì)算結(jié)果 */*清空Whereat用來處理下一行*/* 在輸出文件中換行 */* While 循環(huán)結(jié)束 */* 刪除 Temp.txt*/

28、檢查堆棧是否為空 */* 檢查 float 堆棧是否為空 */ int FIsEmpty(FStack S)return(S->Next=NULL);彈出棧頂元素 */void Pop(Stack S)PtrToNode FirstCell;if (IsEmpty(S)perror("Empty Stack"); elseFirstCell = S->Next;S->Next = S->Next->Next; free(FirstCell);/* 彈出 float 棧頂元素 */void FPop(FStack S) Ptr_Fn FirstC

29、ell;FirstCell = S->Next;S->Next = S->Next->Next; free(FirstCell);if (FIsEmpty(S) perror("Empty Stack");else/*將堆棧置空 */void MakeEmpty(Stack S)if (S = NULL)perror("Must use Createstack first"); elsewhile (!IsEmpty(S) Pop(S);將float堆棧置空*/void FMakeEmpty(FStack S)if (S = NU

30、LL)perror("Must use Createstack first"); elsewhile (!IsEmpty(S) Pop(S);元素進(jìn)棧 */void Push(char X, Stack S)PtrToNode TmpCell;TmpCell = (PtrToNode)malloc(sizeof(struct Node); if (TmpCell = NULL) perror("Out of Space!");else TmpCell->Element = X; TmpCell->Next = S->Next; S-&g

31、t;Next = TmpCell;/*元素進(jìn)棧 */void FPush(float X, FStack S)Ptr_Fn TmpCell;TmpCell = (Ptr_Fn)malloc(sizeof(struct FNode); if (TmpCell = NULL)perror("Out of Space!");elseTmpCell->Element = X; TmpCell->Next = S->Next; S->Next = TmpCell;返回棧頂元素 */char Top(Stack S) if (!IsEmpty(S)return

32、S->Next->Element;perror("Empty Stack");exit(1);return 0;/* 返回 float 棧頂元素 */float FTop(FStack S)if (!FIsEmpty(S)return S->Next->Element;perror("Empty Stack");exit(1);return 0;/* 將堆棧元素倒置 */void Reverse(Stack Rev)Stack Tempstack;Tempstack = malloc(sizeof(struct Node);Tem

33、pstack->Next = NULL;while (!IsEmpty(Rev)Push(Top(Rev),Tempstack); /* 將元素壓棧到一個(gè)臨時(shí)堆棧 */ Pop(Rev);Rev->Next = Tempstack->Next; /* 指向新的堆棧 */*Whereat 說明 :Whereat 記錄了操作數(shù)和運(yùn)算符號(hào)的位置，用A 和 B 區(qū)分。 A = operand, B =operator.(例如1+2轉(zhuǎn)換成12+,在whereat中的形式應(yīng)該是 AAB)OpHolder 說明 :Char 類型的堆棧 Opholder 用來保存運(yùn)算符號(hào)。*/* 將中綴表帶

34、式轉(zhuǎn)換為后綴表達(dá)式 */void ConvertToPost(FILE *In, Stack Whereat, FILE *Temp)Stack OpHolder;char holder;char lastseen;int digitcounter = 0; /* 操作數(shù)的計(jì)數(shù)器 */OpHolder = malloc(sizeof(struct Node); /*初始化 */OpHolder->Next = NULL;holder=getc(In);lastseen = '' /* 用來防止輸入格式錯(cuò)誤，例如兩個(gè)小數(shù)點(diǎn)*/putc(' ',Temp);w

35、hile (holder !='n') && (holder != EOF)if (holder = ' ')digitcounter = 0;else if ( IsOperator(holder) = -1)/* 如果 holder不是操作數(shù)或運(yùn)算符號(hào)*/PrintError = 1;else if (IsOperator(holder)=0)if (lastseen = holder) && (lastseen = '.')/*錯(cuò)誤處理 */PrintError = 1;elselastseen = hold

36、er;if (digitcounter = 0)Push('A',Whereat);/*進(jìn)棧*/digitcounter+;/*計(jì)數(shù)器加一 */putc(' ',Temp);putc(holder,Temp);elsedigitcounter = 0;if (lastseen = holder) && (lastseen != '(') && (lastseen != ')')/*"("情況特殊對(duì)待 */PrintError = 1;elselastseen = holder;i

37、f(lsEmpty(OpHolder)=1)/* 當(dāng) OpHolder 為空*/Push(holder,OpHolder);else if(OperatorValue(Top(OpHolder) 況*/if(OperatorValue(holder)=5) Pop(OpHolder);elsePush(holder,OpHolder);else if(OperatorValue(holder) = 6)Push(holder,OpHolder);else if(OperatorValue(holder) = 5) 況*/while (IsEmpty(OpHolder) (OperatorVal

38、ue(Top(OpHolder) != 6)putc(' ',Temp);Push('B',Whereat); putc(Top(OpHolder),Temp); Pop(OpHolder);if (IsEmpty(OpHolder) = 1)= 6) /*OpHolder 是"(" 的情/* OpHolder 是" )" 的情!= 1) &&/*錯(cuò)誤處理,括號(hào)不匹配 */PrintError = 1; elsePop(OpHolder);else if(OperatorValue(holder) = Op

39、eratorValue(Top(OpHolder)&& (OperatorValue(holder) = 3)/* 冪運(yùn)算情況 */Push(holder,OpHolder);else if(OperatorValue(holder) < OperatorValue(Top(OpHolder)&& OperatorValue(Top(OpHolder) = 3)/* 冪運(yùn)算情況 */putc(' ',Temp);Push('B',Whereat); putc(Top(OpHolder),Temp);Pop(OpHolder)

40、;while(IsEmpty(OpHolder) != 1) && (OperatorValue(Top(OpHolder) = 3)Push('B',Whereat); putc(' ',Temp); putc(Top(OpHolder),Temp);Pop(OpHolder); Push(holder,OpHolder);/*如果當(dāng)前運(yùn)算符號(hào)的優(yōu)先級(jí)小于或者等于堆棧中的運(yùn)算符號(hào)的優(yōu)先級(jí),則將其放入temp中，并且將堆棧中的運(yùn)算符號(hào)出棧，放入temp中，直到堆棧為空或者優(yōu)先級(jí)小于堆棧頂元素的優(yōu)先級(jí)*/else if(OperatorValue(

41、Top(OpHolder) >= OperatorValue(holder)while(IsEmpty(OpHolder) != 1)&&(OperatorValue(Top(OpHolder)>=OperatorValue(holder)&& (OperatorValue(Top(OpHolder)!=6)putc(' ',Temp); putc(Top(OpHolder),Temp); Push('B',Whereat); Pop(OpHolder);Push(holder,OpHolder);else if(Op

42、eratorValue(Top(OpHolder) < OperatorValue(holder)/*如果當(dāng)前運(yùn)算符號(hào)的優(yōu)先級(jí)大于堆棧中的運(yùn)算符號(hào)的優(yōu)先級(jí),則將其壓入堆棧中*/Push(holder,OpHolder);holder=getc(In);/* While 循環(huán)結(jié)束 */while(IsEmpty(OpHolder)!=1)/*最后如果堆棧中還有運(yùn)算符號(hào)，則一并放到temp中*/Push('B',Whereat);putc(' ',Temp); putc(Top(OpHolder),Temp);Pop(OpHolder);MakeEmpty(O

43、pHolder);free(OpHolder);/* 判斷類型， 1為運(yùn)算符號(hào)， 0為操作數(shù)， -1為錯(cuò)誤 */int IsOperator(char ToCompare)if (ToCompare = '(' | ToCompare = ')'| ToCompare = '+' | ToCompare =I I| ToCompare = '*'| ToCompare = '/'| ToCompare = 'A'| ToCompare= '%')return 1;else if (T

44、oCompare = '1' | ToCompare = '2'| ToCompare = '3'| ToCompare = '4' | ToCompare = '5'| ToCompare = '6'| ToCompare = '7'| ToCompare = '8' | ToCompare = '9'| ToCompare = '0'| ToCompare = '.')return 0;elsereturn -1;/

45、* 返回運(yùn)算符號(hào)的優(yōu)先級(jí) */int OperatorValue(char ValueToGive)if (ValueToGive = '(')return 6;if (ValueToGive = return 5;= ')')if (ValueToGive ='A')return 3;if (ValueToGive = '%')return 2;if (ValueToGive = '*')return 2;if (ValueToGive = '/')return 2;if (ValueToGive

46、 = '+')return 1;if (ValueToGive = '-')return 1;return 0;/* 計(jì)算后綴表達(dá)式 */void Calculate(FILE *Change, Stack Whereat, FILE *Temp)FStack Operands;float looker;char Op;char spacefinder;float answer = 0;float NumA;float NumB;Operands = (Ptr_Fn)malloc(sizeof(struct FNode);Operands->Next= N

47、ULL;while (IsEmpty(Whereat) != 1) && PrintError != 1) /* 循環(huán)直到 Whereat 空，或者遇到錯(cuò) 誤*/if (Top(Whereat) = 'A') fscanf(Temp," ",&spacefinder);fscanf(Temp,"%f",&looker);/*如果是 A,則是操作數(shù) */FPush(looker,Operands);Pop(Whereat);else if (Top(Whereat) = 'B')fscanf(

48、Temp," ",&spacefinder);/*如果是B,則是運(yùn)算符*/Op = getc(Temp);switch(Op) /*判斷是什么運(yùn)算符 */caseD：/*冪運(yùn)算*/NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands)/*錯(cuò)誤處理 */PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);if (NumA = 0 && NumB < 0)|(NumA<0) && (NumB - (int)NumB != 0) PrintError = 1;elseanswer = pow(Nu