前缀表达式的计算

前面我们曾对后缀表达式做过讨论。后缀表达式的计算过程是首先设定一个操作数栈，顺序扫描整个后缀表达式，如果遇到操作数，则将操作数压栈；如果遇到操作符，则从操作数栈中弹出相应的操作数进行运算，并将运算结果进行压栈。当将整个后缀表达式扫描完毕时，操作数栈中应该只有一个元素，该元素的值即为后缀表达式的计算结果。

对于一个后缀表达式：

1 2 3 + -

其对应的前缀表达式为：

-1 + 2 3

前缀表达式的计算方法与后缀表达式的计算方法类似。对前缀表达式从后向前扫描，设定一个操作数栈，如果是操作数，则将其直接入栈，如果是操作符，则从栈中弹出操作符对应的操作数进行运算，并将计算结果压栈。直至从右到左扫描完毕整个前缀表达式，这时操作数栈中应该只有一个元素，该元素的值则为前缀表达式的计算结果。

具体前缀表达式的计算程序如下：

 1 // 计算前缀表达式
 2 #include <iostream>
 3 #include <sstream>
 4 #include <vector>
 5 #include <stack>
 6 #include <string>
 7 using namespace std;
 8 
 9 void GetPrefix(vector<string>& prefix)
10 {
11     prefix.clear();
12     string line, tmp;
13     getline(cin, line);
14     istringstream sin(line);
15     while (sin >> tmp)
16     {
17         prefix.push_back(tmp);
18     }
19 }
20 
21 bool IsOperator(const string& op)
22 {
23     return op == "+" || op == "-" || op == "*" || op == "/";
24 }
25 
26 double CalPrefix(const vector<string>& prefix)
27 {
28     double ret = 0.0;
29     stack<double> opeStk;
30     for (int i = prefix.size() - 1; i >= 0; --i)
31     {
32         if (!IsOperator(prefix[i]))
33         {
34             opeStk.push((double)atof(prefix[i].c_str()));
35         }
36         else
37         {
38             double a = opeStk.top();
39             opeStk.pop();
40             double b = opeStk.top();
41             opeStk.pop();
42             double c = 0.0;
43 
44             switch (prefix[i][0])
45             {
46             case '+':
47                 c = a + b;
48                 opeStk.push(c);
49                 break;
50 
51             case '-':
52                 c = a - b;
53                 opeStk.push(c);
54                 break;
55 
56             case '*':
57                 c = a * b;
58                 opeStk.push(c);
59                 break;
60 
61             case '/':
62                 c = a / b;
63                 opeStk.push(c);
64                 break;
65 
66             default:
67                 break;
68             }
69         }
70     }
71 
72     if (opeStk.size() == 1)
73     {
74         return opeStk.top();
75     }
76     else
77     {
78         return -1000000000.0;
79     }
80 }
81 
82 int main()
83 {
84     vector<string> prefix;
85     while (true)
86     {
87         GetPrefix(prefix);
88         cout << CalPrefix(prefix) << endl << endl;
89     }
90     return 0;
91 }