用棧實(shí)現(xiàn)表達(dá)式計(jì)算.doc

1、一、設(shè)計(jì)思想算法一：利用棧將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式再進(jìn)行計(jì)算。（ 1）構(gòu)造 char 類型的棧函數(shù)以及棧的相關(guān)函數(shù)（出棧函數(shù)、進(jìn)棧函數(shù)、創(chuàng)建棧函數(shù)、銷毀棧函數(shù)、判斷棧是否為空函數(shù)、看棧頂函數(shù)等）。（ 2）在 main 函數(shù)中讓用戶進(jìn)行輸入，將用戶輸入的字符串進(jìn)行循環(huán)、判斷（如果數(shù)字字符后面的是運(yùn)算符，則在數(shù)字字符后加“#”以便進(jìn)行區(qū)分；否則，繼續(xù)循環(huán)。）并將判斷后的字符串傳遞到新的數(shù)組中，循環(huán)結(jié)束后， 再將數(shù)組傳遞給中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)（Min_Back() ）。（ 3）中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)是利用運(yùn)算符的優(yōu)先級(jí)進(jìn)行判斷來(lái)將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的函數(shù)。函數(shù)中利用構(gòu)建的棧以及

2、棧的相關(guān)函數(shù)對(duì)運(yùn)算符進(jìn)行操作： 先看棧頂， 如果棧為空或棧頂元素為 （或者棧頂元素為 +或并且現(xiàn)有運(yùn)算符為 * 、 / 或 %又或是現(xiàn)有運(yùn)算符為 （，則現(xiàn)有元素進(jìn)棧；否則，再對(duì)現(xiàn)有元素進(jìn)行判斷：如果現(xiàn)有元素為），運(yùn)算符出棧直到 （ 出棧；否則，運(yùn)算符出棧直到?？栈蛘邨ｍ斣氐膬?yōu)先級(jí)低于現(xiàn)有運(yùn)算符，現(xiàn)有運(yùn)算符才進(jìn)棧。循環(huán)結(jié)束后，將棧中的運(yùn)算符全部依次輸出，最后將后綴表達(dá)式傳遞給求值函數(shù)（countfor()），再銷毀棧。（ 4）求值函數(shù)中首先是利用strtod()函數(shù)將數(shù)字字符串轉(zhuǎn)換成double 類型的數(shù)字，然后構(gòu)建一個(gè)數(shù)字棧，將轉(zhuǎn)換后的數(shù)字傳遞到棧中，每當(dāng)遇到運(yùn)算符時(shí)，就從數(shù)字棧中“扔出”兩

3、個(gè)數(shù)字進(jìn)行相應(yīng)的運(yùn)算，循環(huán)結(jié)束后，將數(shù)字棧中的數(shù)字“扔出” ，并輸出成為表達(dá)式最終的結(jié)果。算法二：利用創(chuàng)建的兩個(gè)棧直接對(duì)表達(dá)式進(jìn)行計(jì)算。（ 1）分別構(gòu)建一個(gè) char 類型和一個(gè) double 類型的棧函數(shù)以及棧的相關(guān)函數(shù) （出棧函數(shù)、進(jìn)棧函數(shù)、創(chuàng)建棧函數(shù)、銷毀棧函數(shù)、判斷棧是否為空函數(shù)、看棧頂函數(shù)等）。（ 2）在 main 函數(shù)中讓用戶進(jìn)行輸入，將用戶輸入的字符串進(jìn)行循環(huán)、判斷（如果數(shù)字字符后面的是運(yùn)算符，則在數(shù)字字符后加“#”以便進(jìn)行區(qū)分；否則，繼續(xù)循環(huán)。）并將判斷后的字符串傳遞到新的數(shù)組中，循環(huán)結(jié)束后， 再將數(shù)組傳遞給中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)（Countfor ()）。（ 3）在 Co

