（精選）數(shù)據(jù)結(jié)構表達式的兩種計算方法

1、一、 設計思想（一） 先將輸入的中綴表達式轉(zhuǎn)為后綴再計算的設計思想我們所熟知的計算表達式為中綴表達式，這之中包含運算符的優(yōu)先級還有括號，這對我們來說已經(jīng)習以為常了，但是在計算機看來，這是非常復雜的一種表達式。因此我們需要有一種更能使計算機理解的不用考慮優(yōu)先級也不包括括號的表達式，也就是后綴表達式。我們可以借助棧將其實現(xiàn)。首先，我們需要將中綴表達式轉(zhuǎn)換為后綴表達式，這也是這個算法的關鍵之處。我們將創(chuàng)建兩個棧，一個是字符型的，用來存放操作符；另一個是浮點型的，存放操作數(shù)。接著，開始掃描輸入的表達式，如果是操作數(shù)直接進入一個存放后綴表達式的數(shù)組，而操作符則按照優(yōu)先級push進棧（加減為1，乘除為2）

2、，若當前操作符優(yōu)先級大于棧頂操作符優(yōu)先級或棧為空，push進棧，而當其優(yōu)先級小于等于棧頂操作符優(yōu)先級，則從棧內(nèi)不斷pop出操作符并進入后綴表達式數(shù)組，直到滿足條件，當前操作符才能push進棧。左括號無條件入棧，右括號不入棧，而不斷從棧頂pop出操作符進入后綴表達式數(shù)組，直到遇到左括號后，將其pop出棧。這樣當掃描完輸入表達式并從操作符棧pop出殘余操作符后并push進棧，后綴表達式數(shù)組中存放的就是我們所需要的后綴表達式了。掃描后綴表達式數(shù)組，若是操作數(shù)，將其轉(zhuǎn)換為浮點型push進數(shù)棧；若是操作符，則連續(xù)從數(shù)棧中pop出兩個數(shù)做相應運算，將結(jié)果push進數(shù)棧。當掃描完數(shù)組后，數(shù)棧頂便為最終結(jié)果，

3、將其pop出，輸出結(jié)果。（二） 一邊掃描一邊計算的設計思想由于第一種算法需要進行兩遍掃描，因此在性能上不會十分優(yōu)秀。而此種算法只用掃描一遍，當掃描完輸入的表達式后便可以直接輸出最終結(jié)果。是第一種算法的改進版，性能上也得到提升，與第一種算法所不同的是其需要同時使用兩個棧，一個操作符棧，一個數(shù)棧。當掃描表達式時，若是操作數(shù)則將其轉(zhuǎn)換為浮點型后直接push進數(shù)棧，而若是操作符則按照優(yōu)先級規(guī)則push進操作符棧（加減為1，乘除為2），若當前操作符優(yōu)先級大于棧頂操作符優(yōu)先級或棧為空，push進棧，而當其優(yōu)先級小于等于棧頂操作符優(yōu)先級，則從棧內(nèi)不斷pop出操作符，直到滿足條件，當前操作符才能push進棧。

4、左括號無條件入棧，右括號不入棧，而不斷從棧頂pop出操作符，直到遇到左括號后，將其pop出棧。這中間pop出操作符后直接從數(shù)棧中pop出兩個數(shù)并計算，將結(jié)果push進數(shù)棧。括號的處理與第一個算法相同。掃描完成后，從操作符棧pop出殘余操作符，從數(shù)棧中pop出兩個數(shù)并計算并進行計算，將結(jié)果push進數(shù)棧。數(shù)棧頂便為最終結(jié)果，將其pop出，輸出結(jié)果。兩種算法各有各的優(yōu)缺點，第一種算法過程比較清晰，使我們能夠更加容易理解棧的使用規(guī)則，但是其性能不如第二種。第二種算法相比第一種來說性能提高了，但是理解起來就不如第一種那么清晰了。二、算法流程圖以下是先將輸入的中綴表達式轉(zhuǎn)為后綴再計算算法：圖1 中綴轉(zhuǎn)后

5、綴算法流程圖以下是一邊掃描一邊計算算法：圖2一邊掃描一邊計算算法流程圖三、源代碼以下為先將輸入的中綴表達式轉(zhuǎn)為后綴再計算算法代碼：#include stdio.h#include stdlib.h/*定義存放操作符的結(jié)構體*/struct OpStrack char op100;/*存放操作符的數(shù)組*/ int top;/*棧頂索引*/ int level100;/*存放操作符優(yōu)先級的數(shù)組*/OpStrackArray;/*定義存放語素的結(jié)構體*/struct OdStrack float od100;/*存放操作數(shù)的數(shù)組*/ int top;/*棧頂索引*/OdStrackArray;/*聲

