后缀表达式的计算
表达式运算过程中，需要先做中缀表达式到后缀表达式的转换。
这里现对后缀表达式求值进行解答。
对后缀表达式进行扫描，遇到操作数将操作数压栈，遇到运算符将操作数出栈，进行运算，将运算的结果压入到操作数栈中。
注意，对于双目运算符，在堆操作数栈出栈的时候要注意，后弹出的操作符为左边的操作符，不要弄反了。
之前的做法是错误的，把后缀表达式存在一个栈中，只对栈顶操作，对于 a b c + * 这种情况不成立。
实现如下：
1 #include <iostream>
2 #include <vector>
3 #include <string>
4 #include <stack>
5 #include <sstream>
6 #include <cstdlib>
7 using namespace std;
8
9 void getPost(vector<string>& post)
10 {
11 post.clear();
12 string tmp;
13 while (cin >> tmp)
14 {
15 post.push_back(tmp);
16 }
17 }
18
19 double stringToDouble(const string& s)
20 {
21 return (atof(s.c_str()));
22 }
23
24 double evalPost(const vector<string>& post)
25 {
26 stack<double> operands;
27 int a, b;
28 for (vector<string>::size_type i = 0; i != post.size(); ++i)
29 {
30 if (post[i] == "+")
31 {
32 b = operands.top();
33 operands.pop();
34 a = operands.top();
35 operands.pop();
36 operands.push(a + b);
37 }
38 else if (post[i] == "-")
39 {
40 b = operands.top();
41 operands.pop();
42 a = operands.top();
43 operands.pop();
44 operands.push(a - b);
45 }
46 else if (post[i] == "*")
47 {
48 b = operands.top();
49 operands.pop();
50 a = operands.top();
51 operands.pop();
52 operands.push(a * b);
53 }
54 else if (post[i] == "/")
55 {
56 b = operands.top();
57 operands.pop();
58 a = operands.top();
59 operands.pop();
60 operands.push(a / b);
61 }
62 else if (post[i] == "%")
63 {
64 b = operands.top();
65 operands.pop();
66 a =operands.top();
67 operands.pop();
68 operands.push(a - b);
69 }
70 else
71 {
72 // stringstream ss;
73 // ss << post[i];
74 // ss >> a;
75 operands.push(stringToDouble(post[i]));
76 }
77 }
78 return operands.top();
79 }
80
81 int main()
82 {
83 vector<string> post;
84 getPost(post);
85 cout << evalPost(post) << endl;
86 return 0;
87 }
posted on 2011-06-28 23:20
unixfy 阅读(683)
评论(0) 编辑 收藏 引用