課程設(shè)計(jì)--表達(dá)式翻譯

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　　選題名稱: 表達(dá)式翻譯 </p><p>　　系（院）: 計(jì)算機(jī)工程系</p><p>　　專 業(yè): 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　班 級(jí):

2、 </p><p>　　姓 名: 學(xué) 號(hào): </p><p>　　指導(dǎo)教師: </p><p>　　學(xué)年學(xué)期: ~ 學(xué)年 第 學(xué)期</p><p>　　年 月 日</p

3、><p><b>　　設(shè)計(jì)任務(wù)書</b></p><p><b>　　注意：</b></p><p>　　任務(wù)書格式參照“任務(wù)書范例”執(zhí)行。</p><p>　　范例中的紅色文字應(yīng)根據(jù)你所選擇的具體課題，修改為對(duì)應(yīng)的內(nèi)容。</p><p>　　范例中的其它內(nèi)容不變。</p&

4、gt;<p><b>　　摘要：</b></p><p>　　后綴表達(dá)式被廣泛應(yīng)用于編譯原理中，原因是后綴表達(dá)式有一個(gè)其他的算法不能比擬的優(yōu)點(diǎn)——拆括號(hào)。標(biāo)準(zhǔn)的表達(dá)式如“A+B”，在數(shù)學(xué)上學(xué)名叫中綴表達(dá)式，原因是運(yùn)算符號(hào)在兩個(gè)運(yùn)算對(duì)象的中間。相對(duì)應(yīng)的還有前綴表達(dá)式，如：“+ - A * B C D”，轉(zhuǎn)換成中綴表達(dá)式為：“A - B * C + D”；后綴表達(dá)式，比如前所述的中

5、綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式為：“A B C * - D +”。后綴表達(dá)式的優(yōu)點(diǎn)是顯而易見的，編譯器在處理時(shí)候按照從左至右的順序讀取后綴表達(dá)式，遇到運(yùn)算對(duì)象直接壓入堆棧，遇到運(yùn)算符就從堆棧提取后進(jìn)的兩個(gè)對(duì)象進(jìn)行計(jì)算，這個(gè)過程正好符合了計(jì)算機(jī)計(jì)算的原理。后綴表達(dá)式比前綴表達(dá)式更加易于轉(zhuǎn)換，并且它的最左面一定為數(shù)字，這一點(diǎn)在實(shí)際編程的時(shí)候就會(huì)體會(huì)到它的好處了。后綴表達(dá)式有一個(gè)更大的優(yōu)點(diǎn)，就是拆括號(hào)，根據(jù)運(yùn)算符的級(jí)別將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式后

6、，運(yùn)算順序就已經(jīng)替代了運(yùn)算符的級(jí)別，這樣也避免了括號(hào)提高運(yùn)算級(jí)別的特殊處理。</p><p>　　關(guān)鍵字：順序棧；優(yōu)先級(jí)；中綴表達(dá)式；后綴表達(dá)式</p><p><b>　　目 錄</b></p><p><b>　　1 需求分析1</b></p><p>　　1.1 任務(wù)要求1</p&

7、gt;<p>　　1.2 課程設(shè)計(jì)思想1</p><p>　　1.3 運(yùn)行環(huán)境1</p><p><b>　　2 概要設(shè)計(jì)1</b></p><p>　　2.1 總體功能結(jié)構(gòu)1</p><p>　　2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2</p><p>　　2.3 程序原理2</p

8、><p>　　3 詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)3</p><p>　　3.1 模塊功能3</p><p>　　3.2 算法原理4</p><p>　　3.3 流程圖12</p><p>　　4 調(diào)試與操作說明12</p><p><b>　　總 結(jié)15</b></p>

9、;<p><b>　　致 謝16</b></p><p>　　參 考 文 獻(xiàn)17</p><p><b>　　指導(dǎo)教師評(píng)語18</b></p><p><b>　　1 需求分析</b></p><p><b>　　1.1 任務(wù)要求</b&g

