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

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)行判斷來將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的函數(shù)。函數(shù)中利用構(gòu)建的棧以及棧的相關(guān)函數(shù)對(duì)運(yùn)

2、算符進(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ù)字棧中“扔出”兩個(gè)數(shù)字進(jìn)行相應(yīng)的運(yùn)算，循環(huán)結(jié)束后，將數(shù)字棧中

3、的數(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）在Countfor()函數(shù)中先創(chuàng)建一個(gè)數(shù)字棧和一個(gè)符號(hào)棧，對(duì)表達(dá)式進(jìn)行循環(huán)

4、，直到元素為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í)低于現(xiàn)有運(yùn)算符，現(xiàn)有運(yùn)算符才進(jìn)棧。每當(dāng)有一個(gè)運(yùn)算符出棧，就從數(shù)棧中取兩個(gè)數(shù)與運(yùn)算符一起傳遞給Judge()函

5、數(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語句對(duì)傳入進(jìn)來的運(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ù)的算法流程圖，主要功能為：錄入字符串和區(qū)分?jǐn)?shù)字字符與運(yùn)算符字符。是否是將一個(gè)#號(hào)傳給數(shù)組str_pass元素不是數(shù)字或.傳給數(shù)組str_pass，

6、原數(shù)組下腳標(biāo)+1否傳給數(shù)組str_pass將新的表達(dá)式傳遞給Countfor ()函數(shù)是對(duì)表達(dá)式進(jìn)行循環(huán)開始用戶輸入表達(dá)式元素為0元素為數(shù)字或.否結(jié)束圖1 中綴轉(zhuǎn)后綴表達(dá)式算法main()函數(shù)流程圖圖2為算法一中Mid_Back()函數(shù)的算法流程圖，主要功能為：將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。將棧進(jìn)行循環(huán)棧不為空否是輸出后綴表達(dá)式結(jié)束將表達(dá)式傳給求值函數(shù)countfor()運(yùn)算符出棧否聲明并創(chuàng)建一個(gè)棧開始對(duì)表達(dá)式進(jìn)行循環(huán)將元素傳給數(shù)組Ba_str是是現(xiàn)有元素不為=元素為數(shù)字、點(diǎn)或者#看棧頂是元素進(jìn)棧否棧為空或棧頂為(或+、-且元素為*、/、%或者元素為(元素為)出棧直到(出棧是否出棧并賦給Ba_

7、str看棧頂是元素進(jìn)棧否出棧，將現(xiàn)有元素進(jìn)棧否棧為空或棧頂為(或+、-且元素為*、/、%或者元素為(圖2中綴轉(zhuǎn)后綴表達(dá)式算法Mid_Back()函數(shù)流程圖圖3為算法一中countfor()函數(shù)的算法流程圖，主要功能為：根據(jù)后綴表達(dá)式求出表達(dá)式的值。清空數(shù)組Consist()調(diào)用strtod()函數(shù)，結(jié)果進(jìn)棧運(yùn)算結(jié)果進(jìn)棧將元素賦給Consist下一個(gè)元素為#是否利用switch()語句判斷運(yùn)算符并進(jìn)行相應(yīng)運(yùn)算元素為數(shù)字、點(diǎn)或者#是是否從數(shù)字棧中“扔出”兩個(gè)數(shù)開始結(jié)束 輸出結(jié)果聲明并創(chuàng)建數(shù)字棧表達(dá)式最終結(jié)果出棧對(duì)表達(dá)式進(jìn)行循環(huán)元素不為0否 圖3中綴轉(zhuǎn)后綴表達(dá)式算法countfor()函數(shù)流程圖算法

8、二： 利用兩個(gè)棧（數(shù)字棧和符號(hào)棧）直接對(duì)表達(dá)式求值。 圖4為算法二中main()函數(shù)的算法流程圖，主要功能為：錄入字符串和區(qū)分?jǐn)?shù)字字符與運(yùn)算符字符。是否是將一個(gè)#號(hào)傳給數(shù)組str_pass元素不是數(shù)字或.傳給數(shù)組str_pass，原數(shù)組下腳標(biāo)+1否傳給數(shù)組str_pass將新的表達(dá)式傳遞給Countfor ()函數(shù)是對(duì)表達(dá)式進(jìn)行循環(huán)開始用戶輸入表達(dá)式元素為0元素為數(shù)字或.否結(jié)束圖4表達(dá)式直接求值算法main()函數(shù)流程圖圖5為算法二中Countfor ()函數(shù)的算法流程圖，主要功能為：利用兩個(gè)棧直接對(duì)表達(dá)式進(jìn)行取值計(jì)算。將出棧的兩個(gè)數(shù)和一個(gè)運(yùn)算符傳給Judge()，并將返回值壓進(jìn)數(shù)棧元素進(jìn)棧將