6、明需要用到的函數(shù)*/int judge(char,char,int,int);int stackIsEmpty();void pushOp(char,int);char popOp();void pushOd(float);float popOd();void compute(char);/*主函數(shù)*/void main() char data100;/*聲明存放中綴表達式的字符串*/ char tempdata200;/*聲明存放后綴表達式的字符串*/ int i=0;/*作為遍歷字符串的索引*/ int j=0;/*作為輸出后綴表達式的索引*/ int z=0;/*作為存放后綴表達式的索引

7、*/ int k=0;/*作為將后綴表達式賦給臨時轉(zhuǎn)float的索引*/ int eq=0;/*判斷括號是否正確的條件*/ float result;/*聲明存放最終結(jié)果的float*/ scanf(%s,data);/*輸入中綴表達式*/ /*中綴轉(zhuǎn)后綴，并將結(jié)果放入tempdata*/ while(datai!=0) if(datai=0&datai=9)|datai=.)/*如果是語素則存放至temp數(shù)組*/ tempdataz=datai; z+; else switch(datai) case +: z+=judge(datai,tempdata,i,1); break; case

8、-: z+=judge(datai,tempdata,i,1);/*加減優(yōu)先級為1*/ break; case *: z+=judge(datai,tempdata,i,2);/*乘除優(yōu)先級為2*/ break; case /: /*返回出棧操作符的數(shù)量，以便將z索引向后推相應步*/ z+=judge(datai,tempdata,i,2); break; case (: pushOp(datai,-1);/*(直接入棧，但入棧后優(yōu)先級最小*/ eq+;/*有一個(eq+1*/ break; case ): while(OpStrackArray.opOpStrackArray.top-1!=

9、()/*)不入棧*/ /*不斷彈出操作符并進入后綴表達式數(shù)組，直到遇到(*/ tempdataz=popOp(); z+;/*索引+1*/*如果發(fā)現(xiàn)還沒碰到與之匹配的(時棧已空則說明表達式不合法*/ if(stackIsEmpty()=1) printf(Expression is not valid!Press any key to continue.); getch(); return; popOp();/*彈出(*/ eq-;/*如有與(配隊的)則eq-1*/ break; i+; if(eq!=0)/*如果eq!=0說明(與)不能完全配隊，輸入的表達式不合法*/ printf(Expr

10、ession is not valid!Press any key to continue.); getch(); return; /*將操作符棧內(nèi)存留的操作符放入tempdata*/ while(stackIsEmpty()=0)/*如果操作符棧不空則不斷彈出操作符并進入后綴表達式數(shù)組*/ tempdataz=popOp(); z+; /*掃描后綴表達式，計算后放入操作數(shù)棧*/ while(k=0&tempdatak=9)|tempdatak=.) tempt=tempdatak; k+; t+; if(temp0!=0)/*判斷temp數(shù)組是否為空，是則將其轉(zhuǎn)換為float并壓棧*/ f=

11、atof(temp);/*字符串轉(zhuǎn)float*/ pushOd(f);/*操作數(shù)入棧*/ if(tempdatak=+|tempdatak=-|tempdatak=*|tempdatak=/) compute(tempdatak);/*如果掃描到操作符則作相應計算*/ k+; /*輸出后綴表達式*/ printf(The postfix expression is:); for(j=0;jz;j+) printf(%c,tempdataj); printf(n); /*從操作數(shù)棧內(nèi)彈出最終結(jié)果并輸出*/ result=popOd(); printf(The result is:%.2f,res

12、ult);/*結(jié)果取兩位小數(shù)*/ printf(n); printf(Press any key to continue.); getch();/*判斷操作符優(yōu)先級并作出相應處理，返回出棧操作符數(shù)量*/int judge(char op,char tempdata,int index,int level) int cont=0; if(stackIsEmpty()=1|OpStrackArray.levelOpStrackArray.top-1=level) /*操作符不斷出棧并入后綴表達式數(shù)組直到棧為空或棧頂操作符優(yōu)先級大于等于當前操作符優(yōu)先級*/ tempdataindex=popOp()

13、; index+;/*后綴表達式數(shù)組索引+1*/ cont+;/*出棧操作符數(shù)量+1*/ pushOp(op,level);/*將當前操作符壓棧*/ return cont;/*判斷操作符棧是否為空，是則返回1，否返回0*/int stackIsEmpty() if(OpStrackArray.op0=0) return 1; return 0;/*將操作符壓入棧*/void pushOp(char op,int level) OpStrackArray.opOpStrackArray.top=op;/*操作符進入數(shù)組*/ OpStrackArray.levelOpStrackArray.to

14、p=level;/*為對應操作符附優(yōu)先級*/ OpStrackArray.top+;/*top索引+1*/*操作符出棧，返回棧頂操作符*/char popOp() char c=OpStrackArray.opOpStrackArray.top-1;/*取得棧頂操作符*/OpStrackArray.opOpStrackArray.top-1=0;/*分別將op數(shù)組與level數(shù)組還原為默認值*/ OpStrackArray.levelOpStrackArray.top-1=0; OpStrackArray.top-;/*top索引-1*/ return c;/*返回棧頂操作符*/*將操作數(shù)壓入

15、棧*/void pushOd(float f) OdStrackArray.odOdStrackArray.top=f;/*操作數(shù)進入數(shù)組*/ OdStrackArray.top+;/*top索引+1*/*操作符出棧，返回棧頂操作數(shù)*/float popOd() float f=OdStrackArray.odOdStrackArray.top-1;/*取得棧頂操作數(shù)*/ OdStrackArray.odOdStrackArray.top-1=0.0;/*將od數(shù)組還原為默認值*/ OdStrackArray.top-;/*top索引-1*/ return f;/*返回棧頂操作數(shù)*/*根據(jù)傳入

16、操作符運算，并將結(jié)果壓入操作數(shù)棧*/void compute(char op) float tempresult;/*臨時計算結(jié)果*/ float od1=popOd(); float od2=popOd();/*連續(xù)pop出兩個操作數(shù)*/ switch(op)/*根據(jù)傳入操作符計算*/ case +: tempresult=od2+od1; break; case -: tempresult=od2-od1; break; case *: tempresult=od2*od1; break; case /: tempresult=od2/od1; break; pushOd(tempresu

17、lt);/*將計算結(jié)果壓棧*/以下為一邊掃描一邊計算算法代碼：#include stdio.h#include stdlib.h/*定義存放操作符的結(jié)構體*/struct OpStrack char op100;/*存放操作符的數(shù)組*/ int top;/*棧頂索引*/ int level100;/*存放操作符優(yōu)先級的數(shù)組*/OpStrackArray;/*定義存放語素的結(jié)構體*/struct OdStrack float od100;/*存放操作數(shù)的數(shù)組*/ int top;/*棧頂索引*/OdStrackArray;/*聲明需要用到的函數(shù)*/void pushOp(char,int);ch

18、ar popOp();void pushOd(float);float popOd();int stackIsEmpty();void judge(char,int);void compute(char);/*主函數(shù)*/void main() char data100;/*聲明存放中綴表達式的字符串*/ int i=0;/*作為遍歷字符串的索引*/ int eq=0;/*判斷括號是否正確的條件*/ float result;/*聲明存放最終結(jié)果的float*/ scanf(%s,data);/*輸入中綴表達式*/ /*掃描輸入的表達式并作出相應處理*/ while(datai!=0) char

19、 temp20=0;/*聲明臨時的存放操作數(shù)的數(shù)組并附初值*/ int j=0;/*作為temp數(shù)組的索引*/ float f;/*存放轉(zhuǎn)換為float的數(shù)*/ while(datai=0&datai=9)|datai=.)/*如果是語素則存放至temp數(shù)組*/ tempj=datai; j+; i+; if(temp0!=0)/*判斷temp數(shù)組是否為空，是則將其轉(zhuǎn)換為float并壓棧*/ f=atof(temp);/*字符串轉(zhuǎn)float*/ pushOd(f);/*操作數(shù)入棧*/ switch(datai) case +: judge(datai,1); break; case -: ju

