利用棧實現(xiàn)表達式求解

1、理學(xué)院課程設(shè)計說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法A設(shè)計實踐課 程 代 碼: 6015059 題 目 二: 利用棧實現(xiàn)表達式求解 開 始 時 間: 2015 年 12 月 28 日完 成 時 間: 2016 年 01 月 10 日課程設(shè)計成績：學(xué)習(xí)態(tài)度及平時成績（30）技術(shù)水平與實際能力（20）創(chuàng)新（5）說明書撰寫質(zhì)量（45）總 分（100）指導(dǎo)教師簽名： 年 月 日西華大學(xué)理學(xué)院課程設(shè)計說明書數(shù)據(jù)結(jié)構(gòu)與算法A設(shè)計實踐任務(wù)書學(xué)院名稱： 理學(xué)院 課程代碼：_6015059_專業(yè)： 信科 年級： 2012 一、設(shè)計題目 利用棧實現(xiàn)表達式求解（限最多1人完成）二、主要內(nèi)容使用棧來解決表達式中的求解

2、優(yōu)先問題三、具體要求及提交的材料利用教材3.2.5節(jié)的理論實現(xiàn)表達式求解。 （1）只考慮+、-、*、/四種數(shù)學(xué)運算（2）只考慮圓括號（ ）參與運算測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；必須上機調(diào)試通過l按數(shù)據(jù)結(jié)構(gòu)課程設(shè)計大綱中的要求完成課程設(shè)計報告格式。 設(shè)計結(jié)束后，每個學(xué)生必須上交的材料有：1 課程設(shè)計報告打印稿一份 2課程設(shè)計的源代碼電子文檔一份四、主要技術(shù)路線提示根據(jù)運算符號的優(yōu)先級來決定當(dāng)前符號是否入棧；注意考慮多重括號匹配的問題。五、進度安排共計兩周時間，建議進度安排如下：1 選題，應(yīng)該在上機實驗之前完成 2. 需求分析、概要設(shè)計可分配4學(xué)時完成2 詳細設(shè)計可分配4學(xué)時 4. 調(diào)試

3、和分析可分配10學(xué)時。2學(xué)時的機動，可提前安排部分提前結(jié)束任務(wù)的學(xué)生答辯六、 推薦參考資料1. 馮博琴 等編著，軟件技術(shù)基礎(chǔ)（修改版），西安交通大學(xué)出版社，19972. 嚴蔚敏 等著，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，20033. 李蕓芳 等著，軟件技術(shù)基礎(chǔ)（第二版），清華大學(xué)出版社，20004. 徐孝凱 等著，數(shù)據(jù)結(jié)構(gòu)（C語言描述），清華大學(xué)出版社，2004指導(dǎo)教師 簽名日期 年 月 日系 主 任 審核日期 年 月 日目 錄摘 要11 引 言22 系統(tǒng)分析32.1功能要求32.1.1 總體要求32.1.2本人所做模塊32.2 數(shù)據(jù)需求33詳細設(shè)計與實現(xiàn)33.1設(shè)計思路33.2整體設(shè)計方案43.3主函

4、數(shù)53.4編碼54系統(tǒng)測試：114.1設(shè)計測試數(shù)據(jù)114.2測試結(jié)果及分析12結(jié) 論13致 謝15參考文獻16附錄17利用棧實現(xiàn)表達式求解摘 要隨著計算機的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值運算，數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)就是為以后利用計算機資源高效地開發(fā)非數(shù)值處理的計算機程序打下堅實的理論、方法和技術(shù)基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)與算法旨在分析研究計算機加工的數(shù)據(jù)對象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，從而使建立在其上的解決問題的算法達到最優(yōu)。棧是一種重要的線性結(jié)構(gòu)，?？梢杂米鲾?shù)制轉(zhuǎn)換、括號匹配的檢驗、行編輯程序等等問題中。從數(shù)據(jù)結(jié)構(gòu)角度看，棧也是線性表，其特殊性在于棧的基本操作是線性表操作的

