前言
介绍实现表达式求值的两种方法
算符优先法
维护一个操作数栈，遍历字符串，如果是乘除法，就立即将 num 与栈顶元素相乘除，结果再入栈，如果是加法，就将 num 入栈，如果是减法，就将 -num 入栈；碰到左括号就递归计算作为 num，然后跳到右括号位置；最后栈内元素相加即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| int findClosing(string s) {
int level = 0, i = 0;
for (i = 0; i < s.length(); ++i) {
if (s[i] == '(')
level++;
else if (s[i] == ')') {
level--;
if (level == 0) break;
}
else continue;
}
return i;
}
int calculate(string s) {
vector<int> stk;
char preSign = '+';
int num = 0;
for (int i = 0; i < s.length(); ++i) {
if (isdigit(s[i]))
num = num * 10 + (s[i] - '0');
if (s[i] == '(') {
int j = findClosing(s.substr(i));
num = calculate(s.substr(i+1, j-1));
i += j;
}
if (!isdigit(s[i]) && s[i] != ' ' || i == s.length()-1) {
switch (preSign) {
case '+':
stk.push_back(num);
break;
case '-':
stk.push_back(-num);
break;
case '*':
stk.back() *= num;
break;
case '/':
stk.back() /= num;
break;
}
preSign = s[i];
num = 0;
}
}
return accumulate(stk.begin(), stk.end(), 0);
}
|
逆波兰表达式
逆波兰表达式是后缀表达式，对计算机的计算有天然的优势，不用考虑优先级问题，将常规的中缀表达式转换为后缀表达式的步骤为：
- 从左到右扫描算式, 如果是数字, 计算数字的值后直接输出
- 如果是右括号,查询栈顶是否为左括号, 如果是, 把左括号出栈, 如果不是, 输出栈顶的符号, 出栈, 直到找到左括号
- 如果是 +, - 运算符, 比较当前运算符和栈顶运算符的优先级, 如果该运算符的优先级大于栈顶运算符的优先级或者栈为空或者栈顶符号为括号, 把该运算符入栈, 否则输出栈顶的符号, 出栈
- 如果是 *, /, ( 运算符，直接入栈.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| string translate(string s) {
char ch;
string ans;
stack<char> stk;
for (int i = 0; i < s.length(); ++i) {
if (isdigit(s[i])) {
while (isdigit(s[i]))
ans += s[i++];
ans += ' ';
}
if (s[i] == ' ')
continue;
if (s[i] == ')') {
ch = stk.top();
while (ch != '(') {
stk.pop();
ans += ch;
ans += ' ';
ch = stk.top();
}
stk.pop();
}
else if (s[i] == '+' || s[i] == '-') {
if (stk.empty())
stk.push(s[i]);
else {
ch = stk.top();
while (!stk.empty() && ch != '(') {
ans += ch;
ans += ' ';
stk.pop();
ch = stk.top();
}
stk.push(s[i]);
}
}
else
stk.push(s[i]);
}
while (!stk.empty()) {
ans += stk.top();
ans += ' ';
stk.pop();
}
return ans;
}
int calculate1(string s) {
s = translate(s);
stack<int> stk;
stk.push(0);
int num = 0, x, y;
for (int i = 0; i < s.length(); ++i) {
if (isdigit(s[i])) {
while (isdigit(s[i])) {
num += num * 10 + (s[i] - '0');
i++;
}
stk.push(num);
num = 0;
}
switch(s[i]) {
case '+':
x = stk.top(); stk.pop();
y = stk.top(); stk.pop();
stk.push(y+x);
break;
case '-':
x = stk.top(); stk.pop();
y = stk.top(); stk.pop();
stk.push(y-x);
break;
case '*':
x = stk.top(); stk.pop();
y = stk.top(); stk.pop();
stk.push(y*x);
break;
case '/':
x = stk.top(); stk.pop();
y = stk.top(); stk.pop();
stk.push(y/x);
break;
}
}
return stk.top();
}
|
微信