20、dge(datai,1);/*加減優(yōu)先級為1*/ break; case *: judge(datai,2); break; case /: judge(datai,2);/*乘除優(yōu)先級為2*/ break; case (: pushOp(datai,-1);/*(直接入棧，但入棧后優(yōu)先級最小*/ eq+;/*有一個(eq+1*/ break; case ): while(OpStrackArray.opOpStrackArray.top-1!=()/*)不入棧*/ compute(popOp();/*不斷彈出操作符并計算，直到遇到(*/*如果發(fā)現(xiàn)還沒碰到與之匹配的(時棧已空則說明表達式不合法

21、*/ if(stackIsEmpty()=1)/ printf(Expression is not valid!Press any key to continue.); getch(); return; popOp();/*彈出(*/ eq-;/*如有與(配隊的)則eq-1*/ break; i+; /*掃描操作符棧內(nèi)殘余操作符并做相應計算*/ while(stackIsEmpty()=0) compute(popOp();/*如果操作符棧不空則彈出操作符并計算*/ /*從操作數(shù)棧內(nèi)彈出最終結(jié)果并輸出*/ if(eq=0)/*如果eq=0說明(與)可以完全配隊，輸入的表達式合法*/ resul

22、t=popOd(); printf(The result is:%.2f,result);/*結(jié)果取兩位小數(shù)*/ else/*如果eq!=0說明(與)不能完全配隊，輸入的表達式不合法*/ printf(Expression is not valid!Press any key to continue.); printf(n); printf(Press any key to continue.); getch();/*將操作符壓入棧*/void pushOp(char op,int level) OpStrackArray.opOpStrackArray.top=op;/*操作符進入數(shù)組*/

23、OpStrackArray.levelOpStrackArray.top=level;/*為對應操作符附優(yōu)先級*/ OpStrackArray.top+;/*top索引+1*/*操作符出棧，返回棧頂操作符*/char popOp() char c=OpStrackArray.opOpStrackArray.top-1;/*取得棧頂操作符*/ OpStrackArray.opOpStrackArray.top-1=0; OpStrackArray.levelOpStrackArray.top-1=0;/*分別將op數(shù)組與level數(shù)組還原為默認值*/ OpStrackArray.top-;/*t

24、op索引-1*/ return c;/*返回棧頂操作符*/*將操作數(shù)壓入棧*/void pushOd(float f) OdStrackArray.odOdStrackArray.top=f;/*操作數(shù)進入數(shù)組*/ OdStrackArray.top+;/*top索引+1*/*操作符出棧，返回棧頂操作數(shù)*/float popOd() float f=OdStrackArray.odOdStrackArray.top-1;/*取得棧頂操作數(shù)*/ OdStrackArray.odOdStrackArray.top-1=0.0;/*將od數(shù)組還原為默認值*/ OdStrackArray.top-;/

25、*top索引-1*/ return f;/*返回棧頂操作數(shù)*/*判斷操作符棧是否為空，是則返回1，否返回0*/int stackIsEmpty() if(OpStrackArray.op0=0) return 1; return 0;/*判斷操作符優(yōu)先級作出相應處理*/void judge(char op,int level) if(stackIsEmpty()=1|OpStrackArray.levelOpStrackArray.top-1=level) /*操作符不斷出棧并計算直到棧為空或棧頂操作符優(yōu)先級大于等于當前操作符優(yōu)先級*/ compute(popOp(); pushOp(op,l

26、evel);/*將當前操作符壓棧*/ /*根據(jù)傳入操作符運算，并將結(jié)果壓入操作數(shù)棧*/void compute(char op) float tempresult;/*臨時計算結(jié)果*/ float od1=popOd(); float od2=popOd();/*連續(xù)pop出兩個操作數(shù)*/ switch(op)/*根據(jù)傳入操作符計算*/ case +: tempresult=od2+od1; break; case -: tempresult=od2-od1; break; case *: tempresult=od2*od1; break; case /: tempresult=od2/od

27、1; break; pushOd(tempresult);/*將計算結(jié)果壓棧*/四、運行結(jié)果圖3中綴轉(zhuǎn)后綴算法運算結(jié)果圖4 一邊掃描一邊計算算法運算結(jié)果五、遇到的問題及解決這部分我主要遇到了如下幾個問題，其內(nèi)容與解決方法如下所列：中綴轉(zhuǎn)后綴算法：l 問題1：掃描完成后輸出的后綴表達式會帶有(，從而導致計算不正確。解決方法：在遇到)后，程序會調(diào)用pop方法不斷從操作符棧內(nèi)彈出操作符存入后綴表達式數(shù)組，直到遇到(。就是在這里，在遇到(后應該直接彈出(而不應該將其存入后綴表達式數(shù)組，改正后后綴表達式中自然就不再存在(。l 問題2：雖然解決了第一個問題，但是有時后綴表達式仍然輸出不正確，不是掉個操作符就是少個數(shù)字。解決方法：經(jīng)過深入研究，我最終發(fā)現(xiàn)凡是當遇到)需要連續(xù)從操作符棧pop出操作符時就會出現(xiàn)這個問題。原來輸入表達式字符串和存儲后綴表達式字符串的索引相同，因為我想數(shù)字與數(shù)字之間有操作符自然分割，但是在這種情況下，輸入表達式字符串索引的確是向后推1，而存儲后綴表達式字符串的索引就不止向后推1了，需要根據(jù)pop出的操作符個數(shù)來確