5、子集，它是操作受限的線性表，因此，可稱為限定性的數(shù)據(jù)結(jié)構(gòu)。但從數(shù)據(jù)類型角度看，它是和線性表大不相同的兩類重要的抽象數(shù)據(jù)類型。棧實限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂，相應(yīng)地，表頭端稱為棧底。不含元素的空表稱為空棧。棧又稱為后進先出的線性表。這次的課程設(shè)計是利用棧實現(xiàn)表達式求解，要求只考慮+、-、*、/四種數(shù)學(xué)運算還有只考慮圓括號參與運算。關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)與算法， 棧， 表達式求解，最優(yōu)1 引 言 1.1問題的提出棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照后進先出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底,最后的數(shù)據(jù)在棧

6、頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。在計算機科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象（數(shù)據(jù)元素）以及它們之間的關(guān)系和運算等的學(xué)科，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是重要地實踐性教學(xué)環(huán)節(jié)。在進行了程序設(shè)計語言課和 數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)的基礎(chǔ)上，設(shè)計實現(xiàn)相關(guān)的數(shù)據(jù)結(jié)構(gòu)經(jīng)典問題，有助于加深對數(shù)據(jù)結(jié)構(gòu)課程的認識。本課程設(shè)計是數(shù)據(jù)結(jié)構(gòu)中的一個關(guān)于用棧實現(xiàn)表達式求解，棧是計算機中常用的一種數(shù)據(jù)結(jié)構(gòu)，具有廣泛的使用。利用棧的性質(zhì)及其操作原理編寫

7、一個使用棧計算表達式的程序有助于更好的掌握棧的使用規(guī)則和原理應(yīng)用。1.2 C語言C語言既有高級語言的特點，又具有匯編語言的特點；既是一個成功的系統(tǒng)設(shè)計語言，有時一個使用的程序設(shè)計語言；既能用來編寫不依賴計算機硬件的應(yīng)用程序，又能用來編寫各種系統(tǒng)程序；是一種受歡迎、應(yīng)用廣泛的程序設(shè)計語言。1.3 C語言發(fā)展過程1973年，美國貝爾實驗室的D.M.RITCHIE在B語言的基礎(chǔ)上最終設(shè)計出了一種新的語言，他取了BCPL的第二個字母作為這種語言的名字，這就是C語言。1977年Dennis M.Ritchie 發(fā)表了不依賴于具體機器系統(tǒng)的C語言編譯文本可移植的C語言編譯程序。1978年Brian W.K