9、出棧的兩個(gè)數(shù)和一個(gè)運(yùn)算符傳給Judge()，并將返回值壓進(jìn)數(shù)棧將出棧的兩個(gè)數(shù)和一個(gè)運(yùn)算符傳給Judge()，并將返回值壓進(jìn)數(shù)棧否否是否棧為空或棧頂為(或+、-且元素為*、/、%或者元素為(否元素為)出棧直到(出棧是是元素進(jìn)棧是清空數(shù)組Consist調(diào)用strtod函數(shù)，并將返回值壓進(jìn)數(shù)棧是是對(duì)表達(dá)式進(jìn)行循環(huán)開始聲明并創(chuàng)建一個(gè)數(shù)字棧和一個(gè)符號(hào)棧元素不為=否結(jié)束對(duì)符號(hào)棧進(jìn)行循環(huán)表達(dá)式最終結(jié)果出棧符號(hào)棧非空否輸出結(jié)果將出棧的兩個(gè)數(shù)和一個(gè)運(yùn)算符傳給Judge()，并將返回值壓進(jìn)數(shù)棧元素為數(shù)字、點(diǎn)或者#將元素傳給數(shù)組Consist是元素為#否棧為空或棧頂為(或+、-且元素為*、/、%或者元素為(圖5表達(dá)

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

11、lib.h"#define STACK_INIT_SIZE 10/存儲(chǔ)空間初始分配量#define STACKINCREMENT 10/存儲(chǔ)空間分配增量typedef struct/構(gòu)建數(shù)字棧 double *base; /在棧構(gòu)造之前和銷毀之后，base的值為NULL double *top; /棧的頂指針 int stacksize; /當(dāng)前已分配的存儲(chǔ)空間，以元素為單位Od;void InitStack(Od &S)/創(chuàng)建一個(gè)棧 S.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double);/分配類型為double if(

12、!S.base) printf("OVERFLOW!"); /存儲(chǔ)分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE;/InitStackstatic GetTop(Od S,double &e) /看棧頂，若棧非空，用e返回S的棧頂元素，并返回1；否則，0 if(S.top>S.base) /棧不空 e=*(S.top-1);/將棧頂元素賦給e return 1; else return 0; /GetTopvoid Push(Od &S,double e)/插入元素e為新的棧頂if(S.top-S.base

13、>=S.stacksize) /棧滿，追加存儲(chǔ) S.base=(double*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(double);if(!S.base) exit(0); /存儲(chǔ)分配失敗S.top=S.base+S.stacksize;/修改站頂指針，指向新的棧頂S.stacksize+=STACKINCREMENT;/更新當(dāng)前已分配的存儲(chǔ)空間 *(S.top)+=e; 將e入棧，成為新的棧頂元素，棧頂指針上移1個(gè)存儲(chǔ)單元/Pushstatic Pop(Od &S,double &e)/刪除S的棧頂元素，

14、用e返回其值 if(S.top=S.base) return 0; e=*-S.top; return 1;/Popvoid DestroyStack(Od &S)/銷毀棧S free(S.base);/釋放?？臻g S.top=S.base=NULL;/棧頂、棧底指針均為空 S.stacksize=0;/當(dāng)前已分配內(nèi)存空間為0/DestroyStackstatic StackEmpty(Od S)/判斷棧是否為空，?？辗祷?，否則，返回0。 if(S.top=S.base) /空棧條件 return 1; else return 0;/StackEmptytypedef struct/

15、構(gòu)建字符棧 char *base;/在棧構(gòu)造之前和銷毀之后，base的值為NULL char *top;/棧的頂指針 int stacksize;/當(dāng)前已分配的存儲(chǔ)空間，以元素為單位Op;void InitStack(Op &S)/創(chuàng)建一個(gè)棧 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);/分配類型為char if(!S.base) printf("OVERFLOW!");/存儲(chǔ)分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE;/InitStackstatic Get

16、Top(Op S,char &e)/看棧頂，若棧非空，用e返回S的棧頂元素，并返回1；否則，0if(S.top>S.base) e=*(S.top-1);/將棧頂元素賦給e return 1; else return 0;/GetTopvoid Push(Op &S,char e)/插入元素e為新的棧頂 if(S.top-S.base>=S.stacksize) /棧滿，追加存儲(chǔ) S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base) exit(0);/存