4、untfor() 函數(shù)中先創(chuàng)建一個(gè)數(shù)字棧和一個(gè)符號(hào)棧，對(duì)表達(dá)式進(jìn)行循環(huán)，直到元素為 0 。在循環(huán)中如果元素為數(shù)字、 點(diǎn)或者 #，將元素賦給新的數(shù)組 Consist ，再判斷下一個(gè)元素是否為 #，若是則利用 strtod() 函數(shù)將數(shù)組中的字符串轉(zhuǎn)換成double 類型的數(shù)字， 然后數(shù)字進(jìn)棧， 清空數(shù)組Consist；否則，繼續(xù)判斷。若元素不為數(shù)字、點(diǎn)或者#，則先看棧頂，如果棧為空或棧頂元素為（或者棧頂元素為+或并且現(xiàn)有元素為* 、/ 或 %又或是現(xiàn)有元素為 （，則現(xiàn)有元素進(jìn)棧；否則，再對(duì)現(xiàn)有元素進(jìn)行判斷：如果現(xiàn)有元素為） ，運(yùn)算符出棧直到 （出棧；否則，運(yùn)算符出棧直到棧空或者棧頂元素的優(yōu)先級(jí)低

5、于現(xiàn)有運(yùn)算符，現(xiàn)有運(yùn)算符才進(jìn)棧。每當(dāng)有一個(gè)運(yùn)算符出棧，就從數(shù)棧中取兩個(gè)數(shù)與運(yùn)算符一起傳遞給Judge() 函數(shù) , 并將函數(shù)的返回值壓入棧中。循環(huán)結(jié)束后，將棧中的運(yùn)算符全部依次輸出，每當(dāng)有一個(gè)運(yùn)算符出棧，就從數(shù)棧中取兩個(gè)數(shù)與運(yùn)算符一起傳遞給Judge() 函數(shù) , 并將函數(shù)的返回值壓入棧中， 最后輸出數(shù)字棧中的數(shù)字成為表達(dá)式的最終結(jié)果，再銷毀棧。（ 4） Judge() 函數(shù)是利用 switch 語(yǔ)句對(duì)傳入進(jìn)來(lái)的運(yùn)算符進(jìn)行判斷，并將傳入的兩個(gè)數(shù)進(jìn)行相應(yīng)的運(yùn)算，并返回運(yùn)算結(jié)果。二、算法流程圖算法一：利用棧將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式再進(jìn)行計(jì)算。圖 1 為算法一中main() 函數(shù)的算法流程圖，主

6、要功能為：錄入字符串和區(qū)分?jǐn)?shù)字字符與運(yùn)算符字符。開始用戶輸入表達(dá)式對(duì)表達(dá)式進(jìn)行循環(huán)元素否元素為數(shù)是傳給數(shù)組是否傳給數(shù)組str_pass元素不是將新的表達(dá)式傳遞否是將一個(gè) #號(hào)傳給結(jié)束圖 1 中綴轉(zhuǎn)后綴表達(dá)式算法 main() 函數(shù)流程圖圖 2 為算法一中 Mid_Back() 函數(shù)的算法流程圖，主要功能為：將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。開始元素進(jìn)棧是出棧直到 ( 出聲明并創(chuàng)建一個(gè)棧是棧為空或棧頂將元素傳給數(shù)否元素對(duì)表達(dá)式進(jìn)行循環(huán)為 (是否出棧并賦給Ba_str圖 2 中綴轉(zhuǎn)后綴表達(dá)式算法Mid_Back() 函數(shù)流程圖圖 3 為算法一中countfor()函數(shù)的算法流程圖，主要功能為：根據(jù)后綴

7、表達(dá)式求出表達(dá)式的值。開始清空數(shù)組 Consist()調(diào)用 strtod()函數(shù)，結(jié)果進(jìn)棧聲明并創(chuàng)建數(shù)字棧是對(duì)表達(dá)式進(jìn)行循環(huán)下一個(gè)元素否元素為數(shù)元素不是是將元素賦給Consist字、點(diǎn)或否否表達(dá)式最終結(jié)果出棧從數(shù)字棧中“扔出”兩個(gè)數(shù)輸出結(jié)果利用 switch()語(yǔ)句判斷運(yùn)算運(yùn)算結(jié)果進(jìn)棧結(jié)束圖 3 中綴轉(zhuǎn)后綴表達(dá)式算法countfor()函數(shù)流程圖算法二：利用兩個(gè)棧（數(shù)字棧和符號(hào)棧）直接對(duì)表達(dá)式求值。圖 4 為算法二中main() 函數(shù)的算法流程圖，主要功能為：錄入字符串和區(qū)分?jǐn)?shù)字字符與運(yùn)算符字符。開始用戶輸入表達(dá)式對(duì)表達(dá)式進(jìn)行循環(huán)元素否元素為數(shù)是傳給數(shù)組是否傳給數(shù)組 str_pass元素不是將

