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

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

2、。三、程序運(yùn)行平臺(tái)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; / 棧的長(zhǎng)度;int InitStack (SqStack &s)/建立一個(gè)空棧 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)棧為空的時(shí)候返回ERRORprintf(運(yùn)算符棧為空!n);return ERROR;elsee=*(s.top-1);棧不為空的時(shí)候用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) );/ 棧滿的時(shí)候,追加5個(gè)存儲(chǔ)空間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)/棧為空棧的時(shí)候，返回ERRORprintf(運(yùn)算符棧為空!n);return ERROR;elseOKe=*-s.top;/棧不為空的時(shí)候用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); 棧為空棧的時(shí)候返回ERRORreturn ERROR;while(t!=s.top)printf( %c,*t); /棧不為空的時(shí)候依次取出棧內(nèi)元素t+；return ERROR;(2)數(shù)字棧部分：struct SqStackn / 定義數(shù)棧int*base;/棧底指針int*top;/棧頂指針intstacksize;棧的長(zhǎng)度;int InitStackn (SqStackn &s)/建立一個(gè)空棧 Ss.base=(i nt*)malloc(50*sizeof(i nt); if(!s.base)exit(OVERFLOW);/ 存儲(chǔ)分配失敗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); /棧為空的時(shí)候返回 ERROR return ERROR;elsee=*(s.top-1);/棧不為空的時(shí)候，用 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); /棧滿的時(shí)候，追加5個(gè)存儲(chǔ)空間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); /棧為空棧的視時(shí)候，返回 ERRORreturn ERROR;elsee=*-s.top;棧不空的時(shí)候，則刪除 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); /棧為空棧的時(shí)候返回 ERRORreturn ERROR;while(t!=s.top)printf(” d,*t); /棧不為空的時(shí)候依次輸出t+；return ERROR;五、算法及時(shí)間復(fù)雜度1、算法：建立兩個(gè)不同類型的空棧，先把一個(gè)妊入運(yùn)算符棧。輸入一個(gè)算術(shù)表達(dá)式的字符串(以結(jié)束)，從第一個(gè)字符依次向后讀，把讀取的數(shù) 字放入數(shù)字棧，運(yùn)算符放入運(yùn)算符棧。判斷新讀取的運(yùn)

9、算符和運(yùn)算符棧頂 得運(yùn)算符號(hào)的優(yōu)先級(jí)，以便確定是運(yùn)算還是把運(yùn)算符壓入運(yùn)算符棧。最后 兩個(gè)遇到一起則運(yùn)算結(jié)束。數(shù)字棧頂?shù)臄?shù)字就是要求的結(jié)果。2、時(shí)間復(fù)雜度：0(n)數(shù)據(jù)壓縮存儲(chǔ)棧，其操作主要有：建立棧 int Push(SeqStack *S, char x)入棧 int Pop(SeqStack *S, char x)出棧。以上各操作運(yùn)算的平均時(shí)間復(fù)雜度為0(n),其主要時(shí)間是耗費(fèi)在輸入操作。六、測(cè)試用例如圖所示。血-|口| 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á)式求值問(wèn)題描述一個(gè)算術(shù)表達(dá)式是由操作數(shù)（operand）、運(yùn)算符（operator）和界限符（delimiter）組成的 假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“ #如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用 算符優(yōu)先法”求算術(shù)表達(dá)式的值?；疽螅?）從鍵盤(pán)讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。（2）顯示輸入序列和棧的變化過(guò)程。*/#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;棧的長(zhǎng)度;int InitStack (SqStack &s)建立一個(gè)空棧 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)棧為空的時(shí)候返回ERRORprintf(運(yùn)算符棧為空!n);return ERROR;elsee=*(s.top-1);棧不為空的時(shí)候用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) );/ 棧滿的時(shí)候，追加5個(gè)存儲(chǔ)空間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)棧為空棧的時(shí)候，返回 ERRORprintf(運(yùn)算符棧為空!n);return ERROR;elsee=*-s.top;棧不為空的時(shí)候用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);/棧為空棧的時(shí)候返回ERRORreturn ERROR;while(t!=s.top)printf( %c,*t); /棧不為空的時(shí)候依次取出棧內(nèi)元素t+； return ERROR;數(shù)字棧部分*struct SqStackn / 定義數(shù)棧int *base; 棧底指針int *top;棧頂指針int stacksize;棧的長(zhǎng)度;int InitStackn (SqStackn &s)建立一個(gè)空棧 Ss.base=(i nt*)ma

