算術(shù)表達(dá)式的求解講解

1、沁捻短工詈噬JIANGSU UNIVERSITY OF TECHNOLOGY軟件 綜合課 程設(shè)計(jì)算術(shù)表達(dá)式的求解&車廂調(diào)度二0一四年六月軟件綜合課程設(shè)計(jì)目錄算數(shù)表達(dá)式的求解 3一、前言 3二、問題陳述 3三、需求分析 3四、概要設(shè)計(jì) 4五、詳細(xì)設(shè)計(jì)和編碼 6六、上級調(diào)試過程 10七、總結(jié)與心得 12八、參考文獻(xiàn) 13附錄（源程序）： 13車廂調(diào)度 201、 問題陳述 202、 問題分析與設(shè)計(jì) 203、 運(yùn)行結(jié)果 20四、設(shè)計(jì)體會(huì)與總結(jié) 214、 （源程序 ） 21第 3 頁 共 22 頁算數(shù)表達(dá)式的求解、前言表達(dá)式計(jì)算是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一

2、個(gè)程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程。在計(jì)算機(jī)中，算術(shù)表達(dá)式由常量、變量、運(yùn)算符和括號(hào)組成。由于不同的運(yùn)算符具有不同的優(yōu)先級，又要考慮括號(hào)，因此，算術(shù)表達(dá)式的求值不可能嚴(yán)格地從左到右進(jìn)行。因而在程序設(shè)計(jì)時(shí)，借助棧實(shí)現(xiàn)。算法輸入：一個(gè)算術(shù)表達(dá)式，由常量、變量、運(yùn)算符和括號(hào)組成（以字符串形式輸入） 。為簡化，規(guī)定操作數(shù)只能為正整數(shù)，操作符為 +、 -* 、 / ，用#表示結(jié)束。算法輸出：表達(dá)式運(yùn)算結(jié)果。算法要點(diǎn)：設(shè)置運(yùn)算符棧和操作數(shù)棧輔助分析算符優(yōu)先關(guān)系。在讀入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)的識(shí)別處理，以及相應(yīng)運(yùn)算。二、問題陳述（算數(shù)表達(dá)式的求解）給定一個(gè)算數(shù)表達(dá)式，通過程序

3、求出最后的結(jié)果要求如下：1 、從鍵盤輸入要求解的算術(shù)表達(dá)式；2 、采用棧結(jié)構(gòu)進(jìn)行算數(shù)表達(dá)式的求解過程；3 、能夠判斷算數(shù)表達(dá)式的正確與否；4 、對于錯(cuò)誤表達(dá)式給出提示；5 、對于正確表達(dá)時(shí)給出最后的結(jié)果。三、需求分析有題目可知， 程序要求給定一算數(shù)表達(dá)式并計(jì)算最后的結(jié)果， 我們知道， 在高級語言中， 任何一個(gè)表達(dá)式都是有操作數(shù)、 運(yùn)算符和界限符組成。 在計(jì)算過程中， 還要考慮表達(dá)式中有無括號(hào)以及左右括號(hào)之分。 由于運(yùn)算符有優(yōu)先級的高低，因此一個(gè)算數(shù)表達(dá)是不可能總是按順序執(zhí)行。通過以上可知，可以用棧來實(shí)現(xiàn)運(yùn)算符的優(yōu)先級完成算術(shù)表達(dá)式的求解。為實(shí)現(xiàn)算法的優(yōu)先級，設(shè)置兩個(gè)棧：一個(gè)稱為操作數(shù)棧opnd

4、,用以寄存操作數(shù)和運(yùn)算結(jié)果，另一個(gè)為操作符棧optr ，用以寄存運(yùn)算符。該算法的基本思想是：（ 1）首先置操作數(shù)棧opnd 為空棧， 表達(dá)式結(jié)束符“ #” 為操作符棧optr 的棧底 元素。（2）依次讀入表達(dá)式中每個(gè)字符，若為操作數(shù)，則進(jìn) opnd棧；若是運(yùn)算符，則與 optr 棧的棧頂運(yùn)算符比較優(yōu)先級后做相應(yīng)操作： 若當(dāng)前操作符大于optr 棧的棧頂，則當(dāng)前操作符入棧；否則， opnd 棧的棧頂元素、次棧頂元素出棧，同時(shí)optr棧的棧頂元素也出棧，形成運(yùn)算，并將結(jié)果壓入 opnd棧，直至整個(gè)表達(dá)式求值完畢（即 optr 棧的棧頂元素和當(dāng)前讀入的字符均為“#” ） 。對于算術(shù)表達(dá)式的輸入， 本