10、t;</p><p>　　本次的課程設(shè)計(jì)實(shí)踐周，我做的課題是表達(dá)式翻譯。此次課程設(shè)計(jì)的任務(wù)是收集一些有關(guān)中綴表達(dá)式翻譯成后綴表達(dá)式知識(shí)的資料，還有括號(hào)匹配方面的資料。編寫完整程序，將中綴表達(dá)式翻譯成后綴表達(dá)式。認(rèn)真主動(dòng)完成課程設(shè)計(jì)的要求。有問題及時(shí)主動(dòng)通過各種方式與教師聯(lián)系溝通。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，設(shè)計(jì)程序并調(diào)試。在課程設(shè)計(jì)周，主要是進(jìn)行課程設(shè)計(jì)的答辯工作，期間也繼續(xù)

11、進(jìn)行的調(diào)試與完善工作，上機(jī)時(shí)數(shù)通常為12~15小時(shí)，參加答辯。</p><p>　　1.2 課程設(shè)計(jì)思想</p><p>　　一般來說，課程設(shè)計(jì)要比教學(xué)實(shí)驗(yàn)復(fù)雜一些，涉及的深度廣些，而且更加實(shí)用一些。其主要目的是通過課程設(shè)計(jì)的綜合訓(xùn)練，培養(yǎng)學(xué)生分析解決實(shí)際問題和編程等實(shí)際動(dòng)手能力，最終目標(biāo)是想通過這種形式，幫助學(xué)生系統(tǒng)掌握數(shù)據(jù)結(jié)構(gòu)這門課程的主要內(nèi)容，使老師更好的完成教學(xué)任務(wù)。數(shù)據(jù)結(jié)構(gòu)是一門

12、涉及多門課程的課程，難度較大，需要較好的C/C++語言的程序設(shè)計(jì)和調(diào)試能力，如果學(xué)生能夠按照要求，從時(shí)間和精力上保證完全的投入，相信能夠有很大的收獲，幾分投入幾分收獲。</p><p><b>　　1.3 運(yùn)行環(huán)境</b></p><p>　　Windows2000以上操作系統(tǒng)、Visual C++6.0以上編譯環(huán)境。</p><p><

13、b>　　2 概要設(shè)計(jì)</b></p><p>　　2.1 總體功能結(jié)構(gòu)</p><p>　　編寫一個(gè)完整的程序，將中綴表達(dá)式翻譯成后綴表達(dá)式。表達(dá)式由操作數(shù)(變量)、操作(運(yùn)算符)以及小括弧“（”和“）”組成，其中：操作包括算術(shù)運(yùn)算、關(guān)系運(yùn)算和邏輯運(yùn)算三類；操作數(shù)應(yīng)能夠識(shí)別但個(gè)字符或由字母和數(shù)字任意多個(gè)字符構(gòu)成；能夠識(shí)別出簡(jiǎn)單的錯(cuò)誤，如括弧不匹配。</p>

14、<p>　　設(shè)計(jì)一個(gè)順序棧類SeqStack，作為程序的頭文件SeqStack.h。再設(shè)計(jì)四個(gè)函數(shù)：棧內(nèi)優(yōu)先級(jí)函數(shù)isp(),棧外優(yōu)先級(jí)函數(shù)icp(),表達(dá)式檢查函數(shù)ExpIsCorrect()和表達(dá)式轉(zhuǎn)換函數(shù)postfix()。</p><p>　　2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</p><p>　　利用一個(gè)順序?？梢詫?shí)現(xiàn)將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，也能實(shí)現(xiàn)對(duì)括號(hào)是否匹配進(jìn)行檢測(cè)。用一

15、個(gè)字符型數(shù)組存放從鍵盤輸入的中綴表達(dá)式，經(jīng)運(yùn)行后由屏幕輸出轉(zhuǎn)化后的后綴表達(dá)式。</p><p><b>　　2.3 程序原理</b></p><p>　　棧（stack）是最常用和最重要的數(shù)據(jù)結(jié)構(gòu)。局部變量是放在棧中的，表達(dá)式的優(yōu)先級(jí)處理也是基于棧來實(shí)現(xiàn)的，函數(shù)調(diào)用時(shí)的參數(shù)傳遞和函數(shù)值的返回都是由棧來實(shí)現(xiàn)的。棧是限制在表的一端進(jìn)行插入和刪除的線性表（即一維數(shù)組）。允許