8、新的表達(dá)式傳遞否是將一個(gè) #號(hào)傳給結(jié)束圖 4 表達(dá)式直接求值算法main() 函數(shù)流程圖圖 5 為算法二中Countfor ()函數(shù)的算法流程圖，主要功能為：利用兩個(gè)棧直接對(duì)表達(dá)式進(jìn)行取值計(jì)算。開始聲明并創(chuàng)建一個(gè)數(shù)清空數(shù)組調(diào)用 strtod函數(shù)，對(duì)表達(dá)式進(jìn)行循環(huán)否是元素為 #將出棧的兩個(gè)數(shù)和一個(gè)元素不否對(duì)符號(hào)棧進(jìn)行循環(huán)符號(hào)棧否表達(dá)式最終結(jié)果出棧輸出結(jié)果結(jié)束運(yùn)算符傳給Judge() ，并元素進(jìn)棧將元素傳給數(shù)組是出棧直到 ( 出是是棧為空或棧頂元素為數(shù)是否否元素為(字、點(diǎn)或否將出棧的兩個(gè)數(shù)和一個(gè)運(yùn)算符傳給Judge() ，并將出棧的兩個(gè)數(shù)和一個(gè)是運(yùn)算符傳給Judge() ，并棧為空或棧頂是為(否將

9、出棧的兩個(gè)數(shù)和一個(gè)運(yùn)算符傳給Judge() ，并元素進(jìn)棧圖 5 表達(dá)式直接求值算法Countfor ()函數(shù)流程圖圖 6 為算法二中 Judge() 函數(shù)的算法流程圖，主要功能為：判斷運(yùn)算符并根據(jù)判斷將兩個(gè)數(shù)進(jìn)行相應(yīng)的計(jì)算，返回計(jì)算結(jié)果。開始利用 switch 語(yǔ)句對(duì)傳進(jìn)來(lái)的運(yùn)算符進(jìn)行判斷并根據(jù)判斷對(duì)兩個(gè)數(shù)返回運(yùn)算結(jié)果結(jié)束圖 6 表達(dá)式直接求值算法Judge() 函數(shù)流程圖三、源代碼下面給出的是用一個(gè)棧對(duì)表達(dá)式中綴轉(zhuǎn)后綴再進(jìn)行運(yùn)算的算法實(shí)現(xiàn)的程序的源代碼：#include #include #include #include #define STACK_INIT_SIZE 10 )|ai=#)

10、|Ba_stri=#) )|Min_stri=#)/ 判斷 Min_stri是否為數(shù)字或者點(diǎn)、#，Consistj=Min_stri; /是，則傳入Consist數(shù)組，直至Min_stri為 #j+;i+;if(Min_stri=#) /如果 Min_stri為 #eod=strtod(Consist,NULL);/利用 strtod函數(shù)，將Consist數(shù)組中的字符串轉(zhuǎn)換成double 類型的數(shù)字Push(Od,eod); /eod進(jìn)棧for(j=0;j20;j+)/將 Consist數(shù)組循環(huán)清空Consistj=0;j=0;else -i;else/Min_stri是運(yùn)算符GetTop(O

