算術表達式的求解數(shù)據(jù)結(jié)構課程設計報告

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

2、表表達式輸入結(jié)束。在表達式輸入過程中，遇操作數(shù)那么直接入棧，遇到運算符那么與棧頂運算符比擬優(yōu)先級,假設當前運算符優(yōu)先級高，那么當前運算符入棧,掃描下一符號;否那么棧頂運算符出棧,兩操作數(shù)出棧,進行運算,所得結(jié)果入數(shù)棧,重新比擬當前運算符與新棧頂運算符。如此重復直到棧頂運算符與當前符號均為#，運算結(jié)束。二、概要設計1、本程序包含的模塊：1棧模塊實現(xiàn)棧抽象數(shù)據(jù)類型2運算模塊實現(xiàn)數(shù)據(jù)表達式的運算3主程序模塊算術運算式的求解棧模塊主函數(shù)模塊main運算模塊初始化棧定義棧結(jié)構出棧入棧取棧頂元素判斷輸入字符類型判斷符號優(yōu)先級根底運算函數(shù)運算函數(shù)三、詳細設計1棧模塊1、定義棧結(jié)構struct Sqstack

3、elemtype *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,elemtype e)if(s.top

4、-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 ERROR;e=*-s.t

5、op;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(char top,char

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

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

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

9、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; case '%

10、': 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; 運算函數(shù)elemtype evaluate(struct Sqstack opnd,struct Sqstack optr)/該函數(shù)為求表達式的值的整個操作過程，通過調(diào)用相應的函數(shù)實現(xiàn)遇到

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

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

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

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

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

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