表達(dá)式的運(yùn)算
總共分兩個步驟
·中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式
·后綴表達(dá)式的計算
中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式：
掃描一遍中綴表達(dá)式
操作符棧
左括號和右括號的特殊性
運(yùn)算符的優(yōu)先級
后綴表達(dá)式的計算：
掃描一遍后綴表達(dá)式
操作數(shù)棧
當(dāng)前操作符，操作數(shù)棧出棧計算，注意雙目運(yùn)算符的左右順序
表達(dá)式運(yùn)算的整個過程，利用了兩個棧
·操作符棧
·操作數(shù)棧
分別應(yīng)用于第一和第二步驟中。
在做中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的過程中需要注意左括號和右括號的入棧出棧，其他操作符相對左括號和右括號的入棧和出棧。注意左括號的棧內(nèi)優(yōu)先級與棧外優(yōu)先級的區(qū)別。
實現(xiàn)：
1 //
2 // 表達(dá)式運(yùn)算
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 閱讀(169)
評論(0) 編輯 收藏 引用