5、程序采用 gets（） 的方法讀入， 將運(yùn)算符 + ，- ，* ， / ， （ ， ） ， #存儲(chǔ)在數(shù)組中時(shí)，定義表達(dá)式求解函數(shù)，在函數(shù)中軟件綜合課程設(shè)計(jì)判斷讀入的字符，如果是運(yùn)算符，將這些字符入操作符optr棧，并比較優(yōu)先級, 判斷是否運(yùn)算。若讀入的字符為0到9'之間的數(shù)字時(shí)，用字符相減轉(zhuǎn)化為 整型，然后將轉(zhuǎn)化后的整型再轉(zhuǎn)化為 ASCII的形式壓入操作數(shù)棧opnd中。四、概要設(shè)計(jì)1、存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本程序主要采用順序棧結(jié)構(gòu)類型(Stack)來存儲(chǔ)表達(dá)式計(jì)算中的數(shù)據(jù)。程 序中需要建立兩個(gè)棧，一個(gè)棧用于寄存運(yùn)算符，另一個(gè)則用于寄存操作數(shù)和計(jì)算 結(jié)果，故需要建立兩個(gè)順序棧結(jié)構(gòu)類型。何一個(gè)表達(dá)式

6、都是由操作符，運(yùn)算符和界限符組成的。我們分別用順序棧來 寄存表達(dá)式的操作數(shù)和運(yùn)算符。棧是限定于緊僅在表尾進(jìn)行插入或刪除操作的線 性表。順序棧的存儲(chǔ)結(jié)構(gòu)是利用一組連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù) 據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置，base為棧底指針, 在順序棧中，它始終指向棧底，即top=base可作為棧空的標(biāo)記，每當(dāng)插入新的 棧頂元素時(shí)，指針top增1,刪除棧頂元素時(shí)，指針top減1。2、算數(shù)優(yōu)先級設(shè)計(jì)對一任意的表達(dá)式，由于表達(dá)式中運(yùn)算符的優(yōu)先級不同， 可能會(huì)使表達(dá)式不 按順序進(jìn)行計(jì)算。在本程序中定義函數(shù) Proceed ()來比較運(yùn)算符的優(yōu)先級，而 函數(shù)中各優(yōu)先級

7、的比較主要根據(jù)以下優(yōu)先級比較的表格：表1:運(yùn)算符優(yōu)先級運(yùn)算符+-*/()#用數(shù)字表示01234156棧內(nèi)操作符的優(yōu)先級3355160棧外操作符的優(yōu)先級2244610在Precede ()函數(shù)中定義兩個(gè)字符型參數(shù)變量 op和c,其中op表示棧頂 運(yùn)算符，c表示當(dāng)前讀入運(yùn)算符，對于當(dāng)前運(yùn)算符是否入棧，進(jìn)行如下操作： 比較當(dāng)前運(yùn)算符和棧頂運(yùn)算符的優(yōu)先級的大?。?、如果當(dāng)前運(yùn)算符的優(yōu)先級大于棧頂運(yùn)算符的優(yōu)先級，即op<c;令函數(shù)返回值為'<,并將當(dāng)前運(yùn)算符進(jìn)optr棧。2、如果當(dāng)前運(yùn)算符的優(yōu)先級小于棧頂運(yùn)算符的優(yōu)先級，即 op>c；令函數(shù)返 回值為少，此時(shí)應(yīng)將棧頂運(yùn)算符出棧和

