算數(shù)表達式的求解課程設計報告

1、合肥學院計算機科學與技術系課程設計報告20 12 20 13 學年第 2 學期課程數(shù)據(jù)結構與算法 課程設計名稱算數(shù)表達式的求解學生姓名周麗娟學號1104012013專業(yè)班級11計本3班指導教師李紅20 13 年 3 月 【問題描述】（算數(shù)表達式的求解）給定一個算數(shù)表達式，通過程序求出最后的結果。【要求】1、 從鍵盤輸入要求解的算術表達式；2、 采用棧結構進行算數(shù)表達式的求解過程；3、 能夠判斷算數(shù)表達式的正確與否；4、 對于錯誤表達式給出提示；5、 對于正確表達時給出最后的結果。1、 問題分析和任務定義有題目可知，程序要求給定一算數(shù)表達式并計算最后的結果，我們知道，在高級語言中，任何一個表達式

2、都是有操作數(shù)、運算符和界限符組成。在計算過程中，還要考慮表達式中有無括號以及左右括號之分。由于運算符有優(yōu)先級的高低，因此一個算數(shù)表達是不可能總是按順序執(zhí)行。 通過以上可知，可以用棧來實現(xiàn)運算符的優(yōu)先級完成算術表達式的求解。為實現(xiàn)算法的優(yōu)先級，設置兩個棧：一個稱為操作數(shù)棧opnd，用以寄存操作數(shù)和運算結果，另一個為操作符棧optr，用以寄存運算符。該算法的基本思想是：（1） 首先置操作數(shù)棧opnd為空棧，表達式結束符“#”為操作符棧optr的棧底元素。（2）依次讀入表達式中每個字符，若為操作數(shù)，則進opnd棧；若是運算符，則與optr棧的棧頂運算符比較優(yōu)先級后做相應操作：若當前操作符大于optr

3、棧的棧頂，則當前操作符入棧；否則，opnd棧的棧頂元素、次棧頂元素出棧，同時optr棧的棧頂元素也出棧，形成運算，并將結果壓入opnd棧，直至整個表達式求值完畢（即optr棧的棧頂元素和當前讀入的字符均為“#”）。 對于算術表達式的輸入，本程序采用gets()的方法讀入，將運算符+，-，*，/，（，），#存儲在數(shù)組中時，定義表達式求解函數(shù)，在函數(shù)中判斷讀入的字符，如果是運算符，將這些字符入操作符optr棧，并比較優(yōu)先級，判斷是否運算。若讀入的字符為0到9之間的數(shù)字時，用字符相減轉化為整型，然后將轉化后的整型再轉化為ascii的形式壓入操作數(shù)棧opnd中。2、數(shù)據(jù)結構的選擇和概要設計（1） 存儲

4、結構設計本程序主要采用順序棧結構類型（stack）來存儲表達式計算中的數(shù)據(jù)。程序中需要建立兩個棧，一個棧用于寄存運算符，另一個則用于寄存操作數(shù)和計算結果，故需要建立兩個順序棧結構類型。（2） 算數(shù)優(yōu)先級設計 對一任意的表達式，由于表達式中運算符的優(yōu)先級不同，可能會使表達式不按順序進行計算。在本程序中定義函數(shù)proceed（）來比較運算符的優(yōu)先級，而函數(shù)中各優(yōu)先級的比較主要根據(jù)以下優(yōu)先級比較的表格：表1：運算符優(yōu)先級運算符+-*/（）#用數(shù)字表示0123456棧內(nèi)操作符的優(yōu)先級3355160棧外操作符的優(yōu)先級2244610 在precede（）函數(shù)中定義兩個字符型參數(shù)變量op和c，其中op表示棧

5、頂運算符，c表示當前讀入運算符，對于當前運算符是否入棧，進行如下操作：比較當前運算符和棧頂運算符的優(yōu)先級的大?。?1、如果當前運算符的優(yōu)先級大于棧頂運算符的優(yōu)先級，即opc;令函數(shù)返回值為c；令函數(shù)返回值為，此時應將棧頂運算符出棧和棧頂、次棧頂操作數(shù)出棧并進行相應的運算。 3、如果當前元素的優(yōu)先級等于棧頂運算符的優(yōu)先級，即op=c；令函數(shù)的返回值為=，此時界限符內(nèi)的表達式已計算完畢。（3）程序模塊設計 1）程序模塊 本程序主要包含3個模塊：主程序模塊、計算模塊以及順序棧操作模塊，調(diào)用關系如圖所示：順序棧操作模塊計算模塊主程序模塊 圖1：程序模塊圖 2）系統(tǒng)功能模塊 本程序大致包含10個函數(shù)，其

6、中包含主函數(shù)。每個函數(shù)都有其相對應的功能實現(xiàn)。 操作符的輸入函數(shù) int in(char c); 運算符比較優(yōu)先級函數(shù) char proceed(char op,char c); 進行四則運算函數(shù) int operate(int a,char a1,int b); 實現(xiàn)表達式的求值函數(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ù) void em

