后綴表達式的計算
表達式運算過程中，需要先做中綴表達式到后綴表達式的轉換。
這里現對后綴表達式求值進行解答。
對后綴表達式進行掃描，遇到操作數將操作數壓棧，遇到運算符將操作數出棧，進行運算，將運算的結果壓入到操作數棧中。
注意，對于雙目運算符，在堆操作數棧出棧的時候要注意，后彈出的操作符為左邊的操作符，不要弄反了。
之前的做法是錯誤的，把后綴表達式存在一個棧中，只對棧頂操作，對于 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 閱讀(687)
評論(0) 編輯 收藏 引用