(鹽城工學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)方案)棧的應(yīng)用表達(dá)式求值

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告棧的應(yīng)用：表達(dá)式求值的設(shè)計(jì)專(zhuān)業(yè)學(xué)生姓名班級(jí)學(xué)號(hào)指導(dǎo)教師徐燕萍完成日期目錄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ì)心得 .87附錄：源代碼 .10棧的應(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)需求分析系統(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 ”文件 的每一行中。這些結(jié)果可能是值（精確到小數(shù)點(diǎn)后兩位） ，也可能是錯(cuò) 誤信息“ ERROR IN

3、 INFIX NOTATION主體功能能夠處理以字符序列的形式輸入的不含變量的實(shí)數(shù)表達(dá)式，正確處 理負(fù)數(shù)與小數(shù)，判斷表達(dá)式是否語(yǔ)法正確（包含分母不能為零的情況）， 正確實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，能夠?qū)⒂?jì)算中遇到的問(wèn)題和結(jié)果以文件的形式予以存儲(chǔ)。2.2系統(tǒng)概要設(shè)計(jì)系統(tǒng)的功能模塊劃分1. 判斷操作數(shù)的函數(shù)isnum（）判斷當(dāng)前所指字符是否屬于數(shù)字,是就返回1不是就返回02. 求運(yùn)算符優(yōu)先級(jí)函數(shù)priority。為了方便判斷運(yùn)算符優(yōu)先級(jí)，先利用switch函數(shù)將不同的運(yùn)算符返 回不同的整型數(shù)字，在根據(jù)數(shù)字的大小判斷優(yōu)先級(jí)。 + -優(yōu)先級(jí)相同，返回?cái)?shù)字相同，* /也是。3. 表達(dá)式求值函數(shù)i

4、nfix_value()此函數(shù)是直接按照設(shè)計(jì)思路完成問(wèn)題要求的函數(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ù)charlnit_SeqStack()Ini t_SeqStack()棧判空Empty_SeqStack()char Empty_SeqStack()入棧函數(shù)Push_SeqStack()charPush_SeqStack()出棧函數(shù)Pop_SeqStac

5、k()charPop_SeqStack()取棧頂函數(shù)GetTop_SeqStack()charGetTop_SeqStack()銷(xiāo)毀棧 Destory_SeqStack()charDestory_SeqStack()系統(tǒng)流程圖3設(shè)計(jì)實(shí)踐 3.1基本分析在計(jì)算機(jī)中，算術(shù)表達(dá)式的計(jì)算往往是通過(guò)使用棧來(lái)實(shí)現(xiàn)的。 所以, 本表達(dá)式求值程序的最主要的數(shù)據(jù)結(jié)構(gòu)就是棧。 可以使用棧來(lái)存儲(chǔ)輸入 表達(dá)式的操作符和操作數(shù)。輸入的表達(dá)式是由操作數(shù)和運(yùn)算符以及改變運(yùn)算次序的圓括號(hào)連 接而成的式子。表達(dá)式求值是高級(jí)語(yǔ)言編譯中的一個(gè)基本問(wèn)題，是棧的典型應(yīng)用實(shí)例。任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(ope

6、rator)和界 限符(delimiter) 組成的。操作數(shù)既可以是常數(shù)，也可以是被說(shuō)明為變 量或常量的標(biāo)識(shí)符；運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn) 算符三類(lèi)；基本界限符有左右括號(hào)和表達(dá)式結(jié)束符等。3.2中綴表達(dá)式求值中綴表達(dá)式：每個(gè)二目運(yùn)算符在兩個(gè)運(yùn)算量的中間，假設(shè)操作數(shù)是 整型常數(shù)，運(yùn)算符只含加、減、乘、除等四種運(yùn)算符，界限符有左右括 號(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)稱(chēng)為算符，它們構(gòu)成的集

