表达式的运算
总共分两个步骤
·中缀表达式转换成后缀表达式
·后缀表达式的计算
中缀表达式转换成后缀表达式：
扫描一遍中缀表达式
操作符栈
左括号和右括号的特殊性
运算符的优先级
后缀表达式的计算：
扫描一遍后缀表达式
操作数栈
当前操作符，操作数栈出栈计算，注意双目运算符的左右顺序
表达式运算的整个过程，利用了两个栈
·操作符栈
·操作数栈
分别应用于第一和第二步骤中。
在做中缀表达式转换成后缀表达式的过程中需要注意左括号和右括号的入栈出栈，其他操作符相对左括号和右括号的入栈和出栈。注意左括号的栈内优先级与栈外优先级的区别。
实现：
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 阅读(137)
评论(0) 编辑 收藏 引用