7、pty(stack *s); 主函數(shù) int main() 3)函數(shù)之間主要調(diào)用的關系圖 本程序主要包含10個程序，各程序之間的關系如圖所示：（部分函數(shù)用以上的編號表示）void main()int evalexpres(void) 圖2：函數(shù)之間調(diào)用關系圖 3、詳細設計和編碼（1）、結構體類型的定義 typedef struct int datamaxsize; int top; int base; /棧底 stack; （2） 、全局變量定義/以下為函數(shù)聲明void initstack(stack *); /初始化棧 int empty(stack *); /判空棧 void push(s

8、tack *, int ); /進棧 int pop(stack *);/出棧 int gettop(stack *); /取棧頂元素 int operate(int ,char ,int ); / 計算結果 char proceed(char ,char ); / 比較優(yōu)先級 int in(char ); /判斷輸入符int evalexpres(void); /表達式計算函數(shù)/ 定義兩個棧分別存放運算符和操作數(shù)stack stackr,stackd; （3） 、系統(tǒng)主要子程序的詳細設計 1）、主函數(shù)模塊設計int main()/主函數(shù) int v; char ch;while(1) pri

9、ntf(t*歡迎使用算術表達式的求解的小程序*n); v = evalexpres(); printf(t表達式的計算結果為:%d,v); printf(ntinput n to quit and enter run again:); do scanf(%c,&ch); if(ch = n | ch = n) exit(0); while(ch!=n); system(cls); return 0; 在主函數(shù)中，設定用戶操作界面的形式，通過調(diào)用表達式求解的子函數(shù)實現(xiàn)算法所要實現(xiàn)的功能，然后通過while()循環(huán)語句控制，可以實現(xiàn)多次調(diào)試。 2）、計算函數(shù)模塊 int operate(int a

10、,char a1,int b) int s; int d1 = a; int d2 = b; /把字符ab變?yōu)閷獢?shù)字 switch(a1) case +: s = d1+d2; break; case -: s = d2-d1;break; case *: s = d1*d2; break; case /: s = d2/d1; return (s+0); /將運算結果轉化為ascii碼的形式入棧， 在計算函數(shù)中，定義3個變量，表示基本運算中的變量。采用開關語句實現(xiàn)表達式的基本運算，將運算結果轉化為ascii的形式返回。 3）、表達式求解的函數(shù)模塊 int evalexpres(void)

11、/ 表達式求解函數(shù) int a,b,i=0,s=0; char c80,r; initstack(&stackr); /初始化棧 push(&stackr,#); /將表達式起始符壓入棧 initstack(&stackd); printf( t請輸入表達式并以#結束：); gets(c); while(ci!=# | gettop(&stackr)!=#) if(!in(ci) /判斷讀入的字符是不是運算符 不是則進opnd棧 if(ci = 0 & ci = 9) s += ci-0; /字符的ascii相減將字符型轉化為整型 while(!in(c+i) /繼續(xù)判斷下一個字符，若不是運算

12、符，表明為多位數(shù)，直到讀取到字符為運算符為止 s*=10; s += ci-0; push(&stackd,s+0); /將整型轉化為ascii的形式入棧，使字符在棧內(nèi)以ascii的形式保存，實現(xiàn)多位數(shù)的計算 s = 0; /初始化s，繼續(xù)判斷 else printf(你輸入的表達式有誤!n); return 0; else switch(proceed(gettop(&stackr),ci) /此函數(shù)用來比較讀取的運算符和棧頂運算符的優(yōu)先級 case : /棧頂?shù)膬?yōu)先級高則出棧，并將計算結果壓入棧內(nèi) r = pop(&stackr); a = pop(&stackd)-0; /操作數(shù)在棧內(nèi)以

13、ascii的形式存儲，出站后要將ascii轉化為整型，然后進行運算 b = pop(&stackd)-0; push(&stackd,operate(a,r,b) ; break; return (gettop(&stackd)-0); / 將棧頂元素轉化為整型的形式輸出 對于表達式求解函數(shù)，在程序中主要思想是對讀入的表達式進棧進行判斷。若讀入的是0到9之間的字符，將這些字符采用ascii相減的形式轉化為整型，再入opnd棧，若讀入的字符為運算符，則將運算符入棧，并比較運算符之間的優(yōu)先級，看是否運算，若棧頂?shù)倪\算符小于當前輸入的運算符，則不需運算，只要將當前運算符入棧即可。否則，運算。運算時先

14、將optr棧的棧頂運算符和opnd棧的棧頂、次棧頂元素出棧，并將opnd棧中出棧的元素的ascii形式轉化為整型再計算，最后講計算結果再轉化為ascii碼的形式壓入opnd棧中。使表達式求解函數(shù)返回值為opnd的棧頂元素。4、上級調(diào)試過程遇到問題以及解決方案 問題1、調(diào)試時沒有錯誤，但運行時顯示錯誤。解決方案：通過它提示的錯誤和警告，在判斷是否為運算符的子函數(shù)中出現(xiàn)錯誤，如果為運算符時返回1，其次返回0，在返回0時沒有用else，這樣使得整個子函數(shù)可以返回一個有效值。 問題2、調(diào)試時程序顯示沒有錯誤，可以運行，但在運行時結果卻出現(xiàn)錯誤。解決方案：把程序從頭看了一遍，發(fā)現(xiàn)在比較優(yōu)先級的函數(shù)中，優(yōu)

