中綴表達式轉換為字尾表達式求值算法

轉載自:http://www.cnblogs.com/wanghetao/archive/2012/04/23/2466580.html

逆波蘭表達式

表達式一般由操作數(Operand)、運算符(Operator)組成，例如算術表達式中，通常把運算符放在兩個操作數的中間，

這稱為中綴表達式(Infix Expression)，如A+B。

波蘭數學家Jan Lukasiewicz提出了另一種數學表示法，它有兩種表示形式：

把運算符寫在操作數之前，稱為波蘭表達式(Polish Expression)或字首表達式(Prefix Expression)，如+AB；

把運算符寫在操作數之後，稱為逆波蘭表達式(Reverse Polish Expression)或字尾表達式(Suffix Expression)，如AB+；

其中，逆波蘭表達式在編譯技術中有着普遍的應用。

算法：

一、 将中綴表達式轉換成字尾表達式算法：

1、從左至右掃描一中綴表達式。

2、若讀取的是操作數，則判斷該操作數的類型，并将該操作數存入操作數堆棧

3、若讀取的是運算符

  (1) 該運算符為左括号"("，則直接存入運算符堆棧。

  (2) 該運算符為右括号")"，則輸出運算符堆棧中的運算符到操作數堆棧，直到遇到左括号為止。

  (3) 該運算符為非括号運算符：

      (a) 若運算符堆棧棧頂的運算符為括号，則直接存入運算符堆棧。

      (b) 若比運算符堆棧棧頂的運算符優先級高或相等，則直接存入運算符堆棧。

      (c) 若比運算符堆棧棧頂的運算符優先級低，則輸出棧頂運算符到操作數堆棧，并将目前運算符壓入運算符堆棧。

4、當表達式讀取完成後運算符堆棧中尚有運算符時，則依序取出運算符到操作數堆棧，直到運算符堆棧為空。

二、逆波蘭表達式求值算法：

1、循環掃描文法單元的項目。

2、如果掃描的項目是操作數，則将其壓入操作數堆棧，并掃描下一個項目。

3、如果掃描的項目是一個二進制運算符，則對棧的頂上兩個操作數執行該運算。

4、如果掃描的項目是一個一進制運算符，則對棧的最頂上操作數執行該運算。

5、将運算結果重新壓入堆棧。

6、重複步驟2-5，堆棧中即為結果值。

c++代碼示例

1. * 
2. *    這裡主要是逆波蘭式的實作，使用兩個stack 這裡用字元串來模拟一個stack，第一步，将中綴表達式轉變為字尾表達式 
3. *    第二步，然後再使用一個stack，計算字尾表達式的結果，這一步很容易出錯，考慮到浮點數的問題。 
4. */  
5. #include <iostream>  
6. #include <string>  
7. #include <stack>  
8. #include <iomanip>  
9. using namespace std;  
10. int cmp(char ch)     // 運算符優先級   
11. {  
12.     switch(ch)  
13.     {  
14.         case '+':  
15.         case '-': return 1;  
16.         case '*':  
17.         case '/': return 2;  
18.         default : return 0;  
19.     }  
20. }  
21. void change(string &s1, string &s2)       // 中綴表達式轉變字尾表達式   
23.     stack <char > s;  
24.     s.push('#');  
25.     int i = 0;  
26.     while(i < s1.length()-1)  
28.         if(s1[i] == '(')  
29.         {  
30.             s.push(s1[i++]);  
31.         }  
32.         else if(s1[i] == ')')  
34.             while(s.top() != '(')  
35.             {  
36.                 s2 += s.top();  
37.                 s2 += ' ';  
38.                 s.pop();  
39.             }  
40.             s.pop();  
41.             i++;  
43.         else if(s1[i] == '+'||s1[i] == '-'||s1[i] == '*'||s1[i] == '/')  
45.             while(cmp(s.top()) >= cmp(s1[i]))  
51.             s.push(s1[i]);  
54.         else  
56.             while('0' <= s1[i]&&s1[i] <= '9'||s1[i] == '.')  
58.                 s2 += s1[i++];  
60.             s2 += ' ';  
63.     while(s.top() != '#')  
65.         s2 += s.top();  
66.         s2 += ' ';  
67.         s.pop();  
70. double value(string s2)         // 計算字尾表達式，得到其結果。   
72.     stack < double> s;  
73.     double x,y;  
75.     while(i < s2.length())  
77.         if(s2[i] == ' ')  
80.             continue;  
82.         switch(s2[i])  
84.             case '+': x = s.top(); s.pop(); x += s.top(); s.pop(); i++; break;  
85.             case '-': x = s.top(); s.pop(); x =s.top()-x; s.pop(); i++; break;  
86.             case '*': x = s.top(); s.pop(); x *= s.top(); s.pop(); i++; break;  
87.             case '/': x = s.top(); s.pop(); x = s.top()/x; s.pop(); i++; break;  
88.             default :  
90.                 x = 0;  
91.                 while('0' <= s2[i]&&s2[i] <= '9')  
92.                 {  
93.                     x = x*10+s2[i] - '0';  
94.                     i++;  
95.                 }  
96.                 if(s2[i] == '.')  
98.                     double k = 10.0;  
99.                     y = 0;  
101.                     while('0' <= s2[i]&&s2[i] <= '9')  
102.                     {  
103.                         y += ((s2[i]-'0')/k);  
104.                         i++;  
105.                         k *= 10;  
106.                     }  
107.                     x += y;  
111.         s.push(x);  
113.     return s.top();  
115. int main(int argc, char const *argv[])  
117.     int n;  
118.     string s1,s2;  
119.     cin>>n;  
120.     while(n--)  
122.         cin>>s1;  
123.         s2 = "";  
124.         change(s1,s2);  
125.         cout<<fixed<<setprecision(2)<<value(s2)<<endl;  
127.     return 0;  
128. }