算術表達式求值課設報告

1、數據結構課程設計設計說明書表達式求值算法的實現學生學號班級成績指導教師數學與電腦科學學院2012年9月7日數據結構課程設計評閱書題目表達式求值算法的實現學生學號指導教師評語及成績成績：教師簽名：年 月曰答辯教師評語及成績成績：教師簽名：年 月曰教研室意見總成績：室主任簽名：年 月曰注：指導教師成績 60%，答辯成績40%，總成績合成后按五級制記入陝筋理工摩院課程設計任務書2011 2012學年第2學期專業(yè) 學號：課程設計名稱：數據結構課程設計設計題目表達式求值算法的實現完成期限：棧的存儲和相關運算是數據結構中數組部分的重點知識和技能。負達式求值算法可借助棧來完成,它的存儲可以使用順序結構也可以

2、使用鏈式結構，這要根據具體的應用來決定。本課程設計按以下的要求運用C/ C+結構體、指針、數據結構等基知識編程實現。任務要求：1闡述設計思想，畫出流程圖；2任意輸入一個表達式算術、邏輯、關系表達式；3建立棧；4借助棧的相關運算完成表達式求值過程;5丨將表達式及其運算結果按照其數學形式打印輸出；6說明測試方法，寫出完整的運行結果，較好的界面設計；7按照格式要求完成課程設計說明書。 設計要求：1問題分析和任務定義：根據設計題目的要求，充分地分析和理解問題，明確問題要求做什么？而不是怎么做？限制條件是什么？確定問題的輸入數據集合。2邏輯設計：對問題描述中涉及的操作對象定義相應的數據類型，并按照以數據

3、結構為中心的原則劃分模塊，定義主程序模塊和各抽象數據類型。邏輯設計的結果應寫出每個抽象數據類型的定義包括數據結構的描述和每個基本操作的功能說明，各個主要模塊的算法， 并畫出模塊之間的調用關系圖；3詳細設計：定義相應的存儲結構并寫出各函數的偽碼算法。在這個過程中，要綜合考慮系統功 能，使得系統結構清晰、合理、簡單和易于調試，抽象數據類型的實現盡可能做到數據封裝，基本操作 的規(guī)格說明盡可能明確具體。詳細設計的結果是對數據結構和基本操作做出進一步的求精，寫出數據存儲結構的類型定義，寫出函數形式的算法框架；4程序編碼：把詳細設計的結果進一步求精為程序設計語言程序。同時加入一些注解和斷言，使 程序中邏輯

4、概念清楚；5程序調試與測試：能夠熟練掌握調試工具的各種功能，設計測試數據確保程序正確。調試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結果；6結果分析：程序運行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。算法 的時間、空間復雜性分析；7編寫課程設計報告；指導教師簽字： 教研室主任簽字：批準日期：年 月 日摘要本次課程設計利用編程軟件，運用 c 語言、指針、結構體、數據結構中棧的相關知識編寫了表達式求值算法的程序。為了實現算符優(yōu)先算法使用兩個工作棧，一個稱為OPTR用以寄存運算符；另一個稱做OPND用以寄存操作數或運算結果。依次讀入表達式，假設是操作符即進OP

5、N棧，假設是運算符則和OPTF棧的棧頂運算符比較優(yōu)先權后作相應的操作，直至整個表達式求值完畢，最終實現了任意 表達式求值的簡單運算。關鍵詞 ：指針;結構體 ;棧目錄1 課題描述 12 設計要求 . 2設計具體要求 2總體規(guī)劃 . 23 邏輯設計與分析 3舉例分析 . 3算法核心 . 34 算法流程圖 . 44.1 主算法流程圖 4主要算法流程代碼 55 詳細設計 6順序棧的建立 6函數及對應程序 76 程序測試 10合法數據輸入 10非法數據輸入 11總結 12查考文獻 . 131 課題描述隨著現代科學技術的迅猛發(fā)展，電腦技術已經滲透到各個領域，成為各行業(yè)必不可少的工具 . 借助 現從識經濟時

6、代的特點， 對國民經濟建設提出了“用信息化帶開工業(yè)化”的指導思想。 對常用算法的實 現與比較操作而言， 全面開發(fā)和應用電腦操作系統就是近期不能回避的問題。 由于電腦技術的發(fā)展， 許 多復雜的數值問題才得以解決。 一個數學問題，乃至一個數值計算公式，如何在電腦上實現，而在電腦 處理計算的過程中又會產生哪些新問題，這是在實際應用算法操作中經常會遇到的課題。在電腦中，算術表達式由常量、變量、運算符和括號組成。由于不同的運算符具有不同的優(yōu)先級，又 要考慮括號，因此，算術表達式的求值不可能嚴格地從左到右進行。因而在程序設計時，借助棧實現。 算法輸入：一個算術表達式，由常量、變量、運算符和括號組成以字符串

