表達式的運算
總共分兩個步驟
·中綴表達式轉換成后綴表達式
·后綴表達式的計算
中綴表達式轉換成后綴表達式：
掃描一遍中綴表達式
操作符棧
左括號和右括號的特殊性
運算符的優先級
后綴表達式的計算：
掃描一遍后綴表達式
操作數棧
當前操作符，操作數棧出棧計算，注意雙目運算符的左右順序
表達式運算的整個過程，利用了兩個棧
·操作符棧
·操作數棧
分別應用于第一和第二步驟中。
在做中綴表達式轉換成后綴表達式的過程中需要注意左括號和右括號的入棧出棧，其他操作符相對左括號和右括號的入棧和出棧。注意左括號的棧內優先級與棧外優先級的區別。
實現：
1 //
2 // 表達式運算
3 // Mark
4 // email: goonyangxiaofang AT 163.com
5 // QQ : 591247876
6 // 2011.6.29
7 // ( ( 1 + 2 ) * 3 + ( 1 + 10 ) ) / 2
8 // ???
9 //
10
11 #include <iostream>
12 #include <string>
13 #include <vector>
14 #include <stack>
15 #include <map>
16 #include <cstdlib>
17 using namespace std;
18
19 map<string, int> operatorPriors;
20
21 void getInfix(vector<string>& infix)
22 {
23 infix.clear();
24 string tmp;
25 while (cin >> tmp)
26 {
27 infix.push_back(tmp);
28 }
29 }
30
31 void init()
32 {
33 operatorPriors["+"] = 10;
34 operatorPriors["-"] = 10;
35 operatorPriors["*"] = 20;
36 operatorPriors["/"] = 20;
37 operatorPriors["%"] = 20;
38 operatorPriors["("] = 30;
39 operatorPriors[")"] = 0;
40 }
41
42 bool prior(const string& op1, const string& op2)
43 {
44 return operatorPriors[op1] > operatorPriors[op2];
45 }
46
47 bool isOperator(const string& s)
48 {
49 return operatorPriors.find(s) != operatorPriors.end();
50 }
51
52 void print(stack<string> operators)
53 {
54 while (!operators.empty())
55 {
56 cout << operators.top() << ' ';
57 operators.pop();
58 }
59 cout << endl;
60 }
61
62 const vector<string>& infixToPostfix(vector<string>& postfix, const vector<string>& infix)
63 {
64 postfix.clear();
65 stack<string> operators;
66 for (vector<string>::size_type i = 0; i != infix.size(); ++i)
67 {
68 if (isOperator(infix[i]))
69 {
70 if (operators.empty())
71 {
72 operators.push(infix[i]);
73 }
74 else if (operators.top() == "(" && infix[i] != ")" || prior(infix[i], operators.top()))
75 {
76 operators.push(infix[i]);
77 }
78 else
79 {
80 if (infix[i] == ")")
81 {
82 while (operators.top() != "(")
83 {
84 postfix.push_back(operators.top());
85 operators.pop();
86 }
87 operators.pop();
88 }
89 else
90 {
91 postfix.push_back(operators.top());
92 operators.pop();
93 while (!operators.empty() && !prior(infix[i], operators.top()) && operators.top() != "(")
94 {
95 postfix.push_back(operators.top());
96 operators.pop();
97 }
98
99 operators.push(infix[i]);
100 }
101 }
102 }
103 else
104 {
105 postfix.push_back(infix[i]);
106 }
107 }
108 while (!operators.empty())
109 {
110 postfix.push_back(operators.top());
111 operators.pop();
112 }
113 return postfix;
114 }
115
116 double stringToDouble(const string& s)
117 {
118 return (atof(s.c_str()));
119 }
120
121 double evalPost(const vector<string>& post)
122 {
123 stack<double> operands;
124 int a, b;
125 for (vector<string>::size_type i = 0; i != post.size(); ++i)
126 {
127 if (post[i] == "+")
128 {
129 b = operands.top();
130 operands.pop();
131 a = operands.top();
132 operands.pop();
133 operands.push(a + b);
134 }
135 else if (post[i] == "-")
136 {
137 b = operands.top();
138 operands.pop();
139 a = operands.top();
140 operands.pop();
141 operands.push(a - b);
142 }
143 else if (post[i] == "*")
144 {
145 b = operands.top();
146 operands.pop();
147 a = operands.top();
148 operands.pop();
149 operands.push(a * b);
150 }
151 else if (post[i] == "/")
152 {
153 b = operands.top();
154 operands.pop();
155 a = operands.top();
156 operands.pop();
157 operands.push(a / b);
158 }
159 else if (post[i] == "%")
160 {
161 b = operands.top();
162 operands.pop();
163 a =operands.top();
164 operands.pop();
165 operands.push(a - b);
166 }
167 else
168 {
169 // stringstream ss;
170 // ss << post[i];
171 // ss >> a;
172 operands.push(stringToDouble(post[i]));
173 }
174 }
175 return operands.top();
176 }
177
178 int main()
179 {
180 init();
181 vector<string> infix;
182 vector<string> postfix;
183 getInfix(infix);
184 infixToPostfix(postfix, infix);
185 for (vector<string>::size_type i = 0; i != postfix.size(); ++i)
186 {
187 cout << postfix[i] << ' ';
188 }
189 cout << endl;
190 cout << evalPost(postfix) << endl;
191 return 0;
192 }
posted on 2011-06-29 01:58
unixfy 閱讀(166)
評論(0) 編輯 收藏 引用