8、棧頂、次棧頂操作數(shù)出棧并進(jìn)行相應(yīng)的 運(yùn)算。3、如果當(dāng)前元素的優(yōu)先級等于棧頂運(yùn)算符的優(yōu)先級，即op=c；令函數(shù)的返回值為'=',此時(shí)界限符內(nèi)的表達(dá)式已計(jì)算完畢。3 、ADT描述ADT Stack數(shù)據(jù)對象：D=ai | ai C ElemSet,i=1,2,，n, n =0數(shù)據(jù)對象：R1=<ai ,ai>| ay, ai 亡 D ,i=2,，n約定an端為棧頂，ai端為棧底?；静僮鳎篒nitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧SoGetTop(S)初始條件：棧S已存在。操作結(jié)果：用P返回S的棧頂元素。Push(&S , ch)初始條件：棧S已存在。

9、操作結(jié)果：插入元素ch為新的棧頂元素。Pop(&S)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素。In(ch)操作結(jié)果：判斷字符是否是運(yùn)算符，運(yùn)算符即返回 1Precede(c1, c2)初始條件：c1,c2為運(yùn)算符。操作結(jié)果：判斷運(yùn)算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。Operate(a,op,b)初始條件：a,b為整數(shù)，op為運(yùn)算符。操作結(jié)果：a與b進(jìn)行運(yùn)算，op為運(yùn)算符，返回其值：num(n)操作結(jié)果：返回操作數(shù)的長度。EvalExpr()初始條件：輸入表達(dá)式合法。操作結(jié)果：返回表達(dá)式的最終結(jié)果。ADT Stack4、程序模塊設(shè)計(jì)(1)程序模塊本程序主要包含3個(gè)模塊：主程序模塊、計(jì)算模

10、塊以及順序棧操作模塊，調(diào) 用關(guān)系如圖所示：圖1:程序模塊圖(2)系統(tǒng)功能模塊本程序大致包含10個(gè)函數(shù)，其中包含主函數(shù)。每個(gè)函數(shù)都有其相對應(yīng)的功 能實(shí)現(xiàn)。操作符的輸入函數(shù)int In(char c);運(yùn)算符比較優(yōu)先級函數(shù) char Proceed(char op,char c);第5頁共22頁(4實(shí)現(xiàn)表達(dá)式的求值函數(shù)int EvalExpres(void);初始化棧函數(shù) void InitStack(Stack *s);入棧函數(shù) void Push(Stack *s, int x);出棧函數(shù) int Pop(Stack *s);七素函數(shù) int GetTop(Stack *s);判?？蘸瘮?shù) vo

11、id Empty(Stack *s);主函數(shù)int main()(3)函數(shù)之間主要調(diào)用的關(guān)系圖(部分函數(shù)用以上本程序主要包含10個(gè)程序，各程序之間的關(guān)系如圖所示: 的編號(hào)表示)圖2:函數(shù)之間調(diào)用關(guān)系圖五、詳細(xì)設(shè)計(jì)和編碼1、結(jié)構(gòu)體類型的定義typedef structint dataMAXSIZE;軟件綜合課程設(shè)計(jì)int top; / 棧頂int base; / 棧底Stack;2 、全局變量定義/ 以下為函數(shù)聲明void InitStack(Stack *); / 初始化棧int Empty(Stack *); / 判空棧void Push(Stack *, int ); /進(jìn)棧int Pop

12、(Stack *);/ 出棧int GetTop(Stack *); / 取棧頂元素int Operate(int ,char ,int ); /計(jì)算結(jié)果char Proceed(char ,char ); / 比較優(yōu)先級int In(char ); / 判斷輸入符int EvalExpres(void); / 表達(dá)式計(jì)算函數(shù)/ 定義兩個(gè)棧分別存放運(yùn)算符和操作數(shù)Stack StackR,StackD;3 、系統(tǒng)主要子程序的詳細(xì)設(shè)計(jì)(1 )主函數(shù)模塊設(shè)計(jì)int main()/ 主函數(shù)int v;char ch;while (1)算術(shù)表達(dá)式求解*" << endl;cout

13、<< "* v = EvalExpres();cout << " 表達(dá)式的計(jì)算結(jié)果為 :" << v << endl;cout << "Input 'n' to quit and ENTER run again:" << endl; do cin>>ch;if (ch = 'n' | ch = 'N') exit(0); while (ch != 'n');system("cls"