7、形式輸入 。為簡化，規(guī)定操作 數只能為正整數，操作符為 +、-* 、/ ，用 #表示結束。算法輸出：表達式運算結果。算法要點：設置運算符 棧和運算數棧輔助分析算符優(yōu)先關系。 在讀入表達式的字符序列的同時， 完成運算符和運算數的識別處理， 以及相應運算。開發(fā)工具 ： Visual C+2設計要求運用C/C+、指針、結構體、數據結構中棧的相關知識編寫任意表達式求值算法的實現。主函數只要是表達式的輸入再通過調用EvaluateExpressio n()函數進行運算數、運算符等相關處理，最后輸出結果。如圖總體規(guī)劃圖3邏輯設計與分析3.1舉例分析如下表是對3*(7-2)的求值分析步驟。特別說明當在計算除

8、法運算時如果分母為0',則出現錯誤提示。步驟OPTR 棧OPND 棧輸入字符主要操作1#3*(7-2)#Push(OPND, '3')2#3*(7-2)#Push(OPTR,')3#*3(7-2)#Push(OPNR,'(')4#*(37-2)#Push(OPND, '7')5#*(3 7-2)#Push(OPNR,'-')6P #*(-r 3 72)#Push(OPND, '2')7#*(-3 7 2)#Operate( 7','-','2')8#*(3 5

9、)#Pop(OPTR)9#*3 5#Operate( 3','* ',5')10#15#Return(GetTop2(OPND)表3.1例子分析核心為了實現算符優(yōu)先算法?？梢允褂脙蓚€工作棧。一個稱為OPTR用以寄存運算符，另一個稱做OPND用以寄存操作數或運算結果。1首先置操作數棧為空棧，表達式起始符” # ”為運算符棧的棧底元素；2依次讀入表達式，假設是操作符即進 OPND棧，假設是運算符則和 OPTF棧的棧頂運算符比較 優(yōu)先權后作相應的操作，直至整個表達式求值完畢即OPTR棧的棧頂元素和當前讀入的字符均為” #”。4算法流程圖4.1主算法流程圖如下列圖4.1

10、給出了主要算法控制流程圖:/* 算術表達式求值的算符優(yōu)先算法。設 OPTR 和 OPND 分別為運算符棧和運算數棧， OPSET 為運算符集合。 */SqStack<char> OPTR; / 運算符棧，字符元素SqStack<float> OPND; / 運算數棧，實數元素char TempData20;float Data,a,b;char theta,c,x,Dr2;InitStack<SqStack<char>,char> (OPTR);Push (OPTR, '#');InitStack <SqStack<f

