數(shù)據(jù)結(jié)構(gòu)——算術(shù)表達(dá)式求值算法

1、沈陽(yáng)航空航天大學(xué)課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告課程設(shè)計(jì)名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：算術(shù)表達(dá)式求值算法算術(shù)表達(dá)式求值算法 院（系）：計(jì)算機(jī)學(xué)院專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)：學(xué) 號(hào)：姓 名：指導(dǎo)教師：丁國(guó)輝完成日期：2013年01月11日沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 -目目 錄錄第第 1 章章 概要設(shè)計(jì)概要設(shè)計(jì).11.1 題目的內(nèi)容與要求.11.2 總體結(jié)構(gòu).1第第 2 章章 詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì).32.1 棧的順序存儲(chǔ)模塊.32.2 進(jìn)棧模塊.32.3 出棧模塊.42.4 運(yùn)算模塊.42.5 判斷優(yōu)先級(jí)模塊.52.6 處理表達(dá)式主體模塊.6第第 3 章章 調(diào)試分析調(diào)試

2、分析.8第第 4 章章 運(yùn)行結(jié)果運(yùn)行結(jié)果.9參考文獻(xiàn)參考文獻(xiàn).11附附 錄（程序清單）錄（程序清單）.12沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 第 1 章 概要設(shè)計(jì)-0-第 1 章 概要設(shè)計(jì)1.1 題目的內(nèi)容與要求題目的內(nèi)容與要求內(nèi)容：設(shè)計(jì)程序，其能夠求解任意給定算數(shù)表達(dá)式的值，算數(shù)表達(dá)式中的操作符來(lái)自于集合+，*，表達(dá)式允許包括小括號(hào)“（） ” ，表達(dá)式的輸入以“#”作為結(jié)束標(biāo)志。 要求：1)利用棧結(jié)構(gòu)實(shí)現(xiàn)表達(dá)式求值算法，即在約定的條件下，正確輸入表達(dá)式，經(jīng)過(guò)程序的運(yùn)行之后，給出表達(dá)式的值；2)系統(tǒng)利用 C 語(yǔ)言實(shí)現(xiàn)；3)獨(dú)立完成系統(tǒng)的設(shè)計(jì)、編碼和調(diào)試。1.2 總體結(jié)構(gòu)總體結(jié)構(gòu)本程序主要分為六個(gè)模塊

3、（主要算法模塊圖見(jiàn)圖 1.1）：棧的順序存儲(chǔ)模塊、進(jìn)棧模塊、出棧模塊、運(yùn)算模塊、判斷優(yōu)先級(jí)模塊、處理表達(dá)式主體模塊。棧的順序存儲(chǔ)模塊：分別建立兩個(gè)棧，第一個(gè)用來(lái)存儲(chǔ)運(yùn)算符，第二個(gè)是用來(lái)存儲(chǔ)數(shù)字。進(jìn)棧模塊：運(yùn)算符和數(shù)字分別存儲(chǔ)在運(yùn)算符棧和數(shù)字棧中，以便運(yùn)算時(shí)的調(diào)用。出棧模塊：由于運(yùn)算的需要，就必須把運(yùn)算符和數(shù)字分別從運(yùn)算符棧和數(shù)字棧中取出來(lái)。運(yùn)算模塊：程序在遇到運(yùn)算符的時(shí)候，根據(jù)此模塊的要求進(jìn)行運(yùn)算。判斷優(yōu)先級(jí)模塊：找出棧頂算符和即將入棧算符的對(duì)應(yīng)的下標(biāo)，然后根據(jù)算符間的優(yōu)先關(guān)系表判斷出算符的優(yōu)先關(guān)系。處理表達(dá)式主體模塊：結(jié)合運(yùn)算模塊和判斷優(yōu)先級(jí)模塊，對(duì)表達(dá)式進(jìn)行系統(tǒng)處理，求出算數(shù)表達(dá)式的值。沈