7、合命名為 OPS根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算過(guò)程中，任意兩個(gè)前后相繼出現(xiàn)的算符01和0 2之間的優(yōu)先關(guān)系必為下面三種關(guān)系之一：0 1 0 2, 0 1的優(yōu)先權(quán)高于0 2。實(shí)現(xiàn)算符優(yōu)先算法時(shí)需要使用兩個(gè)工作棧：一個(gè)稱(chēng)作operator ,用 以存放運(yùn)算符；另一個(gè)稱(chēng)作opera nd，用以存放操作數(shù)或運(yùn)算的中間結(jié) 果。算法的基本過(guò)程如下：首先初始化操作數(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)比較，并做如下處理：(

8、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)算后，將運(yùn)算結(jié)果作為中間結(jié)果推入 opera nd棧;(3) 若棧頂運(yùn)算符的優(yōu)先級(jí)與剛讀入的運(yùn)算符的優(yōu)先級(jí)相同， 說(shuō)明 左右括號(hào)相遇，只需將棧頂運(yùn)算符(左括號(hào))退棧即可。 operator棧的 棧頂元素和當(dāng)前讀入的字符均為“ #”時(shí)，說(shuō)明表達(dá)式起始符“ #”與表 達(dá)式結(jié)束符“ #”相遇，整個(gè)表達(dá)式求解結(jié)束。int ExpEvaluati on() /

