《數(shù)據(jù)結(jié)構(gòu)》算術(shù)表達(dá)式求值

1、二課程設(shè)計2算術(shù)表達(dá)式求值一、需求分析二、程序的主要功能三、程序運(yùn)行平臺四、數(shù)據(jù)結(jié)構(gòu)五、算法及時間復(fù)雜度六、測試用例七、程序源代碼三感想體會與總結(jié)算術(shù)表達(dá)式求值一、需求分析一個算術(shù)表達(dá)式是由操作數(shù)（operand）、運(yùn)算符（operator）和界限符 （delimiter）組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號和表達(dá)式起始、結(jié)束符“#”，如：# （ 7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符 優(yōu)先法”求算術(shù)表達(dá)式的值。二、程序的主要功能1）從鍵盤讀入一個合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。2）顯示輸入序列和棧的變化過程

2、。三、程序運(yùn)行平臺Visual C+6.0 版本四、數(shù)據(jù)結(jié)構(gòu)本程序的數(shù)據(jù)結(jié)構(gòu)為棧。1）運(yùn)算符棧部分：struct SqStack / 定義棧char *base; /棧底指針char *top; /棧頂指針int stacksize; / 棧的長度;int InitStack (SqStack &s)/建立一個空棧 Sif (!(s.base = (char *)malloc(50 * sizeof(char) exit(O);s.top=s.base;s.stacksize=50;return OK;char GetTop(SqStack s,char &e)/ 運(yùn)算符取棧頂元素if (s.

3、top=s.base)棧為空的時候返回ERRORprintf(運(yùn)算符棧為空!n);return ERROR;elsee=*(s.top-1);棧不為空的時候用e做返回值，返回S的棧頂元素，并返回 OKreturn OK;int Push(SqStack & s,char e) /運(yùn)算符入棧if (s.top-s.base = s.stacksize)printf(運(yùn)算符棧滿!n);s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) );/ 棧滿的時候,追加5個存儲空間if(!s.base) exit (OVERFLOW);s.t

4、op=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e;/把 e 入棧return OK;int Pop(SqStack & s,char & e) /運(yùn)算符出棧if (s.top=s.base)/棧為空棧的時候，返回ERRORprintf(運(yùn)算符棧為空!n);return ERROR;elseOKe=*-s.top;/棧不為空的時候用e做返回值，刪除S的棧頂元素，并返回return OK;int StackTraverse(SqStack & s) / 運(yùn)算符棧的遍歷char *t;t=s.base ;if (s.top=s.base)printf(

5、運(yùn)算符棧為空!n); 棧為空棧的時候返回ERRORreturn ERROR;while(t!=s.top)printf( %c,*t); /棧不為空的時候依次取出棧內(nèi)元素t+；return ERROR;(2)數(shù)字棧部分：struct SqStackn / 定義數(shù)棧int*base;/棧底指針int*top;/棧頂指針intstacksize;棧的長度;int InitStackn (SqStackn &s)/建立一個空棧 Ss.base=(i nt*)malloc(50*sizeof(i nt); if(!s.base)exit(OVERFLOW);/ 存儲分配失敗s.top=s.base;s

6、.stacksize=50;return OK;int GetTop n(SqStackn s,i nt & e) /數(shù)棧取棧頂元素if (s.top=s.base)printf(運(yùn)算數(shù)棧為空!n); /棧為空的時候返回 ERROR return ERROR;elsee=*(s.top-1);/棧不為空的時候，用 e作返回值，返回S的棧頂元素，并返回 0K return OK;int Push n(SqStackn &s,i nt e) /數(shù)棧入棧if (s.top-s.base =s.stacksize)printf(運(yùn)算數(shù)棧滿!n); /棧滿的時候，追加5個存儲空間s.base=(i nt

7、*)realloc (s.base,(s.stacksize+5)*sizeof(i nt); if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize; / 插入元素 e為新的棧頂元素 s.stacksize+=5;*(s.top)+=e; /棧頂指針變化return OK;int Pop n(SqStackn & s,i nt & e) /數(shù)棧出棧if (s.top=s.base)printf(運(yùn)算符棧為空!n); /棧為空棧的視時候，返回 ERRORreturn ERROR;elsee=*-s.top;棧不空的時候，則刪除 S的棧頂元素，用

8、e返回其值，并返回OKreturn OK;int StackTraverse n( SqStackn & s) /數(shù)棧遍歷int *t;t=s.base ;if (s.top=s.base)printf(運(yùn)算數(shù)棧為空!n); /棧為空棧的時候返回 ERRORreturn ERROR;while(t!=s.top)printf(” d,*t); /棧不為空的時候依次輸出t+；return ERROR;五、算法及時間復(fù)雜度1、算法：建立兩個不同類型的空棧，先把一個妊入運(yùn)算符棧。輸入一個算術(shù)表達(dá)式的字符串(以結(jié)束)，從第一個字符依次向后讀，把讀取的數(shù) 字放入數(shù)字棧，運(yùn)算符放入運(yùn)算符棧。判斷新讀取的運(yùn)

9、算符和運(yùn)算符棧頂 得運(yùn)算符號的優(yōu)先級，以便確定是運(yùn)算還是把運(yùn)算符壓入運(yùn)算符棧。最后 兩個遇到一起則運(yùn)算結(jié)束。數(shù)字棧頂?shù)臄?shù)字就是要求的結(jié)果。2、時間復(fù)雜度：0(n)數(shù)據(jù)壓縮存儲棧，其操作主要有：建立棧 int Push(SeqStack *S, char x)入棧 int Pop(SeqStack *S, char x)出棧。以上各操作運(yùn)算的平均時間復(fù)雜度為0(n),其主要時間是耗費(fèi)在輸入操作。六、測試用例如圖所示。血-|口| X運(yùn)算數(shù)棧為:2運(yùn)算符棧為: 柱豊嘉棧為:2 34運(yùn)算符棧為; + * 運(yùn)算數(shù)棧為:2 34運(yùn)算符棧為| 運(yùn)算數(shù)棧為;2 34 6運(yùn)算符棧為|# + -* 運(yùn)算數(shù)桟為I

10、2 34 6 4最終結(jié)果如圖所示:按N#n七、源代碼/*第七題算術(shù)表達(dá)式求值問題描述一個算術(shù)表達(dá)式是由操作數(shù)（operand）、運(yùn)算符（operator）和界限符（delimiter）組成的 假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號和表達(dá)式起始、結(jié)束符“ #如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用 算符優(yōu)先法”求算術(shù)表達(dá)式的值。基本要求（1）從鍵盤讀入一個合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。（2）顯示輸入序列和棧的變化過程。*/#i nclude #i nclude #i nclude #in elude #in elude

11、 vconi o.h#in elude #defi ne OK 1#defi ne ERROR 0#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10/=/以下定義兩種棧，分別存放運(yùn)算符和數(shù)字/=運(yùn)算符棧部分*struct SqStack/ 定義棧char *base;棧底指針char *top; 棧頂指針int stacksize;棧的長度;int InitStack (SqStack &s)建立一個空棧 Sif (!(s.base = (char *)malloc(50 * sizeof(char)exit(O);s.top=s.ba

12、se;s.stacksize=50;return OK;char GetTop(SqStack s,char &e)/ 運(yùn)算符取棧頂元素if (s.top=s.base)棧為空的時候返回ERRORprintf(運(yùn)算符棧為空!n);return ERROR;elsee=*(s.top-1);棧不為空的時候用e做返回值，返回S的棧頂元素，并返回OKreturn OK;int Push(SqStack &s,char e) / 運(yùn)算符入棧if (s.top-s.base = s.stacksize)printf(運(yùn)算符棧滿!n);s.base=(char*)realloc (s.base,(s.st

13、acksize+5)*sizeof(char) );/ 棧滿的時候，追加5個存儲空間if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e;/把 e 入棧return OK;int Pop(SqStack &s,char &e) / 運(yùn)算符出棧if (s.top=s.base)棧為空棧的時候，返回 ERRORprintf(運(yùn)算符棧為空!n);return ERROR;elsee=*-s.top;棧不為空的時候用e做返回值，刪除S的棧頂元素，并返回OKreturn OK;int StackTr

14、averse(SqStack & s) / 運(yùn)算符棧的遍歷char *t;t=s.base ;if (s.top=s.base)printf(運(yùn)算符棧為空!n);/棧為空棧的時候返回ERRORreturn ERROR;while(t!=s.top)printf( %c,*t); /棧不為空的時候依次取出棧內(nèi)元素t+； return ERROR;數(shù)字棧部分*struct SqStackn / 定義數(shù)棧int *base; 棧底指針int *top;棧頂指針int stacksize;棧的長度;int InitStackn (SqStackn &s)建立一個空棧 Ss.base=(i nt*)ma

15、lloc(50*sizeof(i nt); if(!s.base)exit(OVERFLOW);存儲分配失敗s.top=s.base;s.stacksize=50;return OK; int GetTopn(SqStackn s,int &e) / 數(shù)棧取棧頂元素if (s.top=s.base)printf(運(yùn)算數(shù)棧為空!n); /棧為空的時候返回ERROR return ERROR;elsee=*(s.top-1); /棧不為空的時候，用e作返回值，返回S的棧頂元素，并返回OKreturn OK;int Pushn(SqStackn &s,int e) / 數(shù)棧入棧if (s.top-s

16、.base =s.stacksize)printf(運(yùn)算數(shù)棧滿!n); /棧滿的時候，追加5個存儲空間s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int); if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize; /插入元素e為新的棧頂元素 s.stacksize+=5;*(s.top)+=e; /棧頂指針變化return OK;int Popn(SqStackn &s,int &e) / 數(shù)棧出棧if (s.top=s.base)printf(運(yùn)算符棧為空!n); /棧為空棧的視時

17、候，返回ERRORreturn ERROR; elsee=*-s.top;棧不空的時候，則刪除S的棧頂元素，用e返回其值，并返回OKreturn OK;int StackTraverse n(SqStackn & s) / 數(shù)棧遍歷int *t;t=s.base ;if (s.top=s.base)printf(運(yùn)算數(shù)棧為空!n); /棧為空棧的時候返回ERRORreturn ERROR;while(t!=s.top)printf( %d,*t); /棧不為空的時候依次輸出 t+;return ERROR;/=/以下定義函數(shù)/= int lsoperator(char ch)/判斷是否為運(yùn)算符

18、，分別將運(yùn)算符和數(shù)字進(jìn)入不同的棧switch (ch)case +:case -:case *:case /:case (:case ):case #:return 1;default:return 0; int Operate(i nt a, char op, int b) / 運(yùn)算操作 int result;switch(op)case +:result=a+b; break;case -:result=a-b; break;case *: result=a*b; break;case /:result=a/b; break;return result;char Precede(char

19、chi, char ch2) / 運(yùn)算符優(yōu)先級的比較 char p;switch(chl)case +:case -:ch2運(yùn)算符if (ch2=+|ch2=-|ch2=)|ch2=#)p = ;ch1運(yùn)算符的優(yōu)先級小于elsep =；break;case case /:if (ch2 =() p =； break;case (:if (ch2 =)p =；else if (ch2 = #)printf(表達(dá)式錯誤！運(yùn)算符不匹配!n); exit(0);elsep =;break ;case #:if (ch2 =)printf(表達(dá)式錯誤！運(yùn)算符不匹配!n); exit(0);else if