17、儲(chǔ)分配失敗S.top=S.base+S.stacksize; /修改站頂指針，指向新的棧頂S.stacksize+=STACKINCREMENT;/更新當(dāng)前已分配的存儲(chǔ)空間 *(S.top)+=e;/將e入棧，成為新的棧頂元素，棧頂指針上移1個(gè)存儲(chǔ)單元/Pushstatic Pop(Op &S,char &e)/刪除S的棧頂元素，用e返回其值 if(S.top=S.base) return 0; e=*-S.top; return 1;/Popvoid DestroyStack(Op &S)/銷毀棧S free(S.base);/釋放?？臻g S.top=S.base=N

18、ULL;/棧頂、棧底指針均為空 S.stacksize=0;/當(dāng)前已分配內(nèi)存空間為0/DestroyStackstatic StackEmpty(Op S)/判斷棧是否為空，?？辗祷?，否則，返回0。 if(S.top=S.base) /空棧條件 return 1; else return 0;/StackEmptyint main(int argc, double* argv) void Mid_Back(char a);/中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)int i=0; /str數(shù)組的下腳標(biāo) int j=0; /str_pass數(shù)組的下腳標(biāo) char str50; /接受用戶輸入字符的數(shù)組 ch

19、ar str_pass50; /接受數(shù)字字符的數(shù)組 printf("請(qǐng)輸入算數(shù)表達(dá)式：n"); scanf("%s",&str); /輸入表達(dá)式 while(stri!='0') /對(duì)str數(shù)組進(jìn)行循環(huán)，知道stri為'0' if(stri>='0'&&stri<='9')|stri='.') /如果stri是數(shù)字或者點(diǎn) str_passj=stri; /則將其賦給str_pass數(shù)組 j+; i+; if(!(stri>='

20、0'&&stri<='9')|stri='.')/再對(duì)下一個(gè)數(shù)組中的元素進(jìn)行判斷 str_passj='#' /如果不是數(shù)字或者點(diǎn)，則添加# j+; else str_passj=stri; /將運(yùn)算符傳到數(shù)組中 j+; i+; Mid_Back(str_pass);/將表達(dá)式傳入中轉(zhuǎn)后綴函數(shù)中return 0;/*中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)*/void Mid_Back(char a)/中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù) int i=0;/數(shù)組a下腳標(biāo) int j=0;/數(shù)組Ba_str下腳標(biāo) char Ba_str50;

21、 char e; Op Op;/聲明符號(hào)棧函數(shù) InitStack(Op);/創(chuàng)建一個(gè)符號(hào)棧 void countfor(char Ba_str);/聲明求值函數(shù) for(i=0;ai!='='i+) /對(duì)數(shù)組a進(jìn)行循環(huán) if(ai>='0'&&ai<='9')|ai='.'|ai='#')/判斷ai是否為數(shù)字、點(diǎn)或者#，是則將元素傳遞到Ba_str數(shù)組中；否則，再次進(jìn)行判斷 Ba_strj=ai; printf("%c",Ba_strj); j+;else GetT

22、op(Op,e);/看棧頂 if(StackEmpty(Op)|e='('|(e='+'|e='-')&&(ai='*'|ai='%'|ai='/')|ai='(') Push(Op,ai); else if(ai=')') /如果現(xiàn)有元素為 ) ，則運(yùn)算符出棧 Pop(Op,e); for(;e!='(') /直到出棧元素為( Ba_strj=e;/將出棧的運(yùn)算符賦給Ba_strj printf("%c",Ba_s

23、trj);/ j+; Pop(Op,e);/運(yùn)算符出棧 else /如果現(xiàn)有元素不為 ),則運(yùn)算符出棧 Pop(Op,e); Ba_strj=e; /將出棧的運(yùn)算符賦給Ba_strj printf("%c",Ba_strj); j+; GetTop(Op,e);/看棧頂 if(StackEmpty(Op)|e='('|(e='+'|e='-')&&(ai='*'|ai='%'|ai='/')|ai='(') /對(duì)棧頂元素與現(xiàn)有元素進(jìn)行優(yōu)先級(jí)比較，符

