數據結構（C語言版）嚴蔚敏：第三章：棧與隊列---棧的應用---p52表達式求值的算法詳細分析

P53 頁   表達式求值----請先查看相應書籍，至少先了解下p53頁的算符間優先關系表。

       算法3.4 ： 描述“算符優先算法”的求值過程

表達式原文

OperandType EvaluateExpression(){

       //算術表達式求值的算符優先算法。設OPTN和OPND分別為運算符棧和運算數棧

       //OP為運算符集合

       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 ‘<’ :    //棧頂元素優先權低

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

              break;

       case ‘=’ :             //脫括號并接收下一字符

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

              Break;

       Case ‘>’ :    //退棧并將運算結果入棧

              Pop(OPTR,theta);

              Pop(OPND,b);

              Pop(OPND,a);

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

              Break;

}//switch

}//while

Return Gettop(OPND);

}//EvaluateExpression

語句分析

OperandType EvaluateExpression(){

       //算術表達式求值的算符優先算法。設OPTN和OPND分別為運算符棧和運算數棧

       //OP為運算符集合

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

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

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

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

       //接下來的代碼將處理這個字符

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

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

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

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

c = getchar();}

//然后再提示用戶輸入下一個字符

              else

//否則的話，c就是OP集合中，說明c是個運算符

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

                                   //precede 應該是一個優先級比較的函數，將GetTop(OPTR)從OPTR的棧頂元素獲取到的去處符與c進行比較優先級。

       case ‘<’ :    //棧頂元素優先權低

              Push(OPTR,c);

c = getchar();

              break;

              //如果是棧頂元素的優先級低，則將輸入的c入棧到OPTR棧，并再接收下一個字符

       case ‘=’ :             //脫括號并接收下一字符

              Pop(OPTR,x);

c = getchar();

              Break;

              //如果兩個運算符優先級相等的時候，也就是要么是左右括號匹配了，要么是#匹配了，但是這里不可能是#號，因為不是#是進入這個循環的條件。

       Case ‘>’ :    //退棧并將運算結果入棧

              Pop(OPTR,theta);

              Pop(OPND,b);

              Pop(OPND,a);

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

              Break;

              //如果是棧內的優先級大于獲取的運算符，則先處理棧內的運算符。也就是先將棧頂的元素出棧后先進行運算，然后將結果入到棧內去。

}//switch

}//while

Return Gettop(OPND);

}//EvaluateExpression

分步驟分析：

4+2*3-10/5

第一步：判斷4是否是運算符，不是運算符，則4入OPND棧，并獲取下一個字符

第二步：+號與OPTR棧內的top元素比較優先級，top元素是一個#號，+號的優先級大于#號（任何運算符的運算優先級都大于#號，只有#自己與自己相等），+號入OPTR棧，并獲取下一個字符

第三步：判斷2是否是運算符，不是運算符，2入OPND棧，并獲取下一個字符，

第四步：：獲取到的一個字符為“*“乘號。與OPTR棧頂的元素+號進行比較優先級，乘號優先，所以乘號直接入OPTR棧，然后獲取下一個元素。

第五步：獲取到的下一個元素是3，是一個操作數，不是運算符，所以直接入棧。再獲取下一個元素。

第六步：獲取到的元素為-號，-號與OPTR棧頂元素進行比較，是個乘號，所以乘號優先。

                     從OPTR棧中，乘號出棧

                     從OPND中，出棧兩個OPND的數，一個是棧頂元素3，另外一個是次棧頂元素2.

                     先進行計算，3*2=6

                     將6入到OPND棧

                     獲取下一個元素

第七步：獲取到的下一個元素為-號，-號與棧頂元素進行比較，是個+號，棧里的元素是1，輸出的符號為2，+與-號，誰在棧內誰優先。所以得先把棧內的算完，明細如下：

                     從OPTR中出棧+號

                     從OPND中出棧兩個數，1個為上一步算出來的6，另外一個為4

                     進行計算，6+4=10

                     將10這個元素入棧到OPND棧中去

                     獲取下一個元素

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

第九步：獲取到的下一個元素為為/，與OPTR棧頂元素進行對比。/號優先，所以直接入棧到OPTR棧中去。獲取下一個元素。

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

第十一步：此時表示式已經完了，所以下一個輸入的字符為“#“號。而#號遇到任何其它運算符都是低優先級的，所以此時的OPTR的棧頂元素為/，/的優先級大于#號的優先級，所以操作步驟如下：

                     從OPTR中出棧一個運算符/

                     從OPND中出棧兩個數，一個是10，一個為5

                     10/5=2

                     將運算的結果2入棧到OPND中去。

                     獲取下一個字符

第十二步：又是#號，再操作一遍

                     10-2=8

                     8入棧

第十三步：又是#號，再拉取棧頂元素，而此是的棧頂元素已經是#號了，所以此是循環結束

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