14、;);return 0;在主函數(shù)中， 設(shè)定用戶操作界面的形式， 通過調(diào)用表達(dá)式求解的子函數(shù)實(shí)現(xiàn)算法所要實(shí)現(xiàn)的功能，然后通過while() 循環(huán)語句控制，可以實(shí)現(xiàn)多次調(diào)試。(2 )計(jì)算函數(shù)模塊int Operate(int a, char a1, int b)int s;int d1 = a;int d2 = b; / 把字符ab變?yōu)閷?yīng)數(shù)字switch (a1)case '+':s = d1 + d2;break;case '-':s = d2 - d1;break;case '*':s = d1*d2;break;case '/'

15、;:if (d1 != 0)s = d2 / d1;elsecout << " 除數(shù)不可以為 0!" << endl;exit(0);將運(yùn)算結(jié)果轉(zhuǎn)化為 ascii 碼的形式入棧，return (s + '0'); / 在計(jì)算函數(shù)中，定義3 個(gè)變量，表示基本運(yùn)算中的變量。采用開關(guān)語句實(shí)現(xiàn)表達(dá)式的基本運(yùn)算，將運(yùn)算結(jié)果轉(zhuǎn)化為 ASCII 的形式返回。(3 )表達(dá)式求解的函數(shù)模塊表達(dá)式求解函數(shù)int EvalExpres(void) / int a, b, i = 0, s = 0;char c80, r;InitStack(&Sta

16、ckR);Push(&StackR, '#');InitStack(&StackD);cout << " 請輸入表達(dá)式并以#結(jié)束：" << endl;gets(c);while (ci != '#' | GetTop(&StackR) != '#')if (!In(ci) / 判斷讀入的字符不是運(yùn)算符是則進(jìn)棧第 9 頁 共 22 頁if (ci >= '0' && ci <= '9') s += ci - '0&

17、#39; / 字符相減將字符型轉(zhuǎn)化為整型while (!In(c+i) / 繼續(xù)判斷下一個(gè)字符，若不是運(yùn)算 符，表明為多位數(shù)，直到讀取到字符為運(yùn)算符為止s *= 10;s += ci - '0'Push(&StackD, s + '0'); / 將整型轉(zhuǎn)化為 ascii 的形式入棧， 使字符在棧內(nèi)以 ascii 的形式保存，實(shí)現(xiàn)多位數(shù)的計(jì)算s = 0;/ 初始化s,繼續(xù)判斷 elsecout << " 你輸入的表達(dá)式有誤!" << endl;exit(0);elseswitch (Proceed(GetTop(

18、&StackR), ci) / 此函數(shù)用來比較讀 取的運(yùn)算符和棧頂運(yùn)算符的優(yōu)先級case '<': / 棧頂?shù)脑貎?yōu)先級低，當(dāng)前運(yùn)算符入棧Push(&StackR, ci);i+;break;case '=':Pop(&StackR);i+;break;case '>': / 棧頂?shù)膬?yōu)先級高則出棧，并將計(jì)算結(jié)果壓入棧內(nèi)r = Pop(&StackR);a = Pop(&StackD) - '0' / 操作數(shù)在棧內(nèi)以 ascii 的形式存儲(chǔ)， 出站后要將ascii 轉(zhuǎn)化為整型，然后

19、進(jìn)行運(yùn)算b = Pop(&StackD) - '0'Push(&StackD, Operate(a, r, b);break;return (GetTop(&StackD) - '0'); /將棧頂元素轉(zhuǎn)化為整型的形式輸出 對于表達(dá)式求解函數(shù)， 在程序中主要思想是對讀入的表達(dá)式進(jìn)棧進(jìn)行判斷。若讀入的是 0到9之間的字符，將這些字符采用ascii 相減的形式轉(zhuǎn)化為軟件綜合課程設(shè)計(jì)整型，再入opnd棧，若讀入的字符為運(yùn)算符，則將運(yùn)算符入棧，并比較運(yùn)算符 之間的優(yōu)先級，看是否運(yùn)算，若棧頂?shù)倪\(yùn)算符小于當(dāng)前輸入的運(yùn)算符， 則不需運(yùn) 算，只要將當(dāng)前運(yùn)