16、插入刪除的一端為棧頂，另一固定端為棧底。當(dāng)表中沒有元素時(shí)稱為空棧。如圖2-1所示，棧中有三個(gè)元素，進(jìn)棧的順序是a、b、c，當(dāng)需要出棧時(shí)其順序?yàn)閏、b、a。所以棧又稱為后進(jìn)先出的線性表（Last In First Out）,簡(jiǎn)稱LIFO表。</p><p>　　在日常生活中，有很多后進(jìn)先出的例子。在程序設(shè)計(jì)中，常常需要使得與保存數(shù)據(jù)時(shí)相反順序來使用這些數(shù)據(jù)，這時(shí)就需要用一個(gè)棧來實(shí)現(xiàn)。</p><

17、p>　　對(duì)于棧，常做的基本運(yùn)算有：</p><p>　　（1）棧初始化：Init_Stack(s)</p><p>　　初始條件：棧s不存在</p><p>　　操作結(jié)果：構(gòu)造了一個(gè)空棧。</p><p>　　（2）判斷?？眨篍mpty_Stack(s)</p><p>　　初始條件:棧s已存在</p>

18、;<p>　　操作結(jié)果：若棧s為空棧返回為1，否則返回為0.</p><p>　　（3）入棧：Push_Stack(s,x)</p><p>　　初始條件：棧s已存在</p><p>　　操作結(jié)果：在棧s的頂部插入一個(gè)新元素x，x成為新的棧頂元素。棧發(fā)生變化。</p><p>　　（4）出棧：Pop_Stack(s)</p

19、><p>　　初始條件：棧s存在且非空</p><p>　　操作結(jié)果：棧s的頂部元素從棧中刪除，棧中少了一個(gè)元素。棧發(fā)生變化。</p><p>　?。?）讀棧頂元素：Top_Stack(s)</p><p>　　初始條件：棧s存在且非空</p><p>　　操作結(jié)果：棧頂元素作為結(jié)果返回，棧不變化。</p>

20、<p>　　棧可以用順序表實(shí)現(xiàn)，稱為順序棧；也可以用鏈表實(shí)現(xiàn)，稱為鏈棧。順序棧和鏈棧的邏輯功能一樣。順序棧必須先開一定大小的內(nèi)存空間，執(zhí)行起來簡(jiǎn)單并且速度快，但可能溢出；鏈棧的內(nèi)存空間隨用隨開，不會(huì)溢出；但執(zhí)行復(fù)雜（不斷地動(dòng)態(tài)分配）且速度慢。</p><p><b>　　3 詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)</b></p><p><b>　　3.1 模塊功能<

21、;/b></p><p>　　定義一個(gè)順序棧類SeqStack，首先構(gòu)造一個(gè)空棧，包含的操作有進(jìn)棧Push()，出棧Pop()，取棧頂元素GetTop()，判?？辗馧otEmpty()。利用這個(gè)順序棧對(duì)中綴表達(dá)式進(jìn)行檢測(cè)，若出錯(cuò)（主要為括號(hào)比匹配），給出出錯(cuò)提示；否則，將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。</p><p>　　表達(dá)式檢測(cè)函數(shù)ExpIsCorrect()，實(shí)現(xiàn)對(duì)表達(dá)式中的括號(hào)

22、進(jìn)行匹配檢驗(yàn)。算術(shù)表達(dá)式中右括號(hào)和左括號(hào)匹配的次序正好符合后到括號(hào)要最先被匹配的“后進(jìn)先出”棧操作特點(diǎn)，因此可以借助一個(gè)棧來進(jìn)行判斷。</p><p>　　表達(dá)式轉(zhuǎn)換函數(shù)postfix()，當(dāng)表達(dá)式正確時(shí)，利用此函數(shù)將中綴表達(dá)式轉(zhuǎn)換成對(duì)應(yīng)的后綴表達(dá)式。將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式過程中，要注意的是“（”無論入棧中級(jí)別為何，直接入棧，在遇到“）”時(shí)候，找到最后進(jìn)入的“（”，并把“（”前面所有的符號(hào)都?jí)喝氤鰲！?lt