9、*讀入一個(gè)簡(jiǎn)單算術(shù)表達(dá)式并計(jì)算其值。*/In itStack (&opera nd);In itStack(&operator);PushStack(&operator, #);printf( ” nn Please 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 */Pus

10、hStack (&opera nd,a);elseswitch(Compare(GetTop(operator),ch)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);為了處理方便，編譯程序常把中綴表達(dá)式首先轉(zhuǎn)換成等價(jià)的后綴表 達(dá)式，后綴表達(dá)式的運(yùn)算符在運(yùn)算對(duì)象之后。在后綴表達(dá)式中，不再引 入括號(hào)，所有的計(jì)算按運(yùn)算符出現(xiàn)的順序

11、，嚴(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á)式中即無(wú)括號(hào)又無(wú)優(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ù)闹稻褪墙Y(jié)果。下面是后綴表達(dá)式求值的算法，在下面的算法中假設(shè)，每個(gè)表達(dá)式是合乎語(yǔ)法的，并且假設(shè)后綴表達(dá)式已被存入一個(gè)足夠大的字符數(shù)組A中，且以 #為結(jié)束

12、字符，為了簡(jiǎn)化問(wèn)題，限定運(yùn)算數(shù)的位數(shù)僅為一位且忽略了數(shù)字字符串與相對(duì)應(yīng)的數(shù)據(jù)之間的轉(zhuǎn)換問(wèn)題。double calcul_exp(char *A) /*本函數(shù)返回由后綴表達(dá)式 A表示的表達(dá)式運(yùn)算結(jié)果*/ SeqStarck s;ch=*A+ ; I nitStack(s);while(ch!= #) if(ch!= 運(yùn)算符)PushStack(s, ch);else PopStack(s, & a);PopStack(s, &b); /*取出兩個(gè)運(yùn)算量*/switch(ch) case ch= +： c=a+b; break ; case ch= -：c=a-b;break ;case ch=

13、*:c=a*b;break ;case ch= /：c=a/b;break ;case ch= %:c=a%b;break ;PushStack (s, c);ch=*A+ ;PopStack(s, result);retur n result ;3.4中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式和前述對(duì)中綴表達(dá)式求值的方法 完全類(lèi)似，但只需要運(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í)類(lèi)似于中綴表達(dá)式求值時(shí)對(duì)運(yùn)算符的 處理過(guò)程

14、，但運(yùn)算符出棧后不是進(jìn)行相應(yīng)的運(yùn)算，而是將其送入B中存放。讀者不難寫(xiě)出算法，在此不在贅述。程序的整體算法分兩步：第一步，從”input.txt ”文件中讀取中綴表達(dá)式，并應(yīng)用運(yùn)算符棧 OpHolder把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，將輸出結(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á)式如下圖圖22：則輸出結(jié)果如下圖3：圖3 他謙眾結(jié)構(gòu)課程謨計(jì)

15、俵達(dá)式求值Debuea達(dá)式求值.eie-aPress mny key to continuezl圖45.2擴(kuò)展測(cè)試：在in put文件中輸入表達(dá)式如下圖5：則輸出結(jié)果如下圖6：圖5圖65.3容錯(cuò)測(cè)試：在in put文件中輸入表達(dá)式如下圖7：則輸出結(jié)果如下圖&圖7Errorininfixnotation ”AErrorininFiMnotation.ErroriniriFiknotation.Errorininfixnotation -Errorininfixnotation ”ErrorininFiMnotation.ErrorininiFixnotatian _ErrrininFixnQtt

16、iqn.ErrorininfiNnotation t_: 1ErrorinInFiMnotation.ErrorIriinfixnotation.ErroriniwFi科notation.ErrorininFixnotation Errorininfixnotation-Errorininfixnotation-Errorininfixnotation.Errorininfixnotation.V|B- Output.txt -記事本 匚遼|區(qū)文件世）騙輯 格式0）査看（D 幫肋圖86設(shè)計(jì)心得通過(guò)此次的課程設(shè)計(jì)，鞏固和加深了我對(duì)棧、隊(duì)列、字符串等理論 知識(shí)的理解；掌握現(xiàn)實(shí)復(fù)雜問(wèn)題的分析建模和解

17、決方法（；提高利用計(jì) 算機(jī)分析解決綜合性實(shí)際問(wèn)題的基本能力。在細(xì)節(jié)問(wèn)題的分析上，較以往有了很大的提高。在尋求最優(yōu)解的問(wèn) 題上，也能夠找到多種解決方案來(lái)使自己的程序收放自如。如，在處理 實(shí)數(shù)的問(wèn)題上，我采用的是每取得一個(gè)字符，就立刻對(duì)此字符進(jìn)行處理 的方法。其實(shí)，我們可以用一個(gè)字符數(shù)組，來(lái)存儲(chǔ)連接著的一系列數(shù)字 字符，然后再通過(guò)atof函數(shù)，直接得到字符數(shù)組中所存儲(chǔ)的數(shù)字。再如， 對(duì)負(fù)數(shù)問(wèn)題的處理上，我最初的想法是通過(guò)一個(gè)標(biāo)志mark來(lái)記錄前面的字符是否是負(fù)號(hào)（或減號(hào)），再在后面取到除符號(hào)外的數(shù)字時(shí)，選擇 是否添加負(fù)號(hào)。另外，與其他人不同的是，在我的課程設(shè)計(jì)中，Compare （）函數(shù)與其他有著

18、很大的區(qū)別。通常情況下，同學(xué)們參照課本，都會(huì) 采用占用7*7=49個(gè)空間的數(shù)組來(lái)分別存儲(chǔ)對(duì)應(yīng)兩個(gè)字符的優(yōu)先級(jí)符號(hào)， 并對(duì)兩個(gè)字符進(jìn)行預(yù)算之后得到數(shù)組中的位置。雖然7*7的數(shù)組所占的空間并不是非常大，但在我看來(lái)這也是一種浪費(fèi)，并且空間的浪費(fèi)并沒(méi) 有換回時(shí)間一定的節(jié)省。因此，我采用了一種常規(guī)的思路。將各種運(yùn)算 符按照數(shù)學(xué)邏輯上的優(yōu)先順序進(jìn)行排序， 并得到兩個(gè)字符之間的優(yōu)先級(jí) 關(guān)系。這樣一來(lái)，我們將不再需要那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)后出），使得在用棧來(lái)編程時(shí)，思路

19、清晰明了。在使用遞歸算法時(shí)，棧也是一種 很好的選擇。此外，這次的課程設(shè)計(jì)進(jìn)一步加強(qiáng)了我們運(yùn)用C語(yǔ)言進(jìn)行編程，調(diào)試，處理問(wèn)題的能力，加深了我們對(duì)算法及數(shù)據(jù)結(jié)構(gòu)的認(rèn)識(shí)。同時(shí)我也 意識(shí)到，開(kāi)發(fā)程序的早期計(jì)劃要做的充分，以免出現(xiàn)程序完成后發(fā)現(xiàn)不 足而帶來(lái)的修改麻煩。雖然這只是一個(gè)小小的軟件，但對(duì)我們之后的影 響確實(shí)很大的。7附：源程序清單#i nclude #include #in elude int Prin tError = 0;/*全局變量，0代表正常，1代表表達(dá)式出錯(cuò)*/*char類(lèi)型鏈表式堆棧，用來(lái)存放運(yùn)算符號(hào)，以及用在中綴表達(dá)式轉(zhuǎn)換等時(shí)候*/typedef struct Node *Ptr

20、ToNode;typedef PtrToNode Stack;int lsEmpty(Stack S);void MakeEmpty(Stack S);void Push(char X,Stack S);char Top(Stack S);void Pop(Stack S);typedef struct Node char Eleme nt; PtrToNode Next;/*float類(lèi)型鏈表式堆棧，用來(lái)存放操作數(shù)*/typedef struct FNode *Ptr_F n;typedef Ptr_Fn FStack;int FisEmpty(FStack S);void FPush(fl

21、oat X,FStack S);float FTop(FStack S);void FPop(FStack S); typedef struct FNode float Eleme nt;Ptr_ Fn Next;void Co nvertToPost(FILE *ln. Stack Whereat,FILE *Temp); void Reverse(Stack Rev);void Calculate(FILE *Cha nge. Stack Whereat,FILE *Temp);主函數(shù)*/int main()/*初始化變量*/FILE *In putFile, *OutputFile,*T

22、emp;Stack Whereat;char sample;In putFile = fope n(l nput.txt,r);OutputFile = fope n( Output.txt,w);Whereat = malloc(sizeof(struct Node);Whereat-Next = NULL;if (!I nputFile | !OutputFile) printf(intput or output file(s) do not exist.n);/*打開(kāi)文件*/*給 Whereat分配空間*/*錯(cuò)誤處理*/return(1);sample = getc(I nputFile

23、); while ( sample != EOF)Temp = fope n(Temp.txt,w+);/* 生成 Temp文 件 */un getc(sample,I nputFile);/* put back sample字符 */ConvertToPost(lnputFile,Whereat,Temp);/* 中綴變后綴 */if (PrintError)/* 錯(cuò)誤處理 */fprin tf(OutputFile,Error in infix no tati on.);fsca nf(I nputFile,n,&sample); Prin tError = 0;else if (IsEm

24、pty(Whereat) = 1)else if (IsEmpty(Whereat) != 1) Reverse(Whereat);if (Top(Whereat) = B)Prin tError = 1;數(shù)而不是運(yùn)算符號(hào)*/fclose(Temp);Temp = fope n(Temp.txt,r+);Calculate(OutputFile, Whereat,Temp); fclose(Temp);MakeEmpty(Whereat); putc(n,OutputFile);sample = getc(I nputFile);/*跳過(guò)在in put文件中的空格*/*錯(cuò)誤處理，*/*A表示操

25、作數(shù)B表示運(yùn)算符*/*后綴表達(dá)式第一個(gè)元素應(yīng)是操作/*計(jì)算結(jié)果*/*清空Whereat用來(lái)處理下一行*/*在輸出文件中換行*/* While循環(huán)結(jié)束*/* 刪除Temp.txt*/free(Whereat); fclose(l nputFile); fclose(OutputFile); remove(Temp.txt); return 1;檢查堆棧是否為空*/int lsEmpty(Stack S) return(S-Next=NULL);/*檢查float堆棧是否為空*/int FIsEmpty(FStack S)return(S-Next=NULL);彈出棧頂元素*/void Pop(S

26、tack 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 FirstCell;if (FIsEmpty(S)perror(Empty Stack); elseFirstCell = S-Next;S-Next = S-Next-Next;free(FirstCell);將堆棧置空*/void MakeEmpty(Stack

27、S)if (S = NULL)perror(Must use Createstack first);elsewhile (!lsEmpty(S) Pop(S);將float堆棧置空*/void FMakeEmpty(FStack S)if (S = NULL)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 (Tm

28、pCell = NULL)perror(Out of Space!);elseTmpCell-Eleme nt = X;TmpCell-Next = S-Next;S-Next = TmpCell;/*float元素進(jìn)棧*/void FPush(float X, FStack S)Ptr_Fn TmpCell;TmpCell = (Ptr_F n)malloc(sizeof(struct FNode);if (TmpCell = NULL) perror(Out of Space!);elseTmpCell-Eleme nt = X;TmpCell-Next = S-Next;S-Next =

29、 TmpCell;返回棧頂元素*/char Top(Stack S)if (!lsEmpty(S)retur n S-Next-Eleme nt; perror(Empty Stack); exit(1);return 0;/* 返回 float棧頂元素 */ float FTop(FStack S)if (!FIsEmpty(S)retur n S-Next-Eleme nt; perror(Empty Stack); exit(1);return 0;/*將堆棧元素倒置*/ void Reverse(Stack Rev)Stack Tempstack;Tempstack = malloc(

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

31、綴表達(dá)式*/void Con vertToPost(FILE *ln, Stack Whereat, FILE *Temp)Stack OpHolder;char holder;char lastsee n;int digitcounter = 0;/*操作數(shù)的計(jì)數(shù)器 */OpHolder = malloc(sizeof(struct Node); /* 初始化 */OpHolder-Next = NULL;holder=getc(I n);lastseen = ;/*用來(lái)防止輸入格式錯(cuò)誤，例如兩個(gè)小數(shù)點(diǎn)*/putc( ,Temp);while (holder !=n) & (holder !

32、= EOF) if (holder = )digitco un ter = 0;/*如果holder不是操作數(shù)或運(yùn)算符else if ( IsOperator(holder) = -1)號(hào)*/Prin tError = 1;else if (IsOperator(holder)=0)/*錯(cuò)誤處理*/if (lastsee n = holder) & (lastsee n = .)Prin tError = 1; else/*進(jìn)棧*/*計(jì)數(shù)器加一 */lastsee n = holder; if (digitco un ter = 0)Push(A,Whereat); digitco un te

33、r+; putc( ,Temp);putc(holder,Temp);elsedigitco un ter = 0;if (lastseen = holder) & (lastseen != () & (lastseen != )/*(情況特殊對(duì)待*/Prin tError = 1;elselastsee n = holder;if(lsEmpty(OpHolder)=1)/* 當(dāng) OpHolder 為空 */Push(holder,OpHolder);else if(OperatorValue(Top(OpHolder) = 6) /*OpHolder 是(的情況 */ if(Operato

34、rValue(holder)=5)Pop(OpHolder);elsePush(holder,OpHolder);else if(OperatorValue(holder) = 6)Push(holder,OpHolder);else if(OperatorValue(holder) = 5)/* OpHolder是)的情況 */while (IsEmpty(OpHolder) != 1) & (OperatorValue(Top(OpHolder) !=6)putc( ,Temp);Push(B,Whereat);putc(Top(OpHolder),Temp);Pop(OpHolder);

35、if (IsEmpty(OpHolder) = 1)/* 錯(cuò)誤處理，括號(hào)不匹配 */Prin tError = 1;elsePop(OpHolder);else if(OperatorValue(holder) = OperatorValue(Top(OpHolder)& (OperatorValue(holder) = 3)/* 幕運(yùn)算情況 */Push(holder,OpHolder);else if(OperatorValue(holder) = OperatorValue(holder)while(lsEmpty(OpHolder) != 1)&(OperatorValue(Top(O

36、pHolder)=OperatorValue(holder)& (OperatorValue(Top(OpHolder)!=6)putc( ,Temp);putc(Top(OpHolder),Temp);Push(B,Whereat);Pop(OpHolder);Push(holder,OpHolder);else if(OperatorValue(Top(OpHolder) Next= NULL;while (IsEmpty(Whereat) != 1) & Prin tError != 1)/*循環(huán)直到Whereat空，或者遇到錯(cuò)誤*/if (Top(Whereat) = A)fsca n

37、f(Temp, ，&spacefi nder);fscanf(Temp,%f,&looker);/*如果是 A,則是操作數(shù) */FPush(looker,Opera nds);Pop(Whereat);else if (Top(Whereat) = B)fscanf(Temp, ，&spacefinder);/* 如果是 B,則是運(yùn)算符 */Op = getc(Temp);switch(Op)/*判斷是什么運(yùn)算符*/case(A):/* 幕運(yùn)算 */NumB = FTop(Opera nds);FPop(Opera nds);if (FlsEmpty(Operands) /*錯(cuò)誤處理 */Pr

38、in tError = 1;elseNumA = FTop(Opera nds);FPop(Opera nds);if (NumA = 0 & NumB 0)|(NumA0)& (NumB - (in t)NumB != 0)Prin tError = 1;elsean swer = pow(NumA,NumB); FPush(a nswer,Opera nds);break;case %:/*取模運(yùn)算*/NumB = FTop(Opera nds);FPop(Opera nds);if (FIsEmpty(Operands)/*錯(cuò)誤處理 */Prin tError = 1;elseNumA = FTop(Opera nds);FPop(Opera nds);if (NumA - (in t)NumA != 0) | (NumB - (in t)NumB != 0)| (NumB = 0)Prin tError = 1;e