算術(shù)表達(dá)式的求解-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

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

2、#的優(yōu)先級(jí)最低，代表表達(dá)式輸入結(jié)束。在表達(dá)式輸入過(guò)程中，遇操作數(shù)則直接入棧，遇到運(yùn)算符則與棧頂運(yùn)算符比較優(yōu)先級(jí),若當(dāng)前運(yùn)算符優(yōu)先級(jí)高，則當(dāng)前運(yùn)算符入棧,掃描下一符號(hào);否則棧頂運(yùn)算符出棧,兩操作數(shù)出棧,進(jìn)行運(yùn)算,所得結(jié)果入數(shù)棧,重新比較當(dāng)前運(yùn)算符與新棧頂運(yùn)算符。如此重復(fù)直到棧頂運(yùn)算符與當(dāng)前符號(hào)均為#，運(yùn)算結(jié)束。二、概要設(shè)計(jì)1、本程序包含的模塊：（1）棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型（2）運(yùn)算模塊實(shí)現(xiàn)數(shù)據(jù)表達(dá)式的運(yùn)算（3）主程序模塊算術(shù)運(yùn)算式的求解棧模塊主函數(shù)模塊main運(yùn)算模塊初始化棧定義棧結(jié)構(gòu)出棧入棧取棧頂元素判斷輸入字符類型判斷符號(hào)優(yōu)先級(jí)基礎(chǔ)運(yùn)算函數(shù)運(yùn)算函數(shù)三、詳細(xì)設(shè)計(jì)（1）棧模塊1、定義棧結(jié)構(gòu)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）運(yùn)算模塊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ùn)算符的優(yōu)先級(jí) char precede(ch

6、ar top,char c)/該函數(shù)為判斷當(dāng)前運(yùn)算符與前一個(gè)運(yùn)算符的優(yōu)先級(jí)，前一個(gè)運(yùn)算符高于或等于當(dāng)前運(yùn)算符的優(yōu)先級(jí)則返回>， 前一個(gè)運(yùn)算符小于當(dāng)前運(yùn)算符的優(yōu)先級(jí)則返<，當(dāng)前一個(gè)運(yùn)算符為（當(dāng)前運(yùn)算符為）時(shí)返回=，用于去除表達(dá)式的括號(hào)。 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("操作符輸入錯(cuò)誤！n"); return result;3、運(yùn)算函數(shù) 基礎(chǔ)運(yùn)算函數(shù)：實(shí)現(xiàn)相應(yīng)的加、減、乘、除、乘方及帶小括號(hào)的基本數(shù)學(xué)運(yùn)算并返回結(jié)果，其中a，b為兩個(gè)操作

9、數(shù)，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輸入錯(cuò)誤!分母不能為0!n"); result=0; else result=a/b;break;

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

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

12、(optr); push(optr,'#'); initstack(opnd); c=getchar(); int flag=0;/當(dāng)輸入操作數(shù)時(shí)flag=1；當(dāng)輸入操作符時(shí)flag=0；/當(dāng)前輸入為操作數(shù)且flag=1時(shí)，將操作數(shù)棧的棧頂元素出棧，然后將其和當(dāng)前輸入轉(zhuǎn)換成相應(yīng)的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并與當(dāng)前操作數(shù)相加，將結(jié)果如操作數(shù)棧 else push(opnd,c-48); flag=1; c=getchar(); else flag=0;/當(dāng)前字符為操作符，則入操作符棧，并將flag置為0 switch(precede(gettop(optr),c)/ 判斷當(dāng)前操作數(shù)與操作符棧中的棧頂元素的優(yōu)先級(jí) case '<': push(optr,c); c=getchar(); break;/ 若當(dāng)前操作符的優(yōu)先級(jí)高于操作符棧的棧頂元素，則將當(dāng)前操作符入操作符棧 case '=': e=pop(optr); c=getchar(); bre

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

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

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