23、;/p><p>　　由于在表達(dá)式轉(zhuǎn)換過程中，需要比較新讀入元素與當(dāng)前棧頂元素的優(yōu)先級(jí)，所以，需要定義兩個(gè)優(yōu)先級(jí)函數(shù)：棧外優(yōu)先級(jí)函數(shù)icp()和棧內(nèi)優(yōu)先級(jí)函數(shù)isp()。</p><p><b>　　3.2 算法原理</b></p><p>　　棧的抽象數(shù)據(jù)類型有兩種典型的存儲(chǔ)表示：基于數(shù)組的存儲(chǔ)表示和基于鏈表的存儲(chǔ)表示?；跀?shù)組的存儲(chǔ)表示實(shí)現(xiàn)的棧稱

24、為順序棧，基于鏈表的存儲(chǔ)表示實(shí)現(xiàn)的棧稱為鏈棧。</p><p>　　順序?？梢圆捎庙樞虮碜鳛槠浯鎯?chǔ)表示，為此，可以在順序棧的聲明中用順序表定義它的存儲(chǔ)空間。本次課程設(shè)計(jì)中，實(shí)用一維數(shù)組作為棧的存儲(chǔ)空間。存放棧元素的數(shù)組的頭指針為*s，該數(shù)組的最大允許存放元素個(gè)數(shù)為maxsize，當(dāng)前棧頂位置由數(shù)組下標(biāo)指針top指示。如果棧不空時(shí)，s[0]是棧中第一個(gè)元素。</p><p><b>

25、;　　順序棧的類定義</b></p><p>　　class SeqStack</p><p><b>　　{</b></p><p><b>　　public:</b></p><p>　　SeqStack(){top=0;}; //構(gòu)造一個(gè)空棧</p><p&g

26、t;　　~SeqStack(){}</p><p>　　void Push(const char x);</p><p>　　char Pop();</p><p>　　char GetTop()const;</p><p>　　bool NotEmpty()const </p><p>　　{return(top!=

27、0);}</p><p><b>　　private:</b></p><p>　　char s[maxsize];</p><p><b>　　int top;</b></p><p><b>　　};</b></p><p>　　top指示的是最后加

28、入的元素的存儲(chǔ)位置。在實(shí)現(xiàn)進(jìn)棧操作時(shí)，應(yīng)先判斷棧是否已滿。棧的最后允許存放位置為maxsize，如果棧頂指針top==maxsize，則說明棧中所有位置均已使用，棧已滿。這時(shí)若再有新元素進(jìn)棧，將發(fā)生溢出，程序轉(zhuǎn)入溢出處理。如果top<maxsize，則先讓棧頂指針進(jìn)1，指到當(dāng)前可加入新元素的位置，再按棧頂指針?biāo)肝恢脤⑿略夭迦?。這個(gè)新插入的元素將成為新的棧頂元素。</p><p>　　另一個(gè)極端情況出現(xiàn)在

29、棧底：如果在退棧時(shí)發(fā)現(xiàn)是空棧，即top==0，則退棧操作將執(zhí)行棧空處理。?？仗幚硪话悴皇浅鲥e(cuò)處理，而是使用這個(gè)棧的算法結(jié)束時(shí)需要執(zhí)行的處理。若當(dāng)前top≥0，則可將棧頂指針減1，等于棧頂退回到次棧頂位置。</p><p><b>　　棧的成員函數(shù)的實(shí)現(xiàn)</b></p><p>　　void SeqStack::Push(const char x)</p>