15、先級的比較比較亂，而且部分出錯，后來查了關于運算符優(yōu)先級的資料，通過在紙上把各種優(yōu)先級列出，解決這個錯誤。算法的時間復雜度 由于在主函數(shù)用到嵌套循環(huán)，故算法的時間復雜度為o（n2）。5、 測試結果及其分析 （1）、實現(xiàn)基本的加減乘除運算，當想要繼續(xù)輸入表達式時點擊enter鍵，若要結束，點擊n或n鍵即可，而且可實現(xiàn)多位數(shù)的運算。（2）、實現(xiàn)復雜的算術表達式（3）、錯誤表達式的處理6、用戶使用說明 （1）本程序執(zhí)行的文件為“算數(shù)表達式的求解問題”。 （2）所求表達式中都只是僅包含加、減、乘、除4種基本運算的，其中也包含括號的應用，所有的運算對象均為簡單變量，要求將表達式中的數(shù)字字符轉化為整型，且

16、輸入表達式以“#”結束。 （3）輸入表達式時，以#結束，當點擊回車鍵時即可得到運算結果，當想繼續(xù)輸入表達式時，再次點擊回車鍵即可，當想結束時，點擊字母n或n。 （4）當輸入錯誤表達式時，程序會給出相應的提醒。7、 參考文獻 （1）王昆侖 、李紅主編，數(shù)據(jù)結構與算法，北京：中國鐵道出版社，2007年5月 （2）阮宏一 、魯靜主編，數(shù)據(jù)結構課程設計（c/c+描述），北京：電子工業(yè)出版社，2011年1月8、 附錄（源程序）：#include #include #define maxsize 16typedef struct int datamaxsize; int top; int base; /棧

17、低 stack; / 順序棧的定義/以下為函數(shù)聲明void initstack(stack *); /初始化棧 int empty(stack *); /判空棧 void push(stack *, int ); /進棧 int pop(stack *);/出棧 int gettop(stack *); /取棧頂元素 int operate(int ,char ,int ); / 計算結果 char proceed(char ,char ); / 比較優(yōu)先級 int in(char ); /判斷輸入符int evalexpres(void); /表達式計算函數(shù)/ 定義兩個棧分別存放運算符和操作

18、數(shù)stack stackr,stackd; int main()/主函數(shù) int v; char ch;while(1) printf(t*歡迎使用算術表達式的求解的小程序*n); v = evalexpres(); printf(t表達式的計算結果為:%d,v); printf(ntinput n to quit and enter run again:); do scanf(%c,&ch); if(ch = n | ch = n) exit(0); while(ch!=n); system(cls); return 0; void initstack(stack *s) /初始化棧 s-t

19、op = 0; s-base = 0; int empty(stack *s)/判斷棧是否為空 if(s-top =s-base) return 1; /?？諘r返回1，否則返回0 else return 0; void push(stack *s, int x) / 進棧 if(s-top = maxsize) printf(terror!n);exit(0); else s-datas-top = x; s-top+; int pop(stack *s)/ 出棧 int e; if(empty(s) printf(terror!n); exit(0); else s-top-; e = s-

20、datas-top; return e; int gettop(stack *s) /取棧頂元素 if(empty(s) printf(terror!n); exit(0); else return s-datas-top-1; int evalexpres(void) / 表達式求解函數(shù) int a,b,i=0,s=0; char c80,r; initstack(&stackr); push(&stackr,#); initstack(&stackd); printf( t請輸入表達式并以#結束：); gets(c); while(ci!=# | gettop(&stackr)!=#) i

21、f(!in(ci) /判斷讀入的字符不是運算符 是則進棧 if(ci = 0 & ci = 9) s += ci-0; /字符相減將字符型轉化為整型 while(!in(c+i) /繼續(xù)判斷下一個字符，若不是運算符，表明為多位數(shù)，直到讀取到字符為運算符為止 s*=10; s += ci-0; push(&stackd,s+0); /將整型轉化為ascii的形式入棧，使字符在棧內(nèi)以ascii的形式保存，實現(xiàn)多位數(shù)的計算 s = 0; /初始化s，繼續(xù)判斷 else printf(t你輸入的表達式有誤!n); exit(0); else switch(proceed(gettop(&stackr),ci) /此函數(shù)用來比較讀取的運算符和棧頂運算符的優(yōu)先級 case : /棧頂?shù)膬?yōu)先級高則出棧，并將計算結果壓入棧內(nèi) r = pop(&stackr); a = pop(&stackd)-0; /操作數(shù)在棧內(nèi)以ascii的形式存儲，出站后要將ascii轉化為整型，然后進行運算 b = pop(&stackd)-0; push(&stackd,operate(a,r,b) ; break; r