20、算符入棧即可。否則，運(yùn)算。運(yùn)算時(shí)先將optr棧的棧頂運(yùn)算符和opnd棧的棧頂、次棧頂元素出棧，并將opnd棧中出棧的元素的ASCII形式 轉(zhuǎn)化為整型再計(jì)算，最后講計(jì)算結(jié)果再轉(zhuǎn)化為 ASCII碼的形式壓入opnd棧中。 使表達(dá)式求解函數(shù)返回值為opnd的棧頂元素。六、上級調(diào)試過程1、遇到問題以及解決方案問題1、調(diào)試時(shí)沒有錯(cuò)誤，但運(yùn)行時(shí)顯示錯(cuò)誤。解決方案：通過它提示的錯(cuò)誤和警告，在判斷是否為運(yùn)算符的子函數(shù)中出現(xiàn)錯(cuò)誤， 如果為運(yùn)算符時(shí)返回1,其次返回0,在返回0時(shí)沒有用else ,這樣使得整個(gè)子 函數(shù)可以返回一個(gè)有效值。問題2、調(diào)試時(shí)程序顯示沒有錯(cuò)誤，可以運(yùn)行，但在運(yùn)行時(shí)結(jié)果卻出現(xiàn)錯(cuò)誤。 解決方案：

21、把程序從頭看了一遍，發(fā)現(xiàn)在比較優(yōu)先級的函數(shù)中，優(yōu)先級的比較比 較亂，而且部分出錯(cuò)，后來查了關(guān)于運(yùn)算符優(yōu)先級的資料， 通過在紙上把各種優(yōu) 先級列出，解決這個(gè)錯(cuò)誤。2、算法的時(shí)間復(fù)雜度由于在主函數(shù)用到嵌套循環(huán)，故算法的時(shí)間復(fù)雜度為O (nA2)03、測試結(jié)果及其分析(1)實(shí)現(xiàn)基本的加減乘除運(yùn)算，當(dāng)想要繼續(xù)輸入表達(dá)式時(shí)點(diǎn)擊 enter鍵，若 要結(jié)束，點(diǎn)擊n或N鍵即可，而且可實(shí)現(xiàn)多位數(shù)的運(yùn)算。強(qiáng) ,C:Progra» FilesMicrosoft Visual StudioMyPrnjects123456Debug123. . . | | |請輸入表達(dá)式邪以次結(jié)劇I6633#I表達(dá)式的計(jì)算結(jié)

22、果為: 2178Input *nJ to quit and ENTER run again：(2)實(shí)現(xiàn)復(fù)雜的算術(shù)表達(dá)式C: ProgiaM FilesXMicrosoft Visual StudioMyProject s123456Debug123.日團(tuán)口情輸入表達(dá)式舁以菇焉h2-<3*4>Z7*2*3tt國達(dá)武的計(jì)算結(jié)果為打7Input 'n' to quit and ENTER run in ：(3)錯(cuò)誤表達(dá)式的處理二口區(qū)輸入的表達(dá)式有誤，Press any key to continue卜NHMMN苴算術(shù)表3古式求 情輸入表達(dá)式舁以，結(jié)54、用戶使用說明(1)

23、本程序執(zhí)行的文件為“算數(shù)表達(dá)式的求解問題”。(2)所求表達(dá)式中都只是僅包含加、減、乘、除 4種基本運(yùn)算的，其中也包 含括號(hào)的應(yīng)用，所有的運(yùn)算對象均為簡單變量，要求將表達(dá)式中的數(shù)字字符轉(zhuǎn)化 為整型，且輸入表達(dá)式以“ #"結(jié)束。(3)輸入表達(dá)式時(shí)，以#結(jié)束，當(dāng)點(diǎn)擊回車鍵時(shí)即可得到運(yùn)算結(jié)果，當(dāng)想 繼續(xù)輸入表達(dá)式時(shí)，再次點(diǎn)擊回車鍵即可，當(dāng)想結(jié)束時(shí)，點(diǎn)擊字母n'或N'(4)當(dāng)輸入錯(cuò)誤表達(dá)式時(shí)，程序會(huì)給出相應(yīng)的提醒。七、總結(jié)與心得C+拜口大二學(xué)到的數(shù)據(jù)結(jié)構(gòu)。課設(shè)題同時(shí)要求程序設(shè)計(jì)者有較強(qiáng)的思維這次課程設(shè)計(jì)讓我更加了解大一學(xué)到的 目要求不僅要求對課本知識(shí)有較深刻的了解, 和動(dòng)手能力