24、合以上情況的，現(xiàn)有元素進(jìn)棧 Push(Op,ai); else /否則運(yùn)算符出棧 Pop(Op,e); Push(Op,ai);/將現(xiàn)有元素放到棧中 Ba_strj=e; /將出棧的運(yùn)算符賦給Ba_strj printf("%c",Ba_strj); j+; while(!StackEmpty(Op)/輸出棧中所有運(yùn)算符Pop(Op,e); Ba_strj=e; /將出棧的運(yùn)算符賦給Ba_strj printf("%c",Ba_strj);/ j+; DestroyStack(Op);/銷毀棧 countfor(Ba_str);/將數(shù)組傳遞給求值函數(shù)/*

25、表達(dá)式求值函數(shù)*/void countfor(char Ba_str) Od Od;/聲明數(shù)字棧函數(shù) InitStack(Od);/創(chuàng)建一個(gè)數(shù)字棧 int i=0;/數(shù)組Ba_str下腳標(biāo) int j=0;/數(shù)組Consist下腳標(biāo) double e; int k=0; double Od1,Od2; char Consist20; for(i=0;Ba_stri!='0'i+) /對(duì)數(shù)組進(jìn)行循環(huán) if(Ba_stri>='0'&&Ba_stri<='9')|Ba_stri='.'|Ba_stri=&#

26、39;#') /如果元素為數(shù)字、點(diǎn)或者#，則將元素賦給Consistj Consistj=Ba_stri; j+; i+; if(Ba_stri='#') /如果元素為# e=strtod(Consist,NULL);/利用strtod函數(shù)將字符串轉(zhuǎn)換成double類型的數(shù)字 Push(Od,e);/數(shù)字進(jìn)棧 for(j=0;j<20;j+)/清空數(shù)組Consist以便重新使用 Consistj='0' j=0; else -i; else /否則，從數(shù)字棧中取兩個(gè)數(shù) Od1=Od2=0; Pop(Od,e); Od2=e; Pop(Od,e);

27、Od1=e; switch(Ba_stri) /判斷運(yùn)算符 case '-':e=Od1-Od2;Push(Od,e);break;/運(yùn)算符為減號(hào)，則兩數(shù)相減 case '+':e=Od1+Od2;Push(Od,e);break; /運(yùn)算符為加號(hào)，則兩數(shù)相加 case '*':e=Od1*Od2;Push(Od,e);break; /運(yùn)算符為乘號(hào)，則兩數(shù)相乘 case '/':e=Od1/Od2;Push(Od,e);break; /運(yùn)算符為除號(hào)，則兩數(shù)相除 case '%':k=(int)Od1%(int)Od

28、2;Push(Od,k);break; /運(yùn)算符為取余號(hào)，則兩數(shù)相除取余/ degault: Pop(Od,e);/將表達(dá)式的結(jié)果“扔出”棧 printf("=%f",e);/對(duì)表達(dá)式的結(jié)果進(jìn)行輸出 DestroyStack(Od);下面給出的是用兩個(gè)棧直接對(duì)表達(dá)式進(jìn)行運(yùn)算的算法實(shí)現(xiàn)的程序的源代碼：#include "stdafx.h"#include "stdio.h"#include "malloc.h"#include "stdlib.h"#define STACK_INIT_SIZE 1

29、0/存儲(chǔ)空間初始分配量#define STACKINCREMENT 10/存儲(chǔ)空間分配增量typedef struct double *base; /在棧構(gòu)造之前和銷毀之后，base的值為NULL double *top; /棧的頂指針 int stacksize;/當(dāng)前已分配的存儲(chǔ)空間，以元素為單位Od;void InitStack(Od &S)/創(chuàng)建一個(gè)棧 S.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double);/分配類型為double if(!S.base) printf("OVERFLOW!"); /存儲(chǔ)

30、分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE;/InitStackstatic GetTop(Od S,double &e)/看棧頂，若棧非空，用e返回S的棧頂元素，并返回1；否則，0 if(S.top>S.base) e=*(S.top-1); return 1; else return 0;/GetTopvoid Push(Od &S,double e)/插入元素e為新的棧頂 if(S.top-S.base>=S.stacksize) /如果棧滿，追加存儲(chǔ) S.base=(double *)realloc(S.ba

31、se,(S.stacksize+STACKINCREMENT)*sizeof(double); if(!S.base) exit(0); /存儲(chǔ)分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *(S.top)+=e;/Pushstatic Pop(Od &S,double &e)/刪除S的棧頂元素，用e返回其值 if(S.top=S.base) return 0; e=*-S.top; return 1;/Popvoid DestroyStack(Od &S)/銷毀棧S free(S.base);/

32、釋放?？臻g S.top=S.base=NULL;/棧頂、棧底指針均為空 S.stacksize=0;/當(dāng)前已分配內(nèi)存空間為0/DestroyStackstatic StackEmpty(Od S)/判斷棧是否為空，?？辗祷?，否則，返回0。 if(S.top=S.base) /空棧條件 return 1; else return 0;/StackEmpty/*/typedef struct char *base;/在棧構(gòu)造之前和銷毀之后，base的值為NULL char *top;/棧的頂指針 int stacksize;/當(dāng)前已分配的存儲(chǔ)空間，以元素為單位Op;void InitStack(

33、Op &S)/創(chuàng)建一個(gè)棧 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);/分配類型為char if(!S.base) printf("OVERFLOW!");/存儲(chǔ)分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE;/InitStackstatic GetTop(Op S,char &e) /看棧頂，若棧非空，用e返回S的棧頂元素，并返回1；否則，0if(S.top>S.base) e=*(S.top-1); return 1; else return 0

34、;/GetTopvoid Push(Op &S,char e)/插入元素e為新的棧頂 if(S.top-S.base>=S.stacksize) /如果棧滿，追加存儲(chǔ) S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char); if(!S.base) exit(0); /存儲(chǔ)分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *(S.top)+=e;/Pushstatic Pop(Op &S,char &e)/刪

35、除S的棧頂元素，用e返回其值 if(S.top=S.base) return 0; e=*-S.top; return 1;/Popvoid DestroyStack(Op &S)/銷毀棧S free(S.base);/釋放?？臻g S.top=S.base=NULL;/棧頂、棧底指針均為空 S.stacksize=0;/當(dāng)前已分配內(nèi)存空間為0/DestroyStackstatic StackEmpty(Op S)/判斷棧是否為空，是返回1，否則返回0。 if(S.top=S.base)/空棧條件 return 1; else return 0;/StackEmpty/*/int mai

36、n(int argc, double* argv) void Mid_Back(char a); int i=0; /str數(shù)組的下腳標(biāo) int j=0; /str_pass數(shù)組的下腳標(biāo) char str50; /接受用戶輸入字符的數(shù)組 char str_pass50; /接受數(shù)字字符的數(shù)組 void Countfor(char Min_str);/進(jìn)行表達(dá)式運(yùn)算的函數(shù) printf("請(qǐng)輸入算數(shù)表達(dá)式：n"); scanf("%s",&str); /輸入表達(dá)式 while(stri!='0') /對(duì)str數(shù)組進(jìn)行循環(huán)，知道str

37、i為'0' if(stri>='0'&&stri<='9')|stri='.') /如果stri是數(shù)字或者點(diǎn) str_passj=stri; /則將其賦給str_pass數(shù)組 j+; i+; if(!(stri>='0'&&stri<='9')|stri='.')/再對(duì)下一個(gè)數(shù)組中的元素進(jìn)行判斷 str_passj='#' /如果不是數(shù)字或者點(diǎn)，則添加# j+; else str_passj=stri; /將運(yùn)算

38、符傳到數(shù)組中 j+; i+; Countfor(str_pass); /將表達(dá)式傳入中轉(zhuǎn)后綴函數(shù)中 return 0;/*表達(dá)式計(jì)算函數(shù)*/void Countfor(char Min_str) Op Op; Od Od; InitStack(Op); /創(chuàng)建一個(gè)Op棧 InitStack(Od); /創(chuàng)建一個(gè)Od棧 double Judge(char c_Operator,double Od1,double Od2);/判斷運(yùn)算符的函數(shù) double eod; char eop; double Od1,Od2; int i=0; /Min_str數(shù)組的下腳標(biāo) int j=0; /Consis

39、t數(shù)組的下腳標(biāo) char Consist20; /接受數(shù)字字符的數(shù)組 for(i=0;Min_stri!='='i+)/對(duì)Min_str數(shù)組進(jìn)行循環(huán) if(Min_stri>='0'&&Min_stri<='9')|Min_stri='.'|Min_stri='#')/判斷Min_stri是否為數(shù)字或者點(diǎn)、#， Consistj=Min_stri; /是，則傳入Consist數(shù)組，直至Min_stri為# j+; i+; if(Min_stri='#') /如果Min_s