11、p,eop); /看棧if(StackEmpty(Op)|eop=(|(eop=+|eop=-)&(Min_stri=*|Min_stri=%|Min_stri=/)| Min_stri=() Push(Op,Min_stri); /else將棧中已有的運(yùn)算符與現(xiàn)有的運(yùn)算符進(jìn)行比較if(Min_stri=) /如果現(xiàn)有的運(yùn)算符為)，Pop(Op,eop); /則棧中的運(yùn)算符出棧，for(;eop!=(;) /直到出棧的運(yùn)算符為(Pop(Od,eod); /一個(gè)運(yùn)算符出棧，數(shù)棧中就Pop 出兩個(gè)數(shù)，進(jìn)行運(yùn)算Od2=eod;Pop(Od,eod);Od1=eod;eod=Judge(eop,Od1

12、,Od2);/對(duì)運(yùn)算符進(jìn)行判斷，并根據(jù)判斷進(jìn)行運(yùn)算Push(Od,eod); /將函數(shù)的返回值壓入進(jìn)棧Pop(Op,eop);elsePop(Op,eop); /運(yùn)算符出棧Pop(Od,eod);/一個(gè)運(yùn)算符出棧，數(shù)棧中就Pop 出兩個(gè)數(shù)，進(jìn)行運(yùn)算Od2=eod;Pop(Od,eod);Od1=eod;eod=Judge(eop,Od1,Od2); /對(duì)運(yùn)算符進(jìn)行判斷，并根據(jù)判斷進(jìn)行運(yùn)算Push(Od,eod); /將函數(shù)的返回值壓入進(jìn)棧GetTop(Op,eop); /看棧頂if(StackEmpty(Op)|eop=(|(eop=+|eop=-)&(Min_stri=*|Min_stri=

13、%|Min_stri=/)|Min_stri=() Push(Op,Min_stri); elsePop(Op,eop); /運(yùn)算符出棧Pop(Od,eod);/一個(gè)運(yùn)算符出棧，數(shù)棧中就Pop 出兩個(gè)數(shù)，進(jìn)行運(yùn)算Od2=eod;Pop(Od,eod);Od1=eod;eod=Judge(eop,Od1,Od2); /對(duì)運(yùn)算符進(jìn)行判斷，并根據(jù)判斷進(jìn)行運(yùn)算Push(Od,eod); /將函數(shù)的返回值壓入進(jìn)棧Push(Op,Min_stri);for(;!StackEmpty(Op); /運(yùn)算符出棧，直到?？誔op(Op,eop); /運(yùn)算符出棧Pop(Od,eod); /一個(gè)運(yùn)算符出棧，數(shù)棧中就P

14、op出兩個(gè)數(shù)，進(jìn)行運(yùn)算Od2=eod;Pop(Od,eod);Od1=eod;eod=Judge(eop,Od1,Od2); /對(duì)運(yùn)算符進(jìn)行判斷，并根據(jù)判斷進(jìn)行運(yùn)算Push(Od,eod); /將函數(shù)的返回值壓入進(jìn)棧Pop(Od,eod);printf(=%f,eod); /輸出表達(dá)式最終結(jié)果DestroyStack(Od); /銷毀數(shù)字棧OdDestroyStack(Op); /銷毀字符棧Opdouble Judge(char c_Operator,double Od1,double Od2)double eod;switch(c_Operator) /判斷 c_Operator是什么運(yùn)算符

15、，并根據(jù)判斷進(jìn)行運(yùn)算case -:eod=Od1-Od2; break;/運(yùn)算符為減號(hào)，則兩數(shù)相減case +:eod=Od1+Od2; break; /運(yùn)算符為加號(hào)，則兩數(shù)相加case *:eod=Od1*Od2; break; /運(yùn)算符為乘號(hào)，則兩數(shù)相乘case /:eod=Od1/Od2;break; /運(yùn)算符為除號(hào)，則兩數(shù)相除case %:eod=(int)Od1%(int)Od2;break; /運(yùn)算符為取余號(hào)，則兩數(shù)相除取余/degault:return eod; /返回運(yùn)算結(jié)果四、運(yùn)行結(jié)果算法一：利用棧將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式再進(jìn)行計(jì)算。將表達(dá)式 “ +2*（32-54/9

16、）-7%5+3=”錄入， 先將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式，#是為了區(qū)分?jǐn)?shù)字與符號(hào)，得到結(jié)果為“56.400000 ”，為正確結(jié)果。圖 7 中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式再進(jìn)行計(jì)算算法的運(yùn)行結(jié)果圖算法二：利用創(chuàng)建的兩個(gè)棧直接對(duì)表達(dá)式進(jìn)行計(jì)算。將表達(dá)式“ +2* （32-54/9 ）-7%5+3=”錄入，得到結(jié)果為“56.400000 ”，為正確結(jié)果。圖 8 兩個(gè)棧直接對(duì)表達(dá)式進(jìn)行計(jì)算算法的運(yùn)行結(jié)果圖五、遇到的問題及解決這部分我主要遇到了如下兩個(gè)問題，其內(nèi)容與解決方法如下所列：在第二個(gè)算法（表達(dá)式直接求值）中輸入表達(dá)式后，運(yùn)算結(jié)果不正確：圖 9 遇到的問題1問題 1 的解決方法：先判斷“病根”在哪里，

17、首先在數(shù)字棧和符號(hào)棧的Pop() 函數(shù)和 Push()函數(shù)中分別加輸出語(yǔ)句，觀察數(shù)字與字符是否正常出入棧，具體如圖10。圖 10 解決問題1 中，在棧中添加輸出語(yǔ)句再次運(yùn)行后，結(jié)果如圖11。圖 11 解決問題 1 中，在棧中添加輸出語(yǔ)句后的運(yùn)行結(jié)果根據(jù)圖 11，可判斷出第一個(gè)數(shù)字1 并沒有成功的入棧反而被替換成了0，造成這樣結(jié)果的原因可能有以下幾點(diǎn)：（ 1）在算法的main() 函數(shù)中，在對(duì)表達(dá)式中數(shù)字字符與運(yùn)算符進(jìn)行區(qū)分操作時(shí)，由于考慮的不全面產(chǎn)生邏輯錯(cuò)誤，這會(huì)使得在接下來(lái)的運(yùn)行中在靠 #來(lái)辨別語(yǔ)速的函數(shù)中會(huì)產(chǎn)生錯(cuò)誤；（2）在算法的Countfor()函數(shù)中，運(yùn)算符優(yōu)先級(jí)的判別可能出現(xiàn)邏輯性

18、錯(cuò)誤，使得運(yùn)算不正確；（3）在算法的Countfor()函數(shù)中，運(yùn)用 strtod()函數(shù)方法不正確，使得字符類型轉(zhuǎn)化成double 類型是發(fā)生錯(cuò)誤，然后再將錯(cuò)誤的數(shù)字傳進(jìn)棧中。根據(jù)判斷依次進(jìn)行調(diào)試，首先在main() 函數(shù)中對(duì)代碼進(jìn)行檢驗(yàn)，觀察是否有邏輯性錯(cuò)誤，結(jié)果發(fā)現(xiàn)在對(duì)表達(dá)式中數(shù)字字符與運(yùn)算符進(jìn)行區(qū)分操作時(shí)，沒有考慮到元素為( 和元素為 ) 時(shí)的情況，使得在添加#號(hào)時(shí)（前和）后都添加了 #，而這是不符合設(shè)計(jì)思想的，所以進(jìn)行調(diào)節(jié)：在判斷了當(dāng)前元素是為數(shù)字或者點(diǎn)之后，在對(duì)下一個(gè)元素進(jìn)行判斷，看其是否為運(yùn)算符，如果是則添加#號(hào)，如果不是就繼續(xù)循環(huán)。 在對(duì)代碼進(jìn)行一番修改之后再運(yùn)行，運(yùn)行結(jié)果正常

19、， 說(shuō)明問題解決了。在第一個(gè)算法（中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式再求值）中輸入表達(dá)式（ 76 9+6*（ 1+1）=）后，中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式結(jié)果不正確+號(hào)應(yīng)該在前，如圖12。圖 12 遇到的問題2問題 2 的解決方法：如同解決問題一一樣，判斷“病根”在哪里，首先在數(shù)字棧和符號(hào)棧的 Pop() 函數(shù)和 Push() 函數(shù)中分別加輸出語(yǔ)句，觀察數(shù)字與字符是否正常出入棧，具體如圖 10。再次運(yùn)行后，結(jié)果如圖13。圖 13 解決問題 2 中，在棧中添加輸出語(yǔ)句后的運(yùn)行結(jié)果根據(jù)圖 13 所示，數(shù)字字符與運(yùn)算符加#號(hào)區(qū)分正確，所以，可以排除main() 函數(shù)在對(duì)表達(dá)式中數(shù)字字符與運(yùn)算符進(jìn)行區(qū)分操作時(shí)，由于考慮的不全面產(chǎn)生邏輯錯(cuò)誤，那么接下來(lái)考慮是否是Mid_Back() 函數(shù)中判斷符號(hào)優(yōu)先級(jí)時(shí)，由于考慮的不全面而產(chǎn)生的邏輯性的錯(cuò)誤。接下來(lái)針對(duì)猜想結(jié)合圖13 對(duì)程