算術表達式的求解-數據結構課程設計報告

1、精選優(yōu)質文檔-傾情為你奉上課程設計報告題目：算術表達式求值一、需求分析1、設計要求：給定一個算術表達式，通過程序求出最后的結果1>、從鍵盤輸入要求解的算術表達式；2>、采用棧結構進行算術表達式的求解過程；3>、能夠判斷算術表達式正確與否；4>、對于錯誤表達式給出提示；5>、對于正確的表達式給出最后的結果；2、設計構想：為了實現算符優(yōu)先算法使用兩個工作棧，一個稱作OPTR，以寄存運算符；另一個稱作OPND，用以寄存操作數或運算結果。在操作數和操作符入棧前，通過一個函數來判別，輸入的是操作數還是操作符，操作數入OPND，操作符入OPTR。在輸入表達式的最后輸入#，設定

2、#的優(yōu)先級最低，代表表達式輸入結束。在表達式輸入過程中，遇操作數則直接入棧，遇到運算符則與棧頂運算符比較優(yōu)先級,若當前運算符優(yōu)先級高，則當前運算符入棧,掃描下一符號;否則棧頂運算符出棧,兩操作數出棧,進行運算,所得結果入數棧,重新比較當前運算符與新棧頂運算符。如此重復直到棧頂運算符與當前符號均為#，運算結束。二、概要設計1、本程序包含的模塊：（1）棧模塊實現棧抽象數據類型（2）運算模塊實現數據表達式的運算（3）主程序模塊算術運算式的求解棧模塊主函數模塊main運算模塊初始化棧定義棧結構出棧入棧取棧頂元素判斷輸入字符類型判斷符號優(yōu)先級基礎運算函數運算函數三、詳細設計（1）棧模塊1、定義棧結構st