4、陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 第 1 章 概要設(shè)計(jì)-1-算術(shù)表達(dá)式求值算法出棧模塊判斷優(yōu)先級(jí)模塊處理表達(dá)式主體模塊棧的順序存儲(chǔ)模塊運(yùn)算模塊進(jìn)棧模塊圖圖 1.1 主要算法模塊圖主要算法模塊圖沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 第 2 章 詳細(xì)設(shè)計(jì)-2-第 2 章 詳細(xì)設(shè)計(jì)在本次課程設(shè)計(jì)中，我們用到了棧這個(gè)重要的數(shù)據(jù)結(jié)構(gòu)。在實(shí)現(xiàn)程序的功能的時(shí)候，有很多重要的程序段是涉及棧方面的：有棧的結(jié)構(gòu)建立，入棧，出棧。另外還有就是對(duì)表達(dá)式進(jìn)行運(yùn)算，判斷運(yùn)算符的優(yōu)先級(jí)，對(duì)表達(dá)式的主體進(jìn)行處理。重要的程序段如下。 2.1 棧的順序存儲(chǔ)模塊棧的順序存儲(chǔ)模塊本課程設(shè)計(jì)是通過(guò)棧為載體來(lái)實(shí)現(xiàn)程序的功能的，因此棧結(jié)構(gòu)的建立是必不可

5、少的。分別建立兩個(gè)棧，第一個(gè)用來(lái)存儲(chǔ)運(yùn)算符，第二個(gè)用來(lái)存儲(chǔ)數(shù)字。2.2 進(jìn)棧模塊進(jìn)棧模塊主要是把運(yùn)算符和數(shù)字分別存儲(chǔ)在運(yùn)算符棧和數(shù)字棧里面。首先判斷棧是否滿(mǎn)，若不滿(mǎn)就進(jìn)棧，把 e 插入為新的棧頂元素；否則就追加存儲(chǔ)空間。流程圖如圖 2.1 所示。FT開(kāi)始判斷棧是否滿(mǎn)追加存儲(chǔ)空間e 進(jìn)棧為新的棧頂元素結(jié)束圖圖 2.12.1 進(jìn)棧進(jìn)棧模塊流程圖模塊流程圖沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 第 2 章 詳細(xì)設(shè)計(jì)-3-2.3 出棧模塊出棧模塊主要是把運(yùn)算符和數(shù)字分別從運(yùn)算符棧和數(shù)字棧中取出來(lái)。由于運(yùn)算的需要，此時(shí)就必須把運(yùn)算符和數(shù)字從棧中取出來(lái)，即出棧。運(yùn)算符和數(shù)字的出棧，是先取出棧頂元素an。由于取出元素

6、之后，原先的棧頂元素的位置為空了。此時(shí)an-1就成了棧頂元素了，所以原先的棧頂指針就減一，指向現(xiàn)在的棧頂元素an-1。第一個(gè)函數(shù)是運(yùn)算符的出棧，第二個(gè)函數(shù)是數(shù)字的出棧。首先判斷棧是否為空，若棧不空，則刪除S的棧頂元素，用e返回其值；否則返回ERROR。流程圖如圖2.2所示。FT開(kāi)始判斷棧是否空返回 ERROR棧頂元素出棧結(jié)束圖圖2.22.2 出棧出棧模塊流程圖模塊流程圖2.4 運(yùn)算模塊運(yùn)算模塊當(dāng)程序在遇到運(yùn)算符的時(shí)候，就要進(jìn)行運(yùn)算。函數(shù)中a和b就是代表數(shù)字，而theta就是代表運(yùn)算符。當(dāng)出棧時(shí)棧頂元素是“+” （加） ，程序就執(zhí)行加法運(yùn)算，最后的結(jié)果是a和b兩數(shù)之和；當(dāng)出棧時(shí)棧頂元素是“-”