11、loat>,float>(OPND); strcpy(TempData,"0");/ 將 TempData 置為空 c=getchar();while (c!= '#' | GetTop<SqStack<char>,char>(OPTR)!= '#')if (!In(c, OPSET)Dr0=c;Dr1='0'/ 存放單個數strcat(TempData,Dr);/ 將單個數連到 TempData 中，形成字符串 c=getchar();if(In(c,OPSET)/ 如果遇到運算符，則將字

12、符串 TempData 轉換成實數，入棧， 并重新置空Data=(float)atof(TempData);Push(OPND, Data); strcpy(TempData,"0");else / 不是運算符則進棧switch (precede(GetTop<SqStack<char>,char>(OPTR), c) case '<': / 棧頂元素優(yōu)先權低Push(OPTR, c); c=getchar();break;case '=': / 脫括號并接收下一字符Pop(OPTR, x); c=getchar

13、(); break;case '>': / 退棧并將運算結果入棧Pop(OPTR, theta);Pop(OPND, b);Pop(OPND, a);Push(OPND, Operate(a, theta, b);break; / switch / while return GetTop<SqStack<float>,float>(OPND)5 詳細設計5.1 順序棧的建立任何一個表達式都是由操作符， 運算符和界限符組成的。 分別用順序棧來寄存表達式的操作數和運 算符。 棧是限定于緊僅在表尾進行插入或刪除操作的線性表。順序棧的存儲結構是利用一組連續(xù)

14、的存儲單元依次存放自棧底到棧頂的數據元素，同時附設指針 top 指示棧頂元素在順序棧中的位置， base 為 棧底指針， 在順序棧中， 它始終指向棧底， 即 top=base 可作為棧空的標記， 每當插入新的棧頂元素時， 指針 top 增 1，刪除棧頂元素時，指針 top 減 1。typedef int Status;template <typename T>struct SqStackT *top;T *base;int stacksize; 順序棧結構template <typename T1,typename T2>Status InitStack(T1 &

15、;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; 初始化棧函數 template <typename T1,typename T2> Status Push(T1 &S,T2 e)if(S.top-S.base>=S.stacksize)S.base=(T2 *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof

16、(T2); if(!S.base) exit (overflow);S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;*S.top+=e;return ok; 入棧函數 template <typename T1,typename T2> Status Pop(T1 &S,T2 &e)if(S.top=S.base) return error;e=*-S.top;return ok; 出棧函數template <typename T1,typename T2>T2 GetTop(T1 S)if(S

17、.top=S.base) return error;else獲取棧頂元素return *(S.top-1);5.2函數及對應程序(1) ln(char Test,char* TestOp)判斷字符是否是運算符功能，運算符即返回ture。Status In( char Test,char* TestOp) bool Fin d=false;for (int i=0; i< OPSETSIZE; i+) if (Test = TestOpi) Find= true;return Fi nd;/判斷是否為運算符(2) ReturnOpOrd(char op,char* TestOp)判斷運算符

18、優(yōu)先權功能，該函數判斷運算符Aop, Bop的優(yōu)先權。判斷運算符優(yōu)先權，返回優(yōu)先權高的。int ReturnOpOrd(char op,char* TestOp) int i;for(i=0; i< OPSETSIZE; i+) if (op = TestOpi) retur n i;return 0;char precede(char Aop, char Bop) return PriorReturnOpOrd(Aop,OPSET)ReturnOpOrd(Bop,OPSET);/ReturnOpOrd和precede組合，判斷運算符優(yōu)先級算符間的優(yōu)先關系如下：+-*/()#+>&

19、lt;<<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=(3) Operate(float a,unsigned char theta, float b) 果直接返回。操作數用對應的運算符進行運算功能。運算結float Operate(float a,unsigned char theta, fl

20、oat b) switch(theta) case '+': return a+b;case '-': return a-b;case '*': return a*b;case '/': if(b!=0) return a/b;else printf(" 輸入錯誤請重輸 ");/ 判斷分母是否為零 為零則重新輸入 default : return 0;/ 運算(4) EvaluateExpression() 主要操作函數，功能主要實現表達式的整體計算OPSET 為運算符集float EvaluateExpres

21、sion() 算術表達式求值的算符優(yōu)先算法，設 OPTR 和 OPND 分別為運算符棧和運算數棧， 合。SqStack<char> OPTR; / 運算符棧，字符元素SqStack<float> OPND; / 運算數棧，實數元素char TempData20;float Data,a,b;char theta,c,x,Dr2;InitStack<SqStack<char>,char> (OPTR);Push (OPTR, '#');InitStack <SqStack<float>,float>(OPND

22、); strcpy(TempData,"0");/ 將 TempData 置為空 c=getchar();while (c!= '#' | GetTop<SqStack<char>,char>(OPTR)!= '#')if (!In(c, OPSET)Dr0=c;Dr1='0'/ 存放單個數strcat(TempData,Dr);/ 將單個數連到 TempData 中，形成字符串 c=getchar();if(In(c,OPSET)/ 如果遇到運算符，則將字符串 TempData 轉換成實數，入棧， /

23、并重新置空 Data=(float)atof(TempData);Push(OPND, Data); strcpy(TempData,"0");else / 不是運算符則進棧switch (precede(GetTop<SqStack<char>,char>(OPTR), c) case '<': / 棧頂元素優(yōu)先權低Push(OPTR, c);c=getchar();break;case '=': / 脫括號并接收下一字符 Pop(OPTR, x);c=getchar();break;case '>': / 退棧并將運算結果入棧Pop(OPTR, theta);Pop(OPND, b);Pop(OPND, a);Push(OPND, Operate(a, theta, b); break; return GetTop<SqStack<float>,float>(OPND); 6程序測試圖6.1運行成功界面2任意輸入表達式 3*(2+4)s * C:5 e 1.1 in g AdAlihLi l jl a IL or EUD eb u.£ Cpp 1 ee*圖6.2表達式輸