3、ruct Sqstackelemtype *top;/棧頂元素elemtype *base; /棧底元素int stacksize;/棧的大小  ;2、棧的基本操作初始化棧status initstack(struct Sqstack &s)s.base=(elemtype *)malloc(stack_size*sizeof(elemtype);if(!s.base)return OVERFLOW;s.top=s.base;s.stacksize=stack_size;return OK;入棧status push(struct Sqstack &s,elemtyp

4、e e)if(s.top-s.base>=s.stacksize) s.base=(elemtype*)realloc(s.base,(s.stacksize+stack_increasement)*sizeof(elemtype);if(!(s.base)return OVERFLOW;s.top=s.base+s.stacksize;s.stacksize+=stack_increasement;* s.top+=e;return OK;出棧elemtype pop(struct Sqstack &s)elemtype e;if(s.top= =s.base)return E

5、RROR;e=*-s.top;return e;取棧頂元素elemtype gettop(struct Sqstack &s)elemtype e;if(s.top=s.base)return ERROR;e=*(s.top-1);return e;（2）運算模塊1、判斷輸入字符c是否為操作符：若是，則返回1；否則，返回0 int In(int c) char p10="+-*/()#" int i=0; while(pi!='0') if(pi=c) return 1;i+; return 0;2、判斷運算符的優(yōu)先級 char precede(ch

6、ar top,char c)/該函數為判斷當前運算符與前一個運算符的優(yōu)先級，前一個運算符高于或等于當前運算符的優(yōu)先級則返回>， 前一個運算符小于當前運算符的優(yōu)先級則返<，當前一個運算符為（當前運算符為）時返回=，用于去除表達式的括號。 char result; switch(c) case '#': result='>' break; case '+': case '-': if(top='#'|top='(') result='<' else result=

7、'>' break; case '*': case '/': if(top='*'|top='/'|top='') result='>' else result='<' break; case '%': if(top='%'|top='/'|top=''|top='*') result='>' else result='<'br

8、eak; case ')': if(top='(') result='=' else result='>' break; case '(': result='<' break; case '': result='<' break; default: printf("操作符輸入錯誤！n"); return result;3、運算函數 基礎運算函數：實現相應的加、減、乘、除、乘方及帶小括號的基本數學運算并返回結果，其中a，b為兩個操作

9、數，theta為操作符elemtype operate(elemtype a,char theta,elemtype b) elemtype result; switch(theta) case '+': result=a+b; break; case '-': result=a-b; break; case '*': result=a*b; break; case '/': if(b=0) printf("nn輸入錯誤!分母不能為0!n"); result=0; else result=a/b;break;

10、case '%': if(b=0|b=NULL) printf("nn輸入錯誤!n");return 0;break; else result=a%b;break; case '': result=(int)pow(double)a,(double)b); break; default: printf("操作符輸入錯誤！n"); return result; 運算函數elemtype evaluate(struct Sqstack opnd,struct Sqstack optr)/該函數為求表達式的值的整個操作過程，通過

11、調用相應的函數實現遇到運算符則與棧頂運算符比較優(yōu)先級,/若當前運算符優(yōu)先級高(前面的運算還不應執(zhí)行)則當前運算符入棧,掃描下一符號;否則棧頂運算符出棧,同時兩操作數出棧,進行運算,所得結果入數棧,/重新比較當前運算符(注意當前運算符未變)與新棧頂運算符。如此重復直到棧頂運算符與當前符號均為#，運算結束。/若操作數為個位數，則直接將輸入的字符減48后入棧，若為多位數，則通過flag來實現。若輸入字符c為操作數且flag=1(即操作數為多位數)，則將操作數棧的棧頂元素出棧后乘以10，然后加上，（c-48）然后將二者的和入操作數棧。 elemtype a,b,c,theta,e; initstack

12、(optr); push(optr,'#'); initstack(opnd); c=getchar(); int flag=0;/當輸入操作數時flag=1；當輸入操作符時flag=0；/當前輸入為操作數且flag=1時，將操作數棧的棧頂元素出棧，然后將其和當前輸入轉換成相應的int類型 while(c!='#'|gettop(optr)!='#') if(!In(c) /c若為操作數則入opnd棧 if(flag=1) e=pop(opnd); / 取棧頂元素 push(opnd,(e*10+(c-48);/將輸入數在轉化為int型，并將上次

13、輸入數*10并與當前操作數相加，將結果如操作數棧 else push(opnd,c-48); flag=1; c=getchar(); else flag=0;/當前字符為操作符，則入操作符棧，并將flag置為0 switch(precede(gettop(optr),c)/ 判斷當前操作數與操作符棧中的棧頂元素的優(yōu)先級 case '<': push(optr,c); c=getchar(); break;/ 若當前操作符的優(yōu)先級高于操作符棧的棧頂元素，則將當前操作符入操作符棧 case '=': e=pop(optr); c=getchar(); bre

14、ak;/ 若當前操作符與操作符棧的棧頂元素構成匹配的括號，則/將操作符棧頂元素出棧 case '>': theta=pop(optr); b=pop(opnd); a=pop(opnd); push(opnd,operate(a,theta,b); break;/ 若當前操作符的優(yōu)先級低于操作符棧的棧頂元素，則將操作符棧棧頂元素出棧，并將操作數棧的棧頂兩個元素出棧，計算兩個元素間以操作符棧棧頂元素為運算符的數學運算 /switch/if /while return pop(opnd);（3）主程序模塊1、main函數 void main(int argc,char *ar

15、gv) struct Sqstack opnd; /操作數棧 struct Sqstack optr;/操作符棧initstack(opdn);initstack(optr); elemtype result; printf("*n"); printf("算術運算式的求解"); printf("n*n"); printf("n請輸入算術運算表達式(以'#'結尾):n"); printf("n"); result=evaluate(opnd,optr); printf("

16、n*n"); printf("nn運算的結果是 :n n%dn",result); printf("n*n"); 四、調試分析1、測試結果 1> 測試數據：3+7*2-1# 測試結果： 2> 測試數據：(3+7)*2-1# 測試結果： 3> 測試數據： 1/0# 測試結果： 2、程序時間復雜度為O（n）；3、設計中出現的問題：在開始的設計中沒有注意除數不能為0 ，后來加入if(b=0) printf("分母為0,the result is errorn"); result=0; else result=a/b;break;來判斷除數是否為04、算法改進：1>輸入的操作數和操作碼由于是字符串類型的，在原設計中實現的操作都是對個位數實現的，實用性不大，故在后來的設計中，通過一個標志flag實現了標志操作數的連續(xù)輸入的判別，繼而實現了多位數的表達式運算2>開始只實現了加、減、乘、除及帶小括號的數學運算，考慮到實用性，在后來的設計中引入pow函數，實現了乘方的運算，調整結果如下：3>最初設計的運行界面過于單調，不夠友好，改進時加入一些*調