數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏：第三章：棧與隊(duì)列---棧的應(yīng)用---p52表達(dá)式求值的算法詳細(xì)分析

P53 頁   表達(dá)式求值----請先查看相應(yīng)書籍，至少先了解下p53頁的算符間優(yōu)先關(guān)系表。

       算法3.4 ： 描述“算符優(yōu)先算法”的求值過程

表達(dá)式原文

OperandType EvaluateExpression(){

       //算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTN和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧

       //OP為運(yùn)算符集合

       InitStack(OPTR); Push(OPTR,’#’);

       initStack(OPND); c = getchar();

       while (c != ‘#’ || GetTop(OPTR) != ‘#’){

              if(! In(c,OP)){Push(OPND,c); c = getchar();}

              else

                     switch (Precede(GetTop(OPTR),c)){

       case ‘<’ :    //棧頂元素優(yōu)先權(quán)低

              Push(OPTR,c); c = getchar();

              break;

       case ‘=’ :             //脫括號(hào)并接收下一字符

              Pop(OPTR,x); c = getchar();

              Break;

       Case ‘>’ :    //退棧并將運(yùn)算結(jié)果入棧

              Pop(OPTR,theta);

              Pop(OPND,b);

              Pop(OPND,a);

              Push(OPND,Operate(a,theta,b);

              Break;

}//switch

}//while

Return Gettop(OPND);

}//EvaluateExpression

語句分析

OperandType EvaluateExpression(){

       //算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTN和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧

       //OP為運(yùn)算符集合

       InitStack(OPTR);              //初始化OPTR棧

Push(OPTR,’#’);               //將“#”放入到OPTR棧的棧底

       initStack(OPND);             //初始化OPND棧

c = getchar();                   //獲取一個(gè)從鍵盤輸入的字符

       //接下來的代碼將處理這個(gè)字符

       while (c != ‘#’ || GetTop(OPTR) != ‘#’){

              //只要c（從鍵盤獲取的字符）不等于“#“ 或者從OPTR獲取的棧頂元素不是”#“時(shí)，就一直循環(huán)。|| 邏輯運(yùn)算符，只要有一個(gè)為真就為真，所以只要有一個(gè)遇到了#就會(huì)退出循環(huán)。

              if(! In(c,OP)){Push(OPND,c);

                     //如果 c這個(gè)字符在OP這個(gè)集合中不存在。就是判斷c是不是輸入的運(yùn)算符。如果不是去處符，則將c的字符入棧到OPND棧中去。

c = getchar();}

//然后再提示用戶輸入下一個(gè)字符

              else

//否則的話，c就是OP集合中，說明c是個(gè)運(yùn)算符

                     switch (Precede(GetTop(OPTR),c)){

                                   //precede 應(yīng)該是一個(gè)優(yōu)先級(jí)比較的函數(shù)，將GetTop(OPTR)從OPTR的棧頂元素獲取到的去處符與c進(jìn)行比較優(yōu)先級(jí)。

       case ‘<’ :    //棧頂元素優(yōu)先權(quán)低

              Push(OPTR,c);

c = getchar();

              break;

              //如果是棧頂元素的優(yōu)先級(jí)低，則將輸入的c入棧到OPTR棧，并再接收下一個(gè)字符

       case ‘=’ :             //脫括號(hào)并接收下一字符

              Pop(OPTR,x);

c = getchar();

              Break;

              //如果兩個(gè)運(yùn)算符優(yōu)先級(jí)相等的時(shí)候，也就是要么是左右括號(hào)匹配了，要么是#匹配了，但是這里不可能是#號(hào)，因?yàn)椴皇?是進(jìn)入這個(gè)循環(huán)的條件。

       Case ‘>’ :    //退棧并將運(yùn)算結(jié)果入棧

              Pop(OPTR,theta);

              Pop(OPND,b);

              Pop(OPND,a);

              Push(OPND,Operate(a,theta,b);

              Break;

              //如果是棧內(nèi)的優(yōu)先級(jí)大于獲取的運(yùn)算符，則先處理?xiàng)?nèi)的運(yùn)算符。也就是先將棧頂?shù)脑爻鰲：笙冗M(jìn)行運(yùn)算，然后將結(jié)果入到棧內(nèi)去。

}//switch

}//while

Return Gettop(OPND);

}//EvaluateExpression

分步驟分析：

4+2*3-10/5

第一步：判斷4是否是運(yùn)算符，不是運(yùn)算符，則4入OPND棧，并獲取下一個(gè)字符

第二步：+號(hào)與OPTR棧內(nèi)的top元素比較優(yōu)先級(jí)，top元素是一個(gè)#號(hào)，+號(hào)的優(yōu)先級(jí)大于#號(hào)（任何運(yùn)算符的運(yùn)算優(yōu)先級(jí)都大于#號(hào)，只有#自己與自己相等），+號(hào)入OPTR棧，并獲取下一個(gè)字符

第三步：判斷2是否是運(yùn)算符，不是運(yùn)算符，2入OPND棧，并獲取下一個(gè)字符，

第四步：：獲取到的一個(gè)字符為“*“乘號(hào)。與OPTR棧頂?shù)脑?號(hào)進(jìn)行比較優(yōu)先級(jí)，乘號(hào)優(yōu)先，所以乘號(hào)直接入OPTR棧，然后獲取下一個(gè)元素。

第五步：獲取到的下一個(gè)元素是3，是一個(gè)操作數(shù)，不是運(yùn)算符，所以直接入棧。再獲取下一個(gè)元素。

第六步：獲取到的元素為-號(hào)，-號(hào)與OPTR棧頂元素進(jìn)行比較，是個(gè)乘號(hào)，所以乘號(hào)優(yōu)先。

                     從OPTR棧中，乘號(hào)出棧

                     從OPND中，出棧兩個(gè)OPND的數(shù)，一個(gè)是棧頂元素3，另外一個(gè)是次棧頂元素2.

                     先進(jìn)行計(jì)算，3*2=6

                     將6入到OPND棧

                     獲取下一個(gè)元素

第七步：獲取到的下一個(gè)元素為-號(hào)，-號(hào)與棧頂元素進(jìn)行比較，是個(gè)+號(hào)，棧里的元素是1，輸出的符號(hào)為2，+與-號(hào)，誰在棧內(nèi)誰優(yōu)先。所以得先把棧內(nèi)的算完，明細(xì)如下：

                     從OPTR中出棧+號(hào)

                     從OPND中出棧兩個(gè)數(shù)，1個(gè)為上一步算出來的6，另外一個(gè)為4

                     進(jìn)行計(jì)算，6+4=10

                     將10這個(gè)元素入棧到OPND棧中去

                     獲取下一個(gè)元素

第八步：獲取的元素為10，是一個(gè)操作數(shù)，數(shù)直接入棧到OPND棧中去，獲取下一個(gè)元素

第九步：獲取到的下一個(gè)元素為為/，與OPTR棧頂元素進(jìn)行對(duì)比。/號(hào)優(yōu)先，所以直接入棧到OPTR棧中去。獲取下一個(gè)元素。

第十步：下一個(gè)元素為5，5是一個(gè)操作數(shù)，直接入棧到OPND棧中去，獲取下一個(gè)元素。

第十一步：此時(shí)表示式已經(jīng)完了，所以下一個(gè)輸入的字符為“#“號(hào)。而#號(hào)遇到任何其它運(yùn)算符都是低優(yōu)先級(jí)的，所以此時(shí)的OPTR的棧頂元素為/，/的優(yōu)先級(jí)大于#號(hào)的優(yōu)先級(jí)，所以操作步驟如下：

                     從OPTR中出棧一個(gè)運(yùn)算符/

                     從OPND中出棧兩個(gè)數(shù)，一個(gè)是10，一個(gè)為5

                     10/5=2

                     將運(yùn)算的結(jié)果2入棧到OPND中去。

                     獲取下一個(gè)字符

第十二步：又是#號(hào)，再操作一遍

                     10-2=8

                     8入棧

第十三步：又是#號(hào)，再拉取棧頂元素，而此是的棧頂元素已經(jīng)是#號(hào)了，所以此是循環(huán)結(jié)束

第十四步：return OPND的棧頂元素為8-----完美結(jié)束。