20、 (ch2 = #)p =；elsep=;break;return p;/=/以下是求值過程/= int EvaluateExpression()/參考書 p53 算法 3.4int a, b, temp, an swer;char ch,op,e;char *str;int j = 0;SqStackn OPND;/OPND 為運(yùn)算數(shù)字棧SqStack OPTR;/OPTR 為運(yùn)算符棧In itStack(OPTR);Push(OPTR,#);/,所以此棧底是#，因為運(yùn)算符棧以#作為結(jié)束標(biāo)志In itStack n(OPND);/ printf(nn按任意鍵開始求解:nn);/ ch=get

21、ch();printf(n請輸入表達(dá)式并以#結(jié)束:n);str =(char*)malloc(50*sizeof(char);gets(str);ch=strj; /ch是字符型的，而e是整型的整數(shù) j+;GetTop(OPTR,e); /e為棧頂元素返回值while (ch!=# | e!=#)if (!Isoperator(ch)遇到數(shù)字，轉(zhuǎn)換成十進(jìn)制并計算temp=ch-0;/將字符轉(zhuǎn)換為十進(jìn)制數(shù)ch=strj;j+；while(!lsoperator(ch)temp=temp*10 + ch-O;II將逐個讀入運(yùn)算數(shù)的各位轉(zhuǎn)化為十進(jìn)制數(shù)ch=strj;j+；Push n(OPND,te

22、mp);else if (Isoperator(ch)判斷是否是運(yùn)算符，不是運(yùn)算符則進(jìn)棧switch (Precede(e,ch)case : Pop(OPTR,op);/彈出最上面兩個，并運(yùn)算，把結(jié)果進(jìn)棧Pop n( OPND,b);Pop n(OPND,a);Push n(OPND,Operate(a,op,b); printf(nn 運(yùn)算符棧為：n); StackTraverse(OPTR); printf(n 數(shù)棧為：n);StackTraverse n(OPND);elseprintf(您的輸入有問題，請檢查重新輸入！)；exit(0); /whileGetTop n(OPND,a

23、nswer);/已輸出。數(shù)字棧最上面即是最終結(jié)果retur n an swer;/=/執(zhí)行部分/= void ShowMe nu() prin tf(nn);printf(Uh);printf(表達(dá)式求值系統(tǒng));printf();printf(void Quit();void Man age() int an swer;/ ShowMe nu();an swer=EvaluateExpressi on();printf(nn 表達(dá)式結(jié)果是:%dn,answer);Quit();void Quit()char ch;prin tf(本次運(yùn)算結(jié)束。n);printf(繼續(xù)本系統(tǒng)嗎？ nn);pri

24、ntf(繼續(xù)運(yùn)算請按 Y/y ); printf(n退出程序請按N/n );printf(n.n);ch=getch();ch=toupper(ch);將ch字符轉(zhuǎn)換成大寫字母if(ch = N)printf(nn 系統(tǒng)退出。n); exit(O);Man age();int mai n()ShowMe nu();Man age();return 0;感想體會與總結(jié)好的算法+編程技巧+高效率=好的程序。1做什么都需要耐心，做設(shè)計寫程序更需要耐心。一開始的時候， 我寫函數(shù)寫的很快，可是等最后調(diào)試的時候發(fā)現(xiàn)錯誤很隱蔽，就很費(fèi)時間 了。后來我先在紙上構(gòu)思出函數(shù)的功能和參數(shù)，考慮好接口之后才動手 編，

25、這樣就比較容易成功了。2、做任何事情我決定都應(yīng)該有個總體規(guī)劃。之后的工作按照規(guī)劃逐 步展開完成。對于一個完整的程序設(shè)計，首先需要總體規(guī)劃寫程序的步 驟，分塊寫分函數(shù)寫，然后寫完一部分馬上糾錯調(diào)試。而不是像我第一個 程序，一口氣寫完，然后再花幾倍的時間調(diào)試。一步步來，走好一步再走 下一步。寫程序是這樣，做項目是這樣，過我們的生活更是應(yīng)該這樣。3、感覺一開始設(shè)計結(jié)構(gòu)寫函數(shù)體現(xiàn)的是數(shù)據(jù)結(jié)構(gòu)的思想，后面的調(diào) 試則更加體現(xiàn)了人的綜合素質(zhì)，專業(yè)知識、堅定耐心、鍥而不舍，真的缺 一不可啊。4、通過這次課設(shè)，不僅僅復(fù)習(xí)了 C語言相關(guān)知識、鞏固了數(shù)據(jù)結(jié)構(gòu) 關(guān)于棧和排序的算法等知識，更磨練了我的意志。古希臘哲學(xué)大師亞里士多德說：人有兩種，一種即 吃飯是為了活著”一種是 活著是為了吃飯”一個人之所以偉大，首先是因為他有超于常人的心。志當(dāng)存高遠(yuǎn)”風(fēng)物長宜放眼量”這些古語皆鼓舞人們要樹立雄無數(shù)個自己，萬千種模樣，萬千愫情