7、（減） ，程序就執(zhí)行減法運(yùn)算，最后的結(jié)果是a和b兩數(shù)之差；當(dāng)出棧時(shí)棧頂元素是“*” （乘） ，程序就執(zhí)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 第 2 章 詳細(xì)設(shè)計(jì)-4-行乘法運(yùn)算，最后的結(jié)果是a和b兩數(shù)之積；當(dāng)出棧時(shí)棧頂元素是“/” （除） ，程序就執(zhí)行除法運(yùn)算，最后的結(jié)果是a和b兩數(shù)之商。函數(shù)的返回值就是函數(shù)最后的結(jié)果。流程圖如圖2.3所示。default/*-+case開(kāi)始theta（運(yùn)算符）a+ba-ba*ba/b錯(cuò)誤結(jié)束圖圖2.32.3 運(yùn)算運(yùn)算模塊流程圖模塊流程圖2.5 判斷優(yōu)先級(jí)模塊判斷優(yōu)先級(jí)模塊由于我們輸入的是四則運(yùn)算，因此就不得不考慮算符的優(yōu)先級(jí)問(wèn)題。先調(diào)用函數(shù)ReturnOpOrd()

8、找出棧頂算符和即將入棧算符的對(duì)應(yīng)的下標(biāo)，然后再調(diào)用precede()函數(shù)，根據(jù)算符間的優(yōu)先關(guān)系表（如表2.4所示）判斷出算符的優(yōu)先關(guān)系：a1a2 a1的優(yōu)先權(quán)高于a2。上述函數(shù)就是判斷優(yōu)先級(jí)的函數(shù)。經(jīng)過(guò)運(yùn)算之后，函數(shù)返回值即為優(yōu)先權(quán)高低。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 第 2 章 詳細(xì)設(shè)計(jì)-5-a2a1*（）#*（#=T開(kāi)始輸入表達(dá)式*c!=#|(GetTop(OPTR,e),e)!= #不是算符數(shù)字進(jìn) OPND棧（存儲(chǔ)數(shù)字的棧）運(yùn)算符進(jìn)OPTR 棧（存儲(chǔ)算符的棧）調(diào)用 ReturnOpOrd()和 precede()函數(shù)判斷優(yōu)先關(guān)系Pop(OPTR,x);c+;（出棧）Pop(OPTR,the

9、ta); Pop(OPND,b); Pop(OPND,a); Push(OPND, Operate(a, theta, b);return (GetTop(OPND,d),d);結(jié)束圖圖 2.52.5 處理表達(dá)式主體處理表達(dá)式主體模塊模塊流程圖流程圖沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 第 3 章 調(diào)試分析-7-第 3 章 調(diào)試分析（1）問(wèn)題：由于輸入時(shí)的疏忽遺漏了“；” 、 “” 、 “） ”等，編譯時(shí)出現(xiàn)錯(cuò)誤。解決方法：通過(guò)編譯器的錯(cuò)誤提示進(jìn)行修改，添加一些遺漏的信息。（2）問(wèn)題：在運(yùn)行時(shí)提示庫(kù)函數(shù)名為未標(biāo)識(shí)符。解決方法：通過(guò)編譯器的錯(cuò)誤提示進(jìn)行修改，缺少頭文件，添加所需的頭文件。（3）問(wèn)題：輸出

10、的數(shù)只能在97以?xún)?nèi),而且只能輸入輸出整數(shù),不能實(shí)現(xiàn)輸入輸出小數(shù)，當(dāng)輸入小數(shù)時(shí)出現(xiàn)錯(cuò)誤解決方法：規(guī)范輸入輸出格式。（4）問(wèn)題：操作數(shù)和運(yùn)算符在一起發(fā)生沖突，當(dāng)混合輸入數(shù)據(jù)和運(yùn)算符，出現(xiàn)異常，沒(méi)有結(jié)果。解決方法：使用兩個(gè)工作棧，一個(gè)存儲(chǔ)數(shù)字，一個(gè)存儲(chǔ)運(yùn)算符。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 第 4 章 使用說(shuō)明-8-第 4 章 運(yùn)行結(jié)果運(yùn)行操作及結(jié)果：（1）顯示輸入表達(dá)式,以#號(hào)結(jié)束。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 第 4 章 使用說(shuō)明-9-（2）正確輸入表達(dá)式,以#號(hào)結(jié)束，就能得到表達(dá)式的值。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 參考文獻(xiàn)-10-參考文獻(xiàn)1 嚴(yán)蔚敏,吳偉明.數(shù)據(jù)結(jié)構(gòu)（C 語(yǔ)言版）M.北京:清華

11、大學(xué)出版社,20072 王敬華，林萍，張清國(guó).C 語(yǔ)言程序設(shè)計(jì)教程M（第二版）.北京:清華大學(xué)出版社,2009.83 吳海燕,任午令,章志勇.數(shù)據(jù)結(jié)構(gòu)M.杭州:浙江大學(xué)出版社,2011.64 胡圣榮,周靄如,羅穗萍.數(shù)據(jù)結(jié)構(gòu)教程與題解M.北京:清華大學(xué)出版社,2011.95 譚浩強(qiáng).C 程序設(shè)計(jì)試題匯編M.北京:清華大學(xué)出版社,2006.36 李兵,崔虹燕,馬曉亭.C 語(yǔ)言程序設(shè)計(jì)M.北京:科學(xué)出版社,2011 沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 附錄-11-附 錄（程序清單）#include#include#includeint InitStack(StackChar &S)int Push(St

12、ackChar &S, char e)int Pop(StackChar &S,char &e)int GetTop(StackChar S,char &e)unsigned char str77 =, , ,=;char OPSET7=+ , - , * , / ,( , ) , #;float EvaluateExpression(char* k)StackChar OPTR;StackFloat OPND;char T20;float Data,a,b;char theta,*c,x,str2;沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 附錄-12-char e;float d;InitStack (

13、OPTR);Push (OPTR, #);InitStack (OPND);c = k;strcpy(T,0);while (*c!= #|(GetTop(OPTR,e),e)!= #)if (!In(*c, OPSET)str0=*c;str1=0;strcat(T,str);c+;if(In(*c,OPSET)Data=(float)atof(T);Push(OPND, Data);strcpy(T,0);elseswitch (precede(GetTop(OPTR,e),e), *c)case : Pop(OPTR, theta);Pop(OPND, b);Pop(OPND, a);P

14、ush(OPND, Operate(a, theta, b);break;return (GetTop(OPND,d),d);float Operate(float a,unsigned char theta, float b)switch(theta)case +:return a+b;case -:return a-b;case *:return a*b;case /:沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 附錄-14-return a/b;default:return 0;int In(char Test,char* TestOp)int ReturnOpOrd(char op,char* Tes

15、tOp)int i;for(i=0;i7;i+)if (op=TestOpi) return i;return 0;char precede(char A, char B)return strReturnOpOrd(A,OPSET)ReturnOpOrd(B,OPSET);void main()char k100;float result;printf(輸入表達(dá)式,以#號(hào)結(jié)束:n);gets(k);result=EvaluateExpression(k);printf(%.2fn,result);沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告-15-課程設(shè)計(jì)總結(jié)：課程設(shè)計(jì)總結(jié)：這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，從理論到實(shí)踐

16、，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)有了更深刻的認(rèn)識(shí)，也學(xué)到了很多東西，不僅鞏固了以前所學(xué)過(guò)的知識(shí)，而且還學(xué)到了很多書(shū)本上所沒(méi)有的內(nèi)容。我在此次課程設(shè)計(jì)中深刻體會(huì)到了要寫(xiě)好一個(gè)程序必須弄清它的最基本的思路，除此之外要有算法思路，會(huì)寫(xiě)一些基本函數(shù)。編程不像做其它事，它要求編程人員有非?？b密的思維，很好的整體把握能力和很好的調(diào)試程序的能力等，也要特別注重細(xì)節(jié)。我在編寫(xiě)程序過(guò)程中遇到了很多的問(wèn)題，一些基本的函數(shù)應(yīng)用不熟練，讓我發(fā)現(xiàn)了自己的知識(shí)的匱乏，掌握的不夠牢固，懂得了只學(xué)書(shū)本上的東西是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，才能真正的學(xué)到東西，才能提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考能力。在程序運(yùn)行成功的時(shí)候，我的心里是非常喜悅的，這些天的努力終于有了回報(bào)。在