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

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

2、表表達(dá)式輸入結(jié)束。在表達(dá)式輸入過程中，遇操作數(shù)那么直接入棧，遇到運(yùn)算符那么與棧頂運(yùn)算符比擬優(yōu)先級(jí),假設(shè)當(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í)根底運(yùn)算函數(shù)運(yùn)算函數(shù)三、詳細(xì)設(shè)計(jì)1棧模塊1、定義棧結(jié)構(gòu)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運(yùn)算模塊1、判斷輸入字符c是否為操作符：假設(shè)是，那么返回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(char top,char

6、 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、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("操作符輸入錯(cuò)誤！n"); return result;3、運(yùn)算函數(shù) 根底運(yùn)算函數(shù)：實(shí)現(xiàn)相應(yīng)的加、減、乘、除、乘方及帶小括號(hào)的根本數(shù)學(xué)運(yùn)算并返回結(jié)果，其中a，b為兩個(gè)操作數(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輸入錯(cuò)誤!分母不能為0!n"); result=0; else result=a/b;break; case '%

10、': 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è)操作過程，通過調(diào)用相應(yīng)的函數(shù)實(shí)現(xiàn)遇到

11、運(yùn)算符那么與棧頂運(yùn)算符比擬優(yōu)先級(jí),/假設(shè)當(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è)操作數(shù)為個(gè)位數(shù)，那么直接將輸入的字符減48后入棧，假設(shè)為多位數(shù)，那么通過flag來實(shí)現(xiàn)。假設(shè)輸入字符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;/當(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è)為操作數(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;/ 假設(shè)當(dāng)前操作符的優(yōu)先級(jí)高于操作符棧的棧頂元素，那么將當(dāng)前操作符入操作符棧 case '=': e=pop(optr); c=getchar(); b

14、reak;/ 假設(shè)當(dāng)前操作符與操作符棧的棧頂元素構(gòu)成匹配的括號(hào)，那么/將操作符棧頂元素出棧 case '>': theta=pop(optr); b=pop(opnd); a=pop(opnd); push(opnd,operate(a,theta,b); break;/ 假設(shè)當(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

15、 *argv) 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(&q

16、uot;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ù)雜度為On；3、設(shè)計(jì)中出現(xiàn)的問題：在開始的設(shè)計(jì)中沒有注意除數(shù)不能為0 ，后來參加if(b=0) printf("分母為0,the result is errorn"); result=0; else result=a/b;break;來判斷除數(shù)是否為04、算法改良：1>輸入的操作數(shù)和操作碼由于是字符串類型的，在原設(shè)計(jì)中實(shí)現(xiàn)的操作都是對(duì)個(gè)位數(shù)實(shí)現(xiàn)的，實(shí)用性不大，故在后來的設(shè)計(jì)中，通過一個(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í)用性，在后來的設(shè)計(jì)中引入pow函數(shù)，實(shí)現(xiàn)了乘方的運(yùn)算，調(diào)整結(jié)果如下：3>最初設(shè)計(jì)的運(yùn)行界面過于單調(diào)，不夠友好，改良時(shí)參