24、和更加了解編程思想和編程技巧。這次課程設(shè)計(jì)讓我有一個(gè)深刻的體會(huì)， 那就是細(xì)節(jié)決定成敗，編程最需要的 是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都不過分，往往檢查了半天發(fā)現(xiàn)錯(cuò)誤發(fā)生在某個(gè)括號(hào)， 分號(hào), 引號(hào)，或者數(shù)據(jù)類型上。就像我在寫 EvalExpres()函數(shù)時(shí)，忘了指針的地址符 值不用加*號(hào)，這一點(diǎn)小小的錯(cuò)誤也耽誤了我?guī)资昼?，所以說細(xì)節(jié)很重要。程序設(shè)計(jì)時(shí)，也不要怕遇到錯(cuò)誤，在實(shí)際操作過程中犯的一些錯(cuò)誤還會(huì)有意 外的收獲，感覺課程設(shè)計(jì)很有意思。在具體操作中這學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的理論 知識(shí)得到鞏固，達(dá)到課程設(shè)計(jì)的基本目的，也發(fā)現(xiàn)自己的不足之出，在以后的上 機(jī)中應(yīng)更加注意，同時(shí)發(fā)現(xiàn)上機(jī)的重要作用，特別算術(shù)表達(dá)式有了深

25、刻的理解。通過實(shí)際操作，我也發(fā)現(xiàn)我的好多不足之處：(1)用棧的結(jié)構(gòu)來解決表達(dá)式的求值，首先要解決的問題是如何將人們習(xí)慣書 寫的表達(dá)式轉(zhuǎn)換成計(jì)算機(jī)容易處理的表達(dá)式。 開始有些茫然，后來通過結(jié)合課本 和同學(xué)的幫助完成了該課題。(2)對一些看似簡單的東西掌握不夠熟練，比如由于函數(shù)的調(diào)用參數(shù)問題不熟第11頁共22頁軟件綜合課程設(shè)計(jì)而造成了調(diào)試的困難。對于語法的掌握也欠缺成熟，需要進(jìn)一步掌握。（3） 棧的結(jié)構(gòu)理解不夠清晰， 造成了設(shè)計(jì)程序時(shí)理不清頭緒， 需要對數(shù)據(jù)結(jié)構(gòu)有更深層次的理解。八、參考文獻(xiàn)1 王昆侖 、李紅主編，數(shù)據(jù)結(jié)構(gòu)與算法，北京：中國鐵道出版社， 2007 年 5 月2阮宏一、魯靜主編，數(shù)據(jù)

26、結(jié)構(gòu)課程設(shè)計(jì)（C/C+苗述），北京：電子工業(yè)出 版社， 2011 年 1 月3嚴(yán)蔚敏、吳偉民主編數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社20024殷人昆等著數(shù)據(jù)結(jié)構(gòu)（C+R）清華大學(xué)出版社2001附錄(源程序) ：#include <iostream> using namespace std;#define MAXSIZE 16typedef structint dataMAXSIZE;int top;int base; / 棧底Stack; / 順序棧的定義/ 以下為函數(shù)聲明void InitStack(Stack *); / 初始化棧int Empty(Stack *); / 判空棧

27、void Push(Stack *, int); / 進(jìn)棧int Pop(Stack *);/ 出棧int GetTop(Stack *); / 取棧頂元素int Operate(int, char, int); /計(jì)算結(jié)果char Proceed(char, char); / 比較優(yōu)先級 int In(char); /判斷輸入符int EvalExpres(void); /表達(dá)式計(jì)算函數(shù)/ 定義兩個(gè)棧分別存放運(yùn)算符和操作數(shù)Stack StackR, StackD;int main()/ 主函數(shù)int v;char ch;while (1)第 21 頁 共 22 頁cout <<”

28、*算術(shù)表達(dá)式求解*" << endl;v = EvalExpres();cout << " 表達(dá)式的計(jì)算結(jié)果為 :" << v << endl;cout << "Input 'n' to quit and ENTER run again:" << endl; do cin>>ch;if (ch = 'n' | ch = 'N') exit(0); while (ch != 'n'); system(