8、ernighian和Dennis M.Ritchie出版了名著The C Programming Language，從而使C語言成為目前世界上流行最廣泛的高級程序設(shè)計語言。1.4任務(wù)與分析本程序用于解決一個可以帶括號的表達式求值的問題，要運用到棧，而且會用到一種簡單直觀，廣為使用的算法，通常稱為“算符優(yōu)先法”。進行表達式求值首先要了解算術(shù)四則運算的規(guī)則。即：(1）先乘除，后加減；（2）從左算到右；（3）先括號內(nèi)后括號外；算符優(yōu)先法根據(jù)這個算符優(yōu)先關(guān)系的規(guī)定來實現(xiàn)對表達式的編譯或解釋執(zhí)行的。任何一個表達式都是由操作數(shù)、運算符和界限符組成。2 系統(tǒng)分析2.1功能要求2.1.1 總體要求利用教材3.

9、2.5節(jié)的理論實現(xiàn)表達式求解。（1）只考慮+、-、*、/四種數(shù)學(xué)運算（2）只考慮圓括號（ ）參與運算2.1.2本人所做模塊根據(jù)這次課程設(shè)計題目的要求，將這次任務(wù)分為了幾個小的模塊，具體模塊的功能如下：Push(&S,e)：入棧函數(shù)模塊Pop(&S,&e)：出棧函數(shù)模塊In(Test,* TestOp)：判斷是否為運算符Operate(a,theta,b) ：根據(jù)theta對a、b進行四則運算操作ReturnOpOrd(op,* TestOp) ：若TestOp為運算符，則返回此運算符在數(shù)組的下標(biāo)precede( Aop, Bop) ：根據(jù)運算符優(yōu)先級表返回Aop與Bop之間的優(yōu)先級Evalua

10、teExpression() ：用運算符優(yōu)先級對算術(shù)表達式求值最后，通過主函數(shù)對以上幾個函數(shù)的調(diào)用，實現(xiàn)該系統(tǒng)的功能。2.2 數(shù)據(jù)需求輸入一個表達式，利用優(yōu)先級表對表達式求值。3詳細設(shè)計與實現(xiàn)3.1設(shè)計思路為了實現(xiàn)算符優(yōu)先算法使用兩個工作棧，一個稱作OPTR，以寄存運算符；另一個稱作OPND，用以寄存操作數(shù)或運算結(jié)果。在操作數(shù)和操作符入棧前，通過一個函數(shù)來判別，輸入的是操作數(shù)還是操作符，操作數(shù)入OPND，操作符入OPTR。在輸入表達式的最后輸入#，設(shè)定#的優(yōu)先級最低，代表表達式輸入結(jié)束。在表達式輸入過程中，遇操作數(shù)則直接入棧，遇到運算符則與棧頂運算符比較優(yōu)先級,若當(dāng)前運算符優(yōu)先級高，則當(dāng)前運算

11、符入棧,掃描下一符號;否則棧頂運算符出棧,兩操作數(shù)出棧,進行運算,所得結(jié)果入數(shù)棧,重新比較當(dāng)前運算符與新棧頂運算符。如此重復(fù)直到棧頂運算符與當(dāng)前符號均為#，運算結(jié)束。3.2整體設(shè)計方案 ReturnOpOrdtmainPopprecedePushInEvaluateExpressionOperate輸出圖1調(diào)用關(guān)系圖通過以上的關(guān)系圖，可以從中看出系統(tǒng)的流程以及函數(shù)之間的調(diào)用關(guān)系。3.3主函數(shù)/=通過該函數(shù)對其他函數(shù)的調(diào)用，實現(xiàn)系統(tǒng)功能int _tmain(int argc, _TCHAR* argv)int nResult,n;while(1)manu();coutendl;coutn;swi

12、tch(n)case 1:puts ( * ); puts ( 請輸入一個運算式，以#結(jié)尾： );printf(n);nResult = EvaluateExpression();printf(n);printf ( 運算結(jié)果是：%dn, nResult );printf(n);break;case 0:exit(0);break;return 0;3.4編碼 /=預(yù)定義 #define ok 1 #define error 0 #define overflow -1#define OPSETSIZE 7#define STACKINCREMENT 100#define STACK_INIT_

13、SIZE 10/=定義順序棧結(jié)構(gòu)模板template struct SqStackT *top; T *base;int stacksize; /=初始化棧函數(shù)模板template /傳進來的 T1，T2生成對應(yīng)的類Status InitStack(T1 &S)S.base=(T2 *)malloc(STACK_INIT_SIZE*sizeof(T2);if(!S.base) exit (overflow);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return ok;/=入棧函數(shù)模板template Status Push(T1 &S,T2 e)if(

14、S.top-S.base=S.stacksize)S.base=(T2 *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(T2);if(!S.base) exit (overflow);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return ok; /=出棧函數(shù)模板template Status Pop(T1 &S,T2 &e)if(S.top=S.base) return error;e=*-S.top;return ok; /=獲取棧頂元素模板temp

15、late T2 GetTop(T1 S)if(S.top=S.base)return error;else return *(S.top-1);/=判斷是否為運算符typedef int Status;Status In(char Test,char* TestOp) bool Find=false; for (int i=0; i, /*-*/, /*/, /*/*/, /*(*/, , /*#*/, ,=, ; /=對兩操作數(shù)進行運算float Operate(float a,unsigned char theta, float b) switch(theta) case +: retur

16、n a+b;case -: return a-b;case *: return a*b;case /: return a/b;default : return 0; /運算 /=求解表達式float EvaluateExpression() / 算術(shù)表達式求值的算符優(yōu)先算法。 / 設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧，OPSET為運算符集合。SqStack OPTR; / 運算符棧，字符元素 SqStack OPND; / 運算數(shù)棧，實數(shù)元素 char TempData20; float Data,a,b; char theta,c,x,Dr2; InitStackSqStack,ch

17、ar (OPTR); Push (OPTR, #); InitStack SqStack,float(OPND); strcpy(TempData,0);/將TempData置為空 c=getchar(); while (c!= # | GetTopSqStack,char(OPTR)!= #) if (!In(c, OPSET) Dr0=c;Dr1=0;/存放單個數(shù)strcat(TempData,Dr);/將單個數(shù)連到TempData中，形成字符串c=getchar();if(In(c,OPSET)/如果遇到運算符，則將字符串TempData轉(zhuǎn)換成實數(shù)，入棧，并重新置空 Data=(floa

18、t)atof(TempData); Push(OPND, Data); strcpy(TempData,0); else / 是運算符則進棧switch (precede(GetTopSqStack,char(OPTR), c) case : / 退棧并將運算結(jié)果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch / while return GetTopSqStack,float(OPND); / EvaluateExpression 4系統(tǒng)測試：運

19、行程序，顯示系統(tǒng)主界面，如圖2所示：圖2 界面顯示4.1設(shè)計測試數(shù)據(jù)輸入表達式以#結(jié)尾，如圖3所示：圖3 輸入表達式4.2測試結(jié)果及分析按erter顯示結(jié)果，如圖4所示：圖4 結(jié)果顯示分析：程序?qū)懗鰜砗?，也調(diào)試了沒有錯誤，但是測試的時候有時能出來結(jié)果，但是有時候什么反應(yīng)也沒有，問同學(xué)也不能找出錯在哪里，很無奈，不知道錯在哪里就根本不知道怎么改，但是我覺得程序應(yīng)該沒有錯誤，后來在一次無意的測試中發(fā)現(xiàn)調(diào)試不出的情況中在鍵入數(shù)字時，測試界面底部有出現(xiàn)此字符“半：”而且括號也是中文環(huán)境下的括號，經(jīng)過反復(fù)測試知道在鍵入表達式時應(yīng)該保證是在英文環(huán)境下，才能出現(xiàn)結(jié)果。結(jié) 論 課程設(shè)計做完了，剛看題目還覺得沒

20、有什么問題，可是這正做了才知道問題大了。細節(jié)等各方面沒有考慮到的問題都出現(xiàn)了。做課程設(shè)計的過程就是一個不斷調(diào)試不斷改進程序的過程。經(jīng)過學(xué)習(xí)，加上自己課外的時間，使我對C語言有了更進一步的認識和了解，要想學(xué)好它要重在實踐，要通過不斷的上機操作才能更好地學(xué)習(xí)它，通過實踐，我也發(fā)現(xiàn)我的好多不足之處，對C語言學(xué)習(xí)平時只是馬馬虎虎的過去了，真正自己去解決實際問題的時候才會發(fā)現(xiàn)自己學(xué)的多么糟糕，通過課程設(shè)計對自己的編程能力也有所提高；再有對C語言的一些標(biāo)準(zhǔn)庫函數(shù)不太了解，還有對函數(shù)調(diào)用的正確使用不夠熟悉，還有對C語言中經(jīng)常出現(xiàn)的錯誤也不了解，通過實踐，使我在這幾個方面的認識有所提高。通過實踐的學(xué)習(xí)，我認到

21、學(xué)好計算機要重視實踐操作，不僅僅是學(xué)習(xí)C語言，還是其它的語言，以及其它的計算機方面的知識都要重在實踐，所以后在學(xué)習(xí)過程中，我會更加注重實踐操作能力的培養(yǎng)，無論學(xué)習(xí)什么，親自動手去做了才能得到最深刻的體會。致 謝本次課程設(shè)計能夠順利完成，首先感謝我的老師，老師在我的課程設(shè)計過程中提出了指導(dǎo)性的方案和架構(gòu)，并指引我閱讀相關(guān)的資料和書籍，使我在不熟悉的領(lǐng)域中仍能迅速掌握新的技術(shù)。第二，我要感謝我的數(shù)據(jù)結(jié)構(gòu)老師，在以往的基礎(chǔ)課學(xué)習(xí)中為我打下良好的基礎(chǔ)，這是我這次課程設(shè)計能夠順利完成的前提。我的同學(xué)也對我進行了一系列的幫助，沒有他們，也許就難以發(fā)現(xiàn)一些潛在的錯誤，在此表示感謝。參考文獻1嚴蔚敏、吳偉民.

22、數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社.20022殷人昆等.數(shù)據(jù)結(jié)構(gòu)（C+版）.清華大學(xué)出版.20013金遠平.數(shù)據(jù)結(jié)構(gòu)（C+描述）.清華大學(xué)出版社.20054許卓群等.數(shù)據(jù)結(jié)構(gòu)與算法.高等教育出版社.2004附錄#include StdAfx.h#include#include #include #include#include/=調(diào)用庫函數(shù)#define ok 1 #define error 0 #define overflow -1#define OPSETSIZE 7#define STACKINCREMENT 100#define STACK_INIT_SIZE 10/=預(yù)定義temp

23、late struct SqStackT *top; T *base;int stacksize;/=順序棧結(jié)構(gòu)模板typedef int Status;template /傳進來的 T1，T2生成對應(yīng)的類Status InitStack(T1 &S)S.base=(T2 *)malloc(STACK_INIT_SIZE*sizeof(T2);if(!S.base) exit (overflow);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return ok;/=初始化棧函數(shù)模板template Status Push(T1 &S,T2 e)if(S.t

24、op-S.base=S.stacksize)S.base=(T2 *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(T2);if(!S.base) exit (overflow);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return ok;/=入棧函數(shù)模板template Status Pop(T1 &S,T2 &e)if(S.top=S.base) return error;e=*-S.top;return ok;/=出棧函數(shù)模板template T2

25、 GetTop(T1 S)if(S.top=S.base)return error;else return *(S.top-1);/=/獲取棧頂元素模板unsigned char Prior77 = / 運算符優(yōu)先級表 / + - * / ( ) # /*+*/, /*-*/, /*/, /*/*/, /*(*/, , /*#*/, ,=, ; /= 運算符優(yōu)先級Status In(char Test,char* TestOp) bool Find=false; for (int i=0; i OPSETSIZE; i+) if (Test = TestOpi) Find= true; ret

26、urn Find;/=判斷是否為運算符float Operate(float a,unsigned char theta, float b) switch(theta) case +: return a+b;case -: return a-b;case *: return a*b;case /: return a/b;default : return 0; /=對兩操作數(shù)進行運算char OPSETOPSETSIZE=+,-,*,/,(,),#; int ReturnOpOrd(char op,char* TestOp) int i; for(i=0; i OPSETSIZE; i+) if

27、 (op = TestOpi) return i; return 0;/=返回運算符的下標(biāo)char precede(char Aop, char Bop) return PriorReturnOpOrd(Aop,OPSET)ReturnOpOrd(Bop,OPSET);/ReturnOpOrd和precede組合，/=判斷運算符優(yōu)先級float EvaluateExpression() / 算術(shù)表達式求值的算符優(yōu)先算法。 / 設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧，OPSET為運算符集合。SqStack OPTR; / 運算符棧，字符元素 SqStack OPND; / 運算數(shù)棧，實數(shù)元素 char TempData20; float Data,a,b; char theta,c,x,Dr2; InitStackSqStack,char (OPTR); Push (OPTR, #); InitStack SqStack,float(OPND); strcpy(TempData,0);/將TempData置為空 c=