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

./一、設(shè)計(jì)思想算法一：利用棧將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式再進(jìn)行計(jì)算?！?構(gòu)造char類型的棧函數(shù)以及棧的相關(guān)函數(shù)〔出棧函數(shù)、進(jìn)棧函數(shù)、創(chuàng)建棧函數(shù)、銷毀棧函數(shù)、判斷棧是否為空函數(shù)、看棧頂函數(shù)等?！?在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<>?！?中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)是利用運(yùn)算符的優(yōu)先級(jí)進(jìn)行判斷來(lái)將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的函數(shù)。函數(shù)中利用構(gòu)建的棧以及棧的相關(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<>,再銷毀棧?！?求值函數(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ù)字棧中的數(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ù)等?！?在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<>?！?在Countfor<>函數(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)算符出棧直到‘〔’〔4Judge<>函數(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ù)的算法流程圖,主要功能為：錄入字符串和區(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)開(kāi)始用戶輸入表達(dá)式元素為’\0元素為數(shù)字或’.’否結(jié)束圖1中綴轉(zhuǎn)后綴表達(dá)式算法main<>函數(shù)流程圖圖2為算法一中Mid_Back<>函數(shù)的算法流程圖,主要功能為：將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。將棧進(jìn)行循環(huán)將棧進(jìn)行循環(huán)棧不為空否是輸出后綴表達(dá)式結(jié)束將表達(dá)式傳給求值函數(shù)countfor<>運(yùn)算符出棧否聲明并創(chuàng)建一個(gè)棧開(kāi)始對(duì)表達(dá)式進(jìn)行循環(huán)將元素傳給數(shù)組Ba_str[]是是現(xiàn)有元素不為’=’元素為數(shù)字、點(diǎn)或者’#’看棧頂是元素進(jìn)棧否棧為空或棧頂為’<’或’+’、’-’且元素為’*’、’/’、’%’或者元素為’<’元素為’>’出棧直到’<’出棧是否出棧并賦給Ba_str[]看棧頂是元素進(jìn)棧否出棧,將現(xiàn)有元素進(jìn)棧否棧為空或棧頂為’<’或’+’、’-’且元素為’*’、’/’、’%’或者元素為’<’圖2中綴轉(zhuǎn)后綴表達(dá)式算法Mid_Back<>函數(shù)流程圖圖3為算法一中countfor<>函數(shù)的算法流程圖,主要功能為：根據(jù)后綴表達(dá)式求出表達(dá)式的值。清空數(shù)組Consist<>清空數(shù)組Consist<>調(diào)用strtod<>函數(shù),結(jié)果進(jìn)棧運(yùn)算結(jié)果進(jìn)棧將元素賦給Consist[]下一個(gè)元素為’#’是否利用switch<>語(yǔ)句判斷運(yùn)算符并進(jìn)行相應(yīng)運(yùn)算元素為數(shù)字、點(diǎn)或者’#’是是否從數(shù)字棧中"扔出"兩個(gè)數(shù)開(kāi)始結(jié)束輸出結(jié)果聲明并創(chuàng)建數(shù)字棧表達(dá)式最終結(jié)果出棧對(duì)表達(dá)式進(jìn)行循環(huán)元素不為’\0否圖3中綴轉(zhuǎn)后綴表達(dá)式算法countfor<>函數(shù)流程圖算法二：利用兩個(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)開(kāi)始用戶輸入表達(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ù)棧將出棧的兩個(gè)數(shù)和一個(gè)運(yùn)算符傳給Judge<>,并將返回值壓進(jìn)數(shù)棧元素進(jìn)棧將出棧的兩個(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)開(kāi)始聲明并創(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á)式直接求值算法Countfor<>函數(shù)流程圖圖6為算法二中Judge<>函數(shù)的算法流程圖,主要功能為：判斷運(yùn)算符并根據(jù)判斷將兩個(gè)數(shù)進(jìn)行相應(yīng)的計(jì)算,返回計(jì)算結(jié)果。開(kāi)始開(kāi)始結(jié)束利用switch語(yǔ)句對(duì)傳進(jìn)來(lái)的運(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"stdlib.h"#defineSTACK_INIT_SIZE10//存儲(chǔ)空間初始分配量#defineSTACKINCREMENT10//存儲(chǔ)空間分配增量typedefstruct{//構(gòu)建數(shù)字棧double*base;//在棧構(gòu)造之前和銷毀之后,base的值為NULLdouble*top;//棧的頂指針intstacksize;//當(dāng)前已分配的存儲(chǔ)空間,以元素為單位}Od;voidInitStack<Od&S>{//創(chuàng)建一個(gè)棧S.base=<double*>malloc<STACK_INIT_SIZE*sizeof<double>>;//分配類型為doubleif<!S.base>{printf<"OVERFLOW!">;//存儲(chǔ)分配失敗}S.top=S.base;S.stacksize=STACK_INIT_SIZE;}//InitStackstaticGetTop<OdS,double&e>{//看棧頂,若棧非空,用e返回S的棧頂元素,并返回1；否則,0if<S.top>S.base>//棧不空{(diào)e=*<S.top-1>;//將棧頂元素賦給ereturn1;}elsereturn0;}//GetTopvoidPush<Od&S,doublee>{//插入元素e為新的棧頂if<S.top-S.base>=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ǔ)單元}//PushstaticPop<Od&S,double&e>{//刪除S的棧頂元素,用e返回其值if<S.top==S.base>return0;e=*--S.top;return1;}//PopvoidDestroyStack<Od&S>{//銷毀棧Sfree<S.base>;//釋放?？臻gS.top=S.base=NULL;//棧頂、棧底指針均為空S.stacksize=0;//當(dāng)前已分配存空間為0}//DestroyStackstaticStackEmpty<OdS>{//判斷棧是否為空,?？辗祷?,否則,返回0。if<S.top==S.base>//空棧條件 return1;else return0;}//StackEmptytypedefstruct{//構(gòu)建字符棧char*base;//在棧構(gòu)造之前和銷毀之后,base的值為NULLchar*top;//棧的頂指針intstacksize;//當(dāng)前已分配的存儲(chǔ)空間,以元素為單位}Op;voidInitStack<Op&S>{//創(chuàng)建一個(gè)棧S.base=<char*>malloc<STACK_INIT_SIZE*sizeof<char>>;//分配類型為charif<!S.base>{ printf<"OVERFLOW!">;//存儲(chǔ)分配失敗}S.top=S.base;S.stacksize=STACK_INIT_SIZE;}//InitStackstaticGetTop<OpS,char&e>{//看棧頂,若棧非空,用e返回S的棧頂元素,并返回1；否則,0 if<S.top>S.base>{ e=*<S.top-1>;//將棧頂元素賦給ereturn1;}elsereturn0;}//GetTopvoidPush<Op&S,chare>{//插入元素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;//更新當(dāng)前已分配的存儲(chǔ)空間}*<S.top>++=e;//將e入棧,成為新的棧頂元素,棧頂指針上移1個(gè)存儲(chǔ)單元}//PushstaticPop<Op&S,char&e>{//刪除S的棧頂元素,用e返回其值if<S.top==S.base>return0;e=*--S.top;return1;}//PopvoidDestroyStack<Op&S>{//銷毀棧Sfree<S.base>;//釋放?？臻gS.top=S.base=NULL;//棧頂、棧底指針均為空S.stacksize=0;//當(dāng)前已分配存空間為0}//DestroyStackstaticStackEmpty<OpS>{//判斷棧是否為空,?？辗祷?,否則,返回0。if<S.top==S.base>//空棧條件 return1;else return0;}//StackEmptyintmain<intargc,double*argv[]>{voidMid_Back<chara[]>;//中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)inti=0;//str[]數(shù)組的下腳標(biāo) intj=0;//str_pass數(shù)組的下腳標(biāo) charstr[50];//接受用戶輸入字符的數(shù)組charstr_pass[50];//接受數(shù)字字符的數(shù)組printf<"請(qǐng)輸入算數(shù)表達(dá)式：\n">;scanf<"%s",&str>;//輸入表達(dá)式while<str[i]!='\0'>//對(duì)str[]數(shù)組進(jìn)行循環(huán),知道str[i]為'\0'{ if<<str[i]>='0'&&str[i]<='9'>||str[i]=='.'>//如果str[i]是數(shù)字或者點(diǎn){ str_pass[j]=str[i];//則將其賦給str_pass[]數(shù)組j++;i++; if<!<<str[i]>='0'&&str[i]<='9'>||str[i]=='.'>>//再對(duì)下一個(gè)數(shù)組中的元素進(jìn)行判斷{ str_pass[j]='#';//如果不是數(shù)字或者點(diǎn),則添加#j++;}}else{ str_pass[j]=str[i];//將運(yùn)算符傳到數(shù)組中j++;i++;}}Mid_Back<str_pass>;//將表達(dá)式傳入中轉(zhuǎn)后綴函數(shù)中return0;}/**************中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)*****************/voidMid_Back<chara[]>{//中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式函數(shù)inti=0;//數(shù)組a[]下腳標(biāo)intj=0;//數(shù)組Ba_str[]下腳標(biāo)charBa_str[50];chare;OpOp;//聲明符號(hào)棧函數(shù)InitStack<Op>;//創(chuàng)建一個(gè)符號(hào)棧voidcountfor<charBa_str[]>;//聲明求值函數(shù)for<i=0;a[i]!='=';i++>{//對(duì)數(shù)組a[]進(jìn)行循環(huán)if<<a[i]>='0'&&a[i]<='9'>||a[i]=='.'||a[i]=='#'> {//判斷a[i]是否為數(shù)字、點(diǎn)或者’#’,是則將元素傳遞到Ba_str[]數(shù)組中；否則,再次進(jìn)行判斷 Ba_str[j]=a[i]; printf<"%c",Ba_str[j]>; j++; } else{ GetTop<Op,e>;//看棧頂if<StackEmpty<Op>||e=='<'||<<e=='+'||e=='-'>&&<a[i]=='*'||a[i]=='%'||a[i]=='/'>>||a[i]=='<'> {Push<Op,a[i]>;}else{if<a[i]=='>'> {//如果現(xiàn)有元素為’>’,則運(yùn)算符出棧Pop<Op,e>;for<;e!='<';> {//直到出棧元素為’<’ Ba_str[j]=e;//將出棧的運(yùn)算符賦給Ba_str[j] printf<"%c",Ba_str[j]>;// j++; Pop<Op,e>;//運(yùn)算符出棧 } } else{//如果現(xiàn)有元素不為’>’,則運(yùn)算符出棧Pop<Op,e>;Ba_str[j]=e;//將出棧的運(yùn)算符賦給Ba_str[j]printf<"%c",Ba_str[j]>;j++;GetTop<Op,e>;//看棧頂if<StackEmpty<Op>||e=='<'||<<e=='+'||e=='-'>&&<a[i]=='*'||a[i]=='%'||a[i]=='/'>>||a[i]=='<'>//對(duì)棧頂元素與現(xiàn)有元素進(jìn)行優(yōu)先級(jí)比較,符合以上情況的,現(xiàn)有元素進(jìn)棧{Push<Op,a[i]>;}else{//否則運(yùn)算符出棧Pop<Op,e>; Push<Op,a[i]>;//將現(xiàn)有元素放到棧中 Ba_str[j]=e;//將出棧的運(yùn)算符賦給Ba_str[j] printf<"%c",Ba_str[j]>; j++;} } } }}while<!StackEmpty<Op>>//輸出棧中所有運(yùn)算符 {Pop<Op,e>; Ba_str[j]=e;//將出棧的運(yùn)算符賦給Ba_str[j] printf<"%c",Ba_str[j]>;// j++; }DestroyStack<Op>;//銷毀棧countfor<Ba_str>;//將數(shù)組傳遞給求值函數(shù)}/*************************表達(dá)式求值函數(shù)*******************************/voidcountfor<charBa_str[]>{OdOd;//聲明數(shù)字棧函數(shù)InitStack<Od>;//創(chuàng)建一個(gè)數(shù)字棧inti=0;//數(shù)組Ba_str[]下腳標(biāo)intj=0;//數(shù)組Consist[]下腳標(biāo)doublee;intk=0;doubleOd1,Od2;charConsist[20];for<i=0;Ba_str[i]!='\0';i++>{//對(duì)數(shù)組進(jìn)行循環(huán)if<<Ba_str[i]>='0'&&Ba_str[i]<='9'>||Ba_str[i]=='.'||Ba_str[i]=='#'>{//如果元素為數(shù)字、點(diǎn)或者’#’,則將元素賦給Consist[j]Consist[j]=Ba_str[i]; j++; i++; if<Ba_str[i]=='#'> {//如果元素為’#’ e=strtod<Consist,NULL>;//利用strtod函數(shù)將字符串轉(zhuǎn)換成double類型的數(shù)字Push<Od,e>;//數(shù)字進(jìn)棧 for<j=0;j<20;j++>//清空數(shù)組Consist[]以便重新使用 {Consist[j]='\0';} j=0; } else--i;}else{//否則,從數(shù)字棧中取兩個(gè)數(shù) Od1=Od2=0; Pop<Od,e>; Od2=e; Pop<Od,e>; Od1=e;switch<Ba_str[i]> {//判斷運(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>Od2;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"#defineSTACK_INIT_SIZE10//存儲(chǔ)空間初始分配量#defineSTACKINCREMENT10//存儲(chǔ)空間分配增量typedefstruct{ double*base;//在棧構(gòu)造之前和銷毀之后,base的值為NULL double*top;//棧的頂指針 intstacksize;//當(dāng)前已分配的存儲(chǔ)空間,以元素為單位}Od;voidInitStack<Od&S>{//創(chuàng)建一個(gè)棧 S.base=<double*>malloc<STACK_INIT_SIZE*sizeof<double>>;//分配類型為doubleif<!S.base>{ printf<"OVERFLOW!">;//存儲(chǔ)分配失敗}S.top=S.base;S.stacksize=STACK_INIT_SIZE;}//InitStackstaticGetTop<OdS,double&e>{//看棧頂,若棧非空,用e返回S的棧頂元素,并返回1；否則,0if<S.top>S.base>{e=*<S.top-1>;return1;}elsereturn0;}//GetTopvoidPush<Od&S,doublee>{//插入元素e為新的棧頂 if<S.top-S.base>=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;}*<S.top>++=e;}//PushstaticPop<Od&S,double&e>{//刪除S的棧頂元素,用e返回其值if<S.top==S.base>return0;e=*--S.top;return1;}//PopvoidDestroyStack<Od&S>{//銷毀棧Sfree<S.base>;//釋放?？臻gS.top=S.base=NULL;//棧頂、棧底指針均為空S.stacksize=0;//當(dāng)前已分配存空間為0}//DestroyStackstaticStackEmpty<OdS>{//判斷棧是否為空,?？辗祷?,否則,返回0。if<S.top==S.base>//空棧條件 return1;elsereturn0;}//StackEmpty/***********************************/typedefstruct{ char*base;//在棧構(gòu)造之前和銷毀之后,base的值為NULL char*top;//棧的頂指針 intstacksize;//當(dāng)前已分配的存儲(chǔ)空間,以元素為單位}Op;voidInitStack<Op&S>{//創(chuàng)建一個(gè)棧 S.base=<char*>malloc<STACK_INIT_SIZE*sizeof<char>>;//分配類型為charif<!S.base>{printf<"OVERFLOW!">;//存儲(chǔ)分配失敗}S.top=S.base;S.stacksize=STACK_INIT_SIZE;}//InitStackstaticGetTop<OpS,char&e>{//看棧頂,若棧非空,用e返回S的棧頂元素,并返回1；否則,0 if<S.top>S.base>{e=*<S.top-1>;return1;}elsereturn0;}//GetTopvoidPush<Op&S,chare>{//插入元素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;}//PushstaticPop<Op&S,char&e>{//刪除S的棧頂元素,用e返回其值if<S.top==S.base>return0;e=*--S.top;return1;}//PopvoidDestroyStack<Op&S>{//銷毀棧Sfree<S.base>;//釋放棧空間S.top=S.base=NULL;//棧頂、棧底指針均為空S.stacksize=0;//當(dāng)前已分配存空間為0}//DestroyStackstaticStackEmpty<OpS>{//判斷棧是否為空,是返回1,否則返回0。if<S.top==S.base>//空棧條件return1;elsereturn0;}//StackEmpty/*****************************************************/intmain<intargc,double*argv[]>{voidMid_Back<chara[]>; inti=0;//str[]數(shù)組的下腳標(biāo) intj=0;//str_pass數(shù)組的下腳標(biāo) charstr[50];//接受用戶輸入字符的數(shù)組charstr_pass[50];//接受數(shù)字字符的數(shù)組voidCountfor<charMin_str[]>;//進(jìn)行表達(dá)式運(yùn)算的函數(shù)printf<"請(qǐng)輸入算數(shù)表達(dá)式：\n">;scanf<"%s",&str>;//輸入表達(dá)式while<str[i]!='\0'>//對(duì)str[]數(shù)組進(jìn)行循環(huán),知道str[i]為'\0'{ if<<str[i]>='0'&&str[i]<='9'>||str[i]=='.'>//如果str[i]是數(shù)字或者點(diǎn) { str_pass[j]=str[i];//則將其賦給str_pass[]數(shù)組j++;i++; if<!<<str[i]>='0'&&str[i]<='9'>||str[i]=='.'>>//再對(duì)下一個(gè)數(shù)組中的元素進(jìn)行判斷{ str_pass[j]='#';//如果不是數(shù)字或者點(diǎn),則添加#j++;}}else { str_pass[j]=str[i];//將運(yùn)算符傳到數(shù)組中 j++;i++; } }Countfor<str_pass>;//將表達(dá)式傳入中轉(zhuǎn)后綴函數(shù)中return0;}/*********表達(dá)式計(jì)算函數(shù)***********/voidCountfor<charMin_str[]>{OpOp;OdOd;InitStack<Op>;//創(chuàng)建一個(gè)Op棧InitStack<Od>;//創(chuàng)建一個(gè)Od棧doubleJudge<charc_Operator,doubleOd1,doubleOd2>;//判斷運(yùn)算符的函數(shù)doubleeod;chareop;doubleOd1,Od2;inti=0;//Min_str[]數(shù)組的下腳標(biāo)intj=0;//Consist[]數(shù)組的下腳標(biāo)charConsist[20];//接受數(shù)字字符的數(shù)組for<i=0;Min_str[i]!='=';i++>//對(duì)Min_str[]數(shù)組進(jìn)行循環(huán){if<<Min_str[i]>='0'&&Min_str[i]<='9'>||Min_str[i]=='.'||Min_str[i]=='#'> {//判斷Min_str[i]是否為數(shù)字或者點(diǎn)、#,Consist[j]=Min_str[i];//是,則傳入Consist[]數(shù)組,直至Min_str[i]為# j++; i++; if<Min_str[i]=='#'>//如果Min_str[i]為# { 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)清空 {Consist[j]='\0';} j=0; } else--i;} else{//Min_str[i]是運(yùn)算符 GetTop<Op,eop>;//看棧if<StackEmpty<Op>||eop=='<'||<<eop=='+'||eop=='-'>&&<Min_str[i]=='*'||Min_str[i]=='%'||Min_str[i]=='/'>>||Min_str[i]=='<'> {Push<Op,Min_str[i]>;}//將棧中已有的運(yùn)算符與現(xiàn)有的運(yùn)算符進(jìn)行比較else { if<Min_str[i]=='>'>//如果現(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,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=='<'||<<eop=='+'||eop=='-'>&&<Min_str[i]=='*'||Min_str[i]=='%'||Min_str[i]=='/'>>||Min_str[i]=='<'> {Push<Op,Min_str[i]>;}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)棧 Push<Op,Min_str[i]>; } } } }}for<;!StackEmpty<Op>;//運(yùn)算符出棧,直到?？調(diào)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>;//銷毀數(shù)字棧OdDestroyStack<Op>;//銷毀字符棧Op}doubleJudge<charc_Operator,doubleOd1,doubleOd2>{doubleeod;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'/':{eod=Od1/Od2;break;}//運(yùn)算符為除號(hào),則兩數(shù)相除case'%':{eod=<int>Od1%<int>Od2;break;}//運(yùn)算符為取余號(hào),則兩數(shù)相除取余//degault:}returneod;//返回運(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”圖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”圖8兩個(gè)棧直接對(duì)表達(dá)式進(jìn)行計(jì)算算法的運(yùn)行結(jié)果圖五、遇到的問(wèn)題及解決這部分我主要遇到了如下兩個(gè)問(wèn)題,其容與解決方法如下所列：在第二個(gè)算法〔表達(dá)式直接求值中輸