40、tri為# eod=strtod(Consist,NULL);/利用strtod函數(shù)，將Consist數(shù)組中的字符串轉(zhuǎn)換成double類型的數(shù)字 Push(Od,eod); /eod進(jìn)棧 for(j=0;j<20;j+)/將Consist數(shù)組循環(huán)清空 Consistj='0' j=0; else -i; else /Min_stri是運(yùn)算符 GetTop(Op,eop); /看棧 if(StackEmpty(Op)|eop='('|(eop='+'|eop='-')&&(Min_stri='*'

41、;|Min_stri='%'|Min_stri='/')| Min_stri='(') Push(Op,Min_stri); /將棧中已有的運(yùn)算符與現(xiàn)有的運(yùn)算符進(jìn)行比較 else 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

42、; eod=Judge(eop,Od1,Od2);/對(duì)運(yùn)算符進(jìn)行判斷，并根據(jù)判斷進(jìn)行運(yùn)算 Push(Od,eod); /將函數(shù)的返回值壓入進(jìn)棧 Pop(Op,eop); else Pop(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='('|(e

43、op='+'|eop='-')&&(Min_stri='*'|Min_stri='%'|Min_stri='/')|Min_stri='(') Push(Op,Min_stri); else Pop(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); /

44、將函數(shù)的返回值壓入進(jìn)棧 Push(Op,Min_stri); for(;!StackEmpty(Op); /運(yùn)算符出棧，直到?？?Pop(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)棧 Pop(Od,eod); printf("=%f",eod); /輸出表達(dá)式最終結(jié)果 DestroyStack(Od); /銷毀

45、數(shù)字棧Od DestroyStack(Op); /銷毀字符棧Opdouble Judge(char c_Operator,double Od1,double Od2) double eod; switch(c_Operator) /判斷c_Operator是什么運(yùn)算符，并根據(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 &

46、#39;/':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á)式“3.4+2*（32-54/9）-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á)式“3.4+2*（32-54/9）-7%5+3=”錄入，得到結(jié)果為“56.400000”，為正確結(jié)果。圖8 兩個(gè)棧直接對(duì)表達(dá)式進(jìn)行計(jì)算算法的運(yùn)行結(jié)果圖五、遇到的問題及解決這部分我主要遇到了如下兩個(gè)問題，其內(nèi)容與解決方法如下所列：l 在第二個(gè)算法（表達(dá)式直接求值）中輸入表達(dá)式后，運(yùn)算結(jié)果不正確： 圖9 遇到的問題1問題1的解決方法：先判斷“病根”在哪里，首先在數(shù)字棧和符號(hào)棧的Pop()函數(shù)