15、lloc(50*sizeof(i nt); if(!s.base)exit(OVERFLOW);存儲(chǔ)分配失敗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); /棧為空的時(shí)候返回ERROR return ERROR;elsee=*(s.top-1); /棧不為空的時(shí)候，用e作返回值，返回S的棧頂元素，并返回OKreturn OK;int Pushn(SqStackn &s,int e) / 數(shù)棧入棧if (s.top-s

16、.base =s.stacksize)printf(運(yùn)算數(shù)棧滿!n); /棧滿的時(shí)候，追加5個(gè)存儲(chǔ)空間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); /棧為空棧的視時(shí)

17、候，返回ERRORreturn ERROR; elsee=*-s.top;棧不空的時(shí)候，則刪除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); /棧為空棧的時(shí)候返回ERRORreturn ERROR;while(t!=s.top)printf( %d,*t); /棧不為空的時(shí)候依次輸出 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)先級(jí)的比較 char p;switch(chl)case +:case -:ch2運(yùn)算符if (ch2=+|ch2=-|ch2=)|ch2=#)p = ;ch1運(yùn)算符的優(yōu)先級(jí)小于elsep =；break;case case /:if (ch2 =() p =； break;case (:if (ch2 =)p =；else if (ch2 = #)printf(表達(dá)式錯(cuò)誤！運(yùn)算符不匹配!n); exit(0);elsep =;break ;case #:if (ch2 =)printf(表達(dá)式錯(cuò)誤！運(yùn)算符不匹配!n); exit(0);else if

20、 (ch2 = #)p =；elsep=;break;return p;/=/以下是求值過(guò)程/= int EvaluateExpression()/參考書(shū) 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)檫\(yùn)算符棧以#作為結(jié)束標(biāo)志In itStack n(OPND);/ printf(nn按任意鍵開(kāi)始求解:nn);/ ch=get

21、ch();printf(n請(qǐng)輸入表達(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)制并計(jì)算temp=ch-0;/將字符轉(zhuǎn)換為十進(jìn)制數(shù)ch=strj;j+；while(!lsoperator(ch)temp=temp*10 + ch-O;II將逐個(gè)讀入運(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);/彈出最上面兩個(gè)，并運(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(您的輸入有問(wèn)題，請(qǐng)檢查重新輸入！)；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)算請(qǐng)按 Y/y ); printf(n退出程序請(qǐng)按N/n );printf(n.n);ch=getch();ch=toupper(ch);將ch字符轉(zhuǎn)換成大寫(xiě)字母if(ch = N)printf(nn 系統(tǒng)退出。n); exit(O);Man age();int mai n()ShowMe nu();Man age();return 0;感想體會(huì)與總結(jié)好的算法+編程技巧+高效率=好的程序。1做什么都需要耐心，做設(shè)計(jì)寫(xiě)程序更需要耐心。一開(kāi)始的時(shí)候， 我寫(xiě)函數(shù)寫(xiě)的很快，可是等最后調(diào)試的時(shí)候發(fā)現(xiàn)錯(cuò)誤很隱蔽，就很費(fèi)時(shí)間 了。后來(lái)我先在紙上構(gòu)思出函數(shù)的功能和參數(shù)，考慮好接口之后才動(dòng)手 編，

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