30、<p><b>　　{</b></p><p>　　if(top==maxsize)</p><p><b>　　{</b></p><p>　　cout<<"棧已滿"<<endl;</p><p><b>　　exit(0);<

31、;/b></p><p><b>　　}</b></p><p>　　s[top]=x; //先存儲(chǔ)x</p><p>　　top++; //然后top加1</p><p><b>　　}</b></p><p>　　char SeqStack::Pop()<

32、/p><p><b>　　{</b></p><p>　　if(top==0)</p><p><b>　　{</b></p><p>　　cout<<"棧已空"<<endl;</p><p><b>　　exit(0);&l

33、t;/b></p><p><b>　　}</b></p><p>　　top--; //top先減1</p><p>　　return s[top]; //然后去元素返回</p><p><b>　　}</b></p><p>　　char SeqStack::G

34、etTop()const //取棧頂數(shù)據(jù)元素</p><p><b>　　{</b></p><p>　　if(top==0)</p><p><b>　　{</b></p><p>　　cout<<"棧已空"<<endl;</p><

35、;p><b>　　exit(0);</b></p><p><b>　　}</b></p><p>　　return s[top-1]; //返回當(dāng)前棧頂元素</p><p><b>　　}</b></p><p>　　舉例說明，在一個(gè)字符串“（a*(b+c)-d）”中

36、位置1和位置4有左括號(hào)“（”，位置8和位置11有右括號(hào)“）”。位置1的左括號(hào)匹配位置11的右括號(hào)，位置4的左括號(hào)匹配位置8的右括號(hào)。而對(duì)于字符串“（a+b））（”，位置6的右括號(hào)沒有可匹配的左括號(hào)，位置7的左括號(hào)沒有可匹配的右括號(hào)。</p><p>　　我們的目的是建立一個(gè)算法，輸入一個(gè)字符串，輸出括號(hào)匹配的信息。</p><p>　　算法思想：算術(shù)表達(dá)式中右括號(hào)和左括號(hào)匹配的次序正好符合

37、后到括號(hào)要最先被匹配的“后進(jìn)先出”棧操作特點(diǎn)，因此可以借助一個(gè)棧來進(jìn)行判斷。</p><p>　　括號(hào)匹配共有四種情況：</p><p>　　左、右括號(hào)配對(duì)次序不正確；</p><p><b>　　右括號(hào)多于左括號(hào)；</b></p><p><b>　　左括號(hào)多于右括號(hào)；</b></p>

38、<p>　　左、右括號(hào)匹配正確。</p><p>　　具體方法是：順序掃描算術(shù)表達(dá)式（表現(xiàn)為一個(gè)字符串），當(dāng)遇到三種類型的左括號(hào)時(shí)，讓該括號(hào)進(jìn)棧；當(dāng)掃描到某一種類型的右括號(hào)時(shí)，比較當(dāng)前棧頂括號(hào)是否與之匹配，若匹配，則退棧，繼續(xù)進(jìn)行判斷；若當(dāng)前棧頂括號(hào)與當(dāng)前掃描的括號(hào)不相同，則左、右括號(hào)配對(duì)次序不正確；若字符串當(dāng)前為某種類型左括號(hào)而棧已空，則右括號(hào)多于左括號(hào)；字符串循環(huán)掃描結(jié)束時(shí)，若棧非空（即粘中尚有

39、某種類型左括號(hào)），則說明左括號(hào)多于右括號(hào)；否則，左、右括號(hào)匹配正確。</p><p><b>　　函數(shù)設(shè)計(jì)如下：</b></p><p>　　void ExpIsCorrect(char exp[],int n) //判斷有n個(gè)字符串exp左、右括號(hào)是否//配對(duì)正確</p><p><b>　　{</b></p&g

40、t;<p>　　SeqStack myStack; //定義順序棧類對(duì)象myStack</p><p><b>　　int i;</b></p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　if(exp[i]==&#

41、39;(')</p><p>　　myStack.Push(exp[i]); //入棧</p><p>　　else if(exp[i]==')'&&myStack.NotEmpty()&&myStack.GetTop()=='(')</p><p>　　myStack.Pop(); //出

42、棧</p><p>　　else if(exp[i]==')'&&myStack.NotEmpty()&&myStack.GetTop()!='(')</p><p><b>　　{</b></p><p>　　cout<<"左右括號(hào)配對(duì)次序不正確！請(qǐng)檢查表達(dá)

43、式"<<endl;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　else if((exp[i]==')')&&!myStack.NotEmpty())</p><p><b

44、>　　{</b></p><p>　　cout<<"右括號(hào)多于左括號(hào)！請(qǐng)檢查表達(dá)式"<<endl;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　}<

45、;/b></p><p>　　if(myStack.NotEmpty())</p><p>　　cout<<"左括號(hào)多于右括號(hào)！請(qǐng)檢查表達(dá)式"<<endl;</p><p><b>　　else</b></p><p><b>　　{</b><

46、/p><p>　　cout<<"表達(dá)式正確，請(qǐng)?jiān)佥斎肷鲜剑ㄒ?結(jié)束）"<<endl;</p><p>　　postfix();</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　使用?？?/p>

47、將表達(dá)式的中綴表示轉(zhuǎn)換成它的前綴表示和后綴表示。本次課程設(shè)計(jì)討論的是比較實(shí)用的將中綴表示轉(zhuǎn)換為后綴表示的方法。</p><p>　　在中綴表達(dá)式中操作符的優(yōu)先級(jí)和括號(hào)使得求職過程復(fù)雜化，把它轉(zhuǎn)換成后綴表達(dá)式，可簡(jiǎn)化求值過程。為了實(shí)現(xiàn)這種轉(zhuǎn)換，需要考慮各操作符的優(yōu)先級(jí)，參看表3-1。</p><p>　　表3-1 各個(gè)算術(shù)操作符的優(yōu)先級(jí)</p><p>　　isp叫做

48、棧內(nèi)（in stack priority）優(yōu)先數(shù)，icp叫做棧外（in coming priority）優(yōu)先數(shù)。從表32中可以看到，左括號(hào)的棧外優(yōu)先數(shù)最高，它一來到立即進(jìn)棧，但當(dāng)它進(jìn)入棧中后，其棧內(nèi)優(yōu)先數(shù)變得極低，以便括號(hào)內(nèi)的其他操作符進(jìn)棧。其他操作符進(jìn)入棧中后優(yōu)先數(shù)都升1，這樣可體現(xiàn)在中綴表達(dá)式中相同優(yōu)先級(jí)的操作符自左向右計(jì)算的要求，讓位于棧頂?shù)牟僮鞣韧藯２⑤敵?。操作符?yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對(duì)或棧底的“#”號(hào)與輸入流最后的’

49、#’號(hào)配對(duì)時(shí)。前者將連續(xù)退出位于棧頂?shù)牟僮鞣钡接龅健ā癁橹埂Ｈ缓髮ⅰ埃ā蓖藯Ｒ詫?duì)消括號(hào)，后者將結(jié)束算法。</p><p>　　掃描中綴表達(dá)式，將它轉(zhuǎn)換為后綴表達(dá)式的算法描述如下：</p><p>　?、贄３跏蓟?，將結(jié)束符#進(jìn)棧。然后讀入中綴表達(dá)式字符流的首字符ch。</p><p>　　②重復(fù)執(zhí)行以下步驟，直到ch=‘#’，同時(shí)棧頂?shù)牟僮鞣彩恰?’，停止循環(huán)

50、。</p><p>　　若ch是操作數(shù)直接輸出，讀入下一個(gè)字符ch。</p><p>　　若ch是操作符，判斷ch 的棧外優(yōu)先級(jí)icp和當(dāng)前位于棧頂?shù)牟僮鞣鹢p的棧內(nèi)優(yōu)先級(jí)isp：</p><p>　　·若icp(ch)>isp(op)，令ch進(jìn)棧，讀入下一個(gè) 字符ch。</p><p>　　·若icp(

51、ch)<isp(op)，退棧并輸出。</p><p>　　·若icp(ch)=isp(op)，退棧但不輸出，若退出的是‘（’號(hào)讀入下一個(gè)字符ch。</p><p>　?、鬯惴ńY(jié)束，輸出序列即為所需的后綴表達(dá)式。</p><p>　　例如，給定中綴表達(dá)式為A+B*(C-D)-E/F,應(yīng)當(dāng)轉(zhuǎn)換成ABCD-*+EF/-，按上述算法應(yīng)執(zhí)行的轉(zhuǎn)換過程（包括棧的

52、變化和輸出）如圖3-1所示。</p><p>　　圖3-1 利用棧的轉(zhuǎn)換過程</p><p>　　中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的算法</p><p>　　void postfix()</p><p>　　{ //把中綴表示轉(zhuǎn)換成后綴表示并輸出之</p><p>　　SeqStack s; //定義棧的對(duì)象s</

53、p><p>　　char ch='#';</p><p>　　s.Push(ch); //棧底放了一個(gè)‘#’</p><p>　　cin.get(ch); //讀入一個(gè)字符</p><p>　　while(s.NotEmpty()==true&&ch!='#') //連續(xù)處理</p>

54、;<p><b>　　{</b></p><p>　　if(isdigit(ch)) //是操作數(shù)，輸出之</p><p><b>　　{</b></p><p>　　cout<<ch<<" ";</p><p>　　cin.get(ch)

55、;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(isp(s.GetTop())<icp(ch)) //新輸入操作符ch優(yōu)先級(jí)高</p><p&

56、gt;<b>　　{</b></p><p>　　s.Push(ch); //進(jìn)棧</p><p>　　cin.get(ch); //讀入下一字符</p><p><b>　　}</b></p><p>　　else if(isp(s.GetTop())>icp(ch)) //新輸入操作

57、符優(yōu)先級(jí)低</p><p><b>　　{</b></p><p>　　cout<<s.Pop()<<" "; //退棧并輸出</p><p><b>　　}</b></p><p><b>　　else</b></p>

58、<p><b>　　{</b></p><p>　　if(s.Pop()=='(')</p><p>　　cin.get(ch);</p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

59、t;<b>　　}</b></p><p>　　cout<<s.Pop();</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　該算法對(duì)輸入表達(dá)式只進(jìn)行一次自左向右的掃描，對(duì)每個(gè)操作數(shù)只執(zhí)行一次輸出，其執(zhí)行時(shí)間為O（1）。

60、對(duì)每一個(gè)操作符，執(zhí)行進(jìn)棧和退棧各一次，其時(shí)間也為O（1）。若設(shè)表達(dá)式中符號(hào)的總數(shù)為n，則總的執(zhí)行時(shí)間復(fù)雜度為O（n）。</p><p><b>　　棧內(nèi)優(yōu)先級(jí)算法</b></p><p>　　int isp(char x) //棧內(nèi)優(yōu)先級(jí)</p><p><b>　　{</b></p><p>&

61、lt;b>　　switch(x)</b></p><p><b>　　{</b></p><p>　　case'#':return 0;break;</p><p>　　case'(':return 1;break;</p><p>　　case'/':c

62、ase'*':return 5;break;</p><p>　　case'+':case'-':return 3;break;</p><p>　　case')':return 6;break;</p><p><b>　　}</b></p><p>&l

63、t;b>　　}</b></p><p><b>　　棧外優(yōu)先級(jí)算法</b></p><p>　　int icp(char x) //棧外優(yōu)先級(jí)</p><p><b>　　{</b></p><p><b>　　switch(x)</b></p>

64、<p><b>　　{</b></p><p>　　case'#':return 0;break;</p><p>　　case'(':return 6;break;</p><p>　　case'/':case'*':return 4;break;</p>

65、;<p>　　case'+':case'-':return 2;break;</p><p>　　case')':return 1;break;</p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

66、t;<b>　　3.3 流程圖</b></p><p><b>　　圖3-2</b></p><p><b>　　4 調(diào)試與操作說明</b></p><p>　　運(yùn)行后的初始界面如圖4-1所示</p><p><b>　　圖4-1</b></p>

67、;<p>　　若表達(dá)式正確，如輸入9-（2+4*7）/5+3，按下回車鍵，結(jié)果如圖4-2所示</p><p><b>　　圖4-2</b></p><p>　　此時(shí)表達(dá)式已被檢測(cè)為正確，則將它轉(zhuǎn)換成后綴表達(dá)式，結(jié)果如圖4-3所示</p><p><b>　　圖4-3</b></p><p&

68、gt;　　輸入n，不結(jié)束，在輸入一個(gè)錯(cuò)誤的中綴表達(dá)式，如圖4-4所示</p><p><b>　　圖4-4</b></p><p><b>　　總 結(jié)</b></p><p><b>　　致 謝</b></p><p><b>　　參 考 文 獻(xiàn)</b>

69、;</p><p>　　1 殷人昆，陶永雷等編著.數(shù)據(jù)結(jié)構(gòu)——用面向?qū)ο蠓椒ㄅcC++語言描述.北京：清華大學(xué)出版社，1997</p><p>　　2 徐孝凱編著.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C/C++描述）.北京：清華大學(xué)出版社，1999</p><p>　　3 朱站立編.數(shù)據(jù)結(jié)構(gòu)——使用C++語言.先西安：西安電子科技大學(xué)出版社，2001</p><p&