29、"cls");return 0; void InitStack(Stack *s) / 初始化棧s->top = 0;s->base = 0;int Empty(Stack *s)/ 判斷棧是否為空if (s->top = s->base)return 1; / ?？諘r(shí)返回 1，否則返回 0 elsereturn 0;void Push(Stack *s, int x) / 進(jìn)棧if (s->top = MAXSIZE)cout << "error" << endl;exit(0); elses-&g

30、t;datas->top = x;s->top+;int Pop(Stack *s)/ 出棧int e;if (Empty(s)cout << "error" << endl;exit(0);elses->top-;e = s->datas->top;return e;int GetTop(Stack *s) / 取棧頂元素if (Empty(s)cout << "error" << endl;exit(0);elsereturn s->datas->top - 1

31、;int EvalExpres(void) /表達(dá)式求解函數(shù)int a, b, i = 0, s = 0;char c80, r;InitStack(&StackR);Push(&StackR, '#');InitStack(&StackD);cout << " 請輸入表達(dá)式并以#結(jié)束：" << endl;gets(c);while (ci != '#' | GetTop(&StackR) != '#')if (!In(ci) / 判斷讀入的字符不是運(yùn)算符是則進(jìn)棧if (

32、ci >= '0' && ci <= '9')s += ci - '0' / 字符相減將字符型轉(zhuǎn)化為整型while (!In(c+i) / 繼續(xù)判斷下一個(gè)字符，若不是運(yùn)算符，表明為多位數(shù)，直到讀取到字符為運(yùn)算符為止s *= 10;s += ci - '0'Push(&StackD, s + '0'); / 將整型轉(zhuǎn)化為 ascii 的形式入棧，使字符在棧內(nèi)以 ascii 的形式保存，實(shí)現(xiàn)多位數(shù)的計(jì)算s = 0;/ 初始化s,繼續(xù)判斷 elsecout << "

33、; 你輸入的表達(dá)式有誤!" << endl;exit(0);elseswitch (Proceed(GetTop(&StackR), ci) / 此函數(shù)用來比較讀取的運(yùn)算符和棧頂運(yùn)算符的優(yōu)先級case '<': / 棧頂?shù)脑貎?yōu)先級低，當(dāng)前運(yùn)算符入棧Push(&StackR, ci);i+;break;case '=':Pop(&StackR);i+;break;case '>': / 棧頂?shù)膬?yōu)先級高則出棧，并將計(jì)算結(jié)果壓入棧內(nèi)r = Pop(&StackR);a = Pop(&a

34、mp;StackD) - '0' / 操作數(shù)在棧內(nèi)以 ascii 的形式存儲(chǔ)，出站后要將ascii 轉(zhuǎn)化為整型，然后進(jìn)行運(yùn)算b = Pop(&StackD) - '0'Push(&StackD, Operate(a, r, b);break;return (GetTop(&StackD) - '0'); /將棧頂元素轉(zhuǎn)化為整型的形式輸出int In(char c) /判斷C是否為運(yùn)算符是返回1否則返回0char ch7 = '+', '-', '*', '/'

35、, '#', '(', ')' ;int i;for (i = 0; i < 7; i+)if (c = chi)return 1;return 0;char Proceed(char op, char c) /op 為棧頂元素， c 為當(dāng)前讀入的運(yùn)算符 比較二者的優(yōu)先級char ch;if (op = '(' && c = ')' | op = '#' && c = '#')ch = '='else if (op = '

36、+' | op = '-')/*候*/switch (c)'+':'-':')':'#': ch = '>' break;'*':'/':棧頂元素為 + 或 - 的時(shí)case case case case case casecase '(': ch = '<'else if (op = '*' | op = '/') /* 候*/switch (c)'+':'-

37、':'*':'/':')':'#': ch = '>' break;棧頂元素為 * 或 / 的時(shí)case case case case case casecase '(': ch = '<'else if (op = '(')/*switch (c)'+':棧頂元素為 ( 的時(shí)候 */case case case case case case'*':'/':'(': ch = '

38、;<' break;'#':cout << "Error! exit(0);沒有右括號(hào)!" << endl;else if (op = ')')/switch (c)棧頂元素為 ) 的時(shí)候casecasecasecasecase+':1*1.'/':'#': ch = '>' break;case '(':cout << "Error! 括號(hào)匹配錯(cuò)誤 exit(0);else if (op = '#

39、') switch (c)/!" << endl;棧頂元素為#的時(shí)候case '+':case '-':case '*':case '/':case '(': ch = '<' break;case ')':cout << "Error! 沒有左括號(hào)!"exit(0);return ch;<< endl;int Operate(int a, char a1, int b)int s;int d1 = a;

40、int d2 = b; / 把字符ab變?yōu)閷?yīng)數(shù)字switch (a1)case '+':s = d1 + d2;break;case '-':s = d2 - d1;break;case '*':軟件綜合課程設(shè)計(jì)s = d1*d2;break;case '/':if (d1 != 0)s = d2 / d1; elsecout << " 除數(shù)不可以為 0!" << endl;exit(0);return (s + '0'); / 將運(yùn)算結(jié)果轉(zhuǎn)化為 ascii 碼的形式入

41、棧， 第 23 頁 共 22 頁車廂調(diào)度一、問題陳述假設(shè)停在鐵路調(diào)度站入口處白車廂序列的編號(hào)一次為1, 2, 3, 4。設(shè)計(jì)一個(gè)程序，求出所有可能由此輸出的長度為 4的車廂序列。二、問題分析與設(shè)計(jì)車廂調(diào)度問題是實(shí)際生活中的一個(gè)抽象問題， 實(shí)際上其本質(zhì)就是一個(gè)N個(gè)數(shù) 的全排列問題，所謂全排列算法就是對于給定的字符集， 用有效的方法將所有可 能的全排列無重復(fù)無遺漏地枚舉出來。N 個(gè)字符的全體排列之間存在一個(gè)確定的線性順序關(guān)系。所有的排列中除最后一個(gè)排列外，都有一個(gè)后繼；除第一個(gè)排列外都有一個(gè)前驅(qū)。 每一個(gè)排列的后 繼都可以從它的前驅(qū)經(jīng)過最少的變化得到， 全排列的生產(chǎn)算法就是從第一個(gè)排列 開始逐個(gè)生

42、產(chǎn)所有的排列的方法。全排列的生產(chǎn)法通常有幾下幾種：字典排序法：從右往左開始找出第一個(gè)比右邊數(shù)字小的數(shù)字的序號(hào) j ,然后 在以j為基準(zhǔn)再從左往右，找出第一個(gè)比它大的最小的數(shù)，然后這兩個(gè)數(shù)位置對 調(diào)。例如：1 5 4 7 6 32 的下一個(gè)排列是1 56 74 3 2 。鄰位交換法：鄰位對換法中下一個(gè)排列總是上一個(gè)排列某相鄰兩位對換得到 的。例如：以4個(gè)元素的排列為例，將最后的元素 4逐次與前面的元素交換，可 以生成4個(gè)新排列：1 2 3 4、1 243、14 2 3、4 1 2 3 。然后將最后一個(gè)排列 的末尾的兩個(gè)元素交換，再逐次將排頭的4與其后的元素交換，又生成四個(gè)新排 列：4 13 2、143 2、1 3 4 2、1 3 2 4 。冉將最后一個(gè)排列的排頭的兩個(gè)元素 交換，再將4從后往前移：3 1 2 4、3 14 2、34 1 2、4 3 1 2。如此循環(huán)既可 求出全部排列。遞歸類算法： 我將選擇遞歸類算法作為實(shí)現(xiàn)該車廂調(diào)度的主要算法，通過 設(shè)計(jì) perm 遞歸函數(shù)。三、運(yùn)行結(jié)果當(dāng)列車長度為4時(shí)：四、設(shè)計(jì)體會(huì)與總結(jié)遞歸算法是解決問題的一種非常好的方法， 我在網(wǎng)上看到這個(gè)車廂調(diào)度的問題一般用棧來實(shí)現(xiàn)， 但是覺得可以用遞歸來完成， 而且比棧更簡單， 就選擇了用遞歸來完成， 通過這兩周內(nèi)的時(shí)間， 我如期完成了此次的課程設(shè)計(jì)