閱讀888 返回首頁    go 阿裏雲 go 技術社區[雲棲]

經典白話算法之中綴表達式和後綴表達式

一、後綴表達式求值

後綴表達式也叫逆波蘭表達式，其求值過程可以用到棧來輔助存儲。

假定待求值的後綴表達式為：6  5  2  3  + 8 * + 3  +  *，則其求值過程如下：


（1）遍曆表達式，遇到的數字首先放入棧中，依次讀入6 5 2 3 此時棧如下所示：


（2）接著讀到“+”，則從棧中彈出3和2，執行3+2，計算結果等於5，並將5壓入到棧中。


（3）然後讀到8（數字入棧），將其直接放入棧中。


（4）讀到“*”，彈出8和5，執行8*5，並將結果40壓入棧中。

而後過程類似，讀到“+”，將40和5彈出，將40+5的結果45壓入棧...以此類推。最後求的值288。


代碼：

  1. #include<iostream>  
  2. #include<stack>  
  3. #include<stdio.h>  
  4. #include<string.h>  
  5. using namespace std;  
  6.   
  7. int main(){  
  8.     string PostArray;  
  9.     int len,i,a,b;  
  10.     while(cin>>PostArray){  
  11.         stack<int> Stack;  
  12.         len = PostArray.length();  
  13.         for(i = 0;i < len;i++){  
  14.             //跳過空格  
  15.             if(PostArray[i] == ' '){  
  16.                 continue;  
  17.             }  
  18.             //如果是數字則入棧  
  19.             if(PostArray[i] >= '0' && PostArray[i] <= '9'){  
  20.                 Stack.push(PostArray[i] - '0');  
  21.             }  
  22.             //如果是字符則從棧讀出兩個數進行運算  
  23.             else{  
  24.                 //算數a出棧  
  25.                 a = Stack.top();  
  26.                 Stack.pop();  
  27.                 //算法b出棧  
  28.                 b = Stack.top();  
  29.                 Stack.pop();  
  30.                 //進行運算（+ - * /）  
  31.                 if(PostArray[i] == '+'){  
  32.                     Stack.push(a + b);  
  33.                 }  
  34.                 else if(PostArray[i] == '-'){  
  35.                     Stack.push(a - b);  
  36.                 }  
  37.                 else if(PostArray[i] == '*'){  
  38.                     Stack.push(a * b);  
  39.                 }  
  40.                 else if(PostArray[i] == '/'){  
  41.                     Stack.push(a / b);  
  42.                 }  
  43.             }  
  44.         }//for  
  45.         printf("%d\n",Stack.top());  
  46.     }//while  
  47.     return 0;  
  48. }  

最後更新：2017-04-03 12:56:30

  上一篇：go CareerCup之1.1字符串中字符判重
  下一篇：go C# 網絡編程之通過豆瓣API獲取書籍信息