计算器问题大约在大二数据结构的课程上学过，当时是使用栈来解决，此外还需要设置很多符号的优先级，以此判断是否弹栈，代码写的很长很麻烦。今天又遇到了这种题，也有了简单的解法，做一个整理。
计算器的难点在于先算乘除后算加减，如果有小括号，需要先算括号里面的内容。因此从简往难，一点点的来看问题如何解决。
无括号
无括号相对简单一些，我们只需要考虑先算乘除后算加减即可。那么思路就是：如果当前符号是加法或减法，那么将符号连带数字压入栈中，比如 +10 或 -11；如果遇到的是乘法或除法，那么就需要把栈尾的元素拿出来，做乘法或除法运算在放入栈中。最后，对栈内的元素求和即可。
我们来看程序：
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
| class Solution {
public:
int calculate(string s) {
int idx = 0;
return subcal(s, idx);
}
int subcal(string s, int& idx) {
int res = 0;
stack<int> stk;
int num = 0;
char sign = '+';
for (int i = 0; i < s.size(); i++) {
char c = s[i];
if (isdigit(c)) {
num = 10 * num + (c - '0');
}
if (!isdigit(c) && c != ' ' || i == s.size() - 1) {
if (sign == '+') {
stk.push(num);
} else if (sign == '-') {
stk.push(-num);
} else if (sign == '*') {
auto tmp = stk.top();
stk.pop();
stk.push(tmp * num);
} else if (sign == '/') {
auto tmp = stk.top();
stk.pop();
stk.push(tmp / num);
}
sign = c;
num = 0;
}
}
while (stk.size()) {
res += stk.top();
stk.pop();
}
return res;
}
};
|
程序中有很多的细节，一点点来分析：
sign 初始值为 +，这样如果开头的数字是正数，那么这个数会被放入栈中；如果开头的数字是负数，那么栈中先放入 0，在放入负数，不影响。- 符号
c 的判断不构成 if-else-if 关系，因为当 i=s.size()-1 的时候，需要处理最后一个数字。即，c 是数字且是最后一个字符的情况下，需要经过这两个分支的处理。
有括号
右括号就比较烦人，因为括号的优先级高于一切，需要找到最内部的括号，逐层往外回退得到答案。而这，也让人容易联想到传说中的递归。
那么递归需要记录关于括号的哪些东西呢？想法自然是遇到一个左括号，那么就计算括号内部的东西，遇到右括号返回。之后跳过括号里面的内容，计算下一个表达式。括号中的括号也是同理。我们来看程序：
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
| class Solution {
public:
int calculate(string s) {
int idx = 0;
return subcal(s, idx);
}
int subcal(string s, int& idx) {
int num = 0;
char sign = '+';
stack<int> stk;
for (int i = 0; i < s.size(); i++) {
char c = s[i];
if (isdigit(c))
num = 10 * num + (c - '0');
if (c == '(') {
num = subcal(s.substr(i+1), idx);
i += (idx + 2);
c = s[i];
}
if (!isdigit(c) && c != ' ' || i == s.size() - 1) {
if (sign == '+')
stk.push(num);
else if (sign == '-')
stk.push(-num);
else if (sign == '*') {
auto tmp = stk.top();
stk.pop();
stk.push(num * tmp);
}
else if (sign == '/') {
auto tmp = stk.top();
stk.pop();
stk.push(tmp / num);
}
sign = c;
num = 0;
}
if (c == ')') {
idx = i;
break;
}
}
int res = 0;
while(stk.size()) {
res += stk.top();
stk.pop();
}
return res;
}
};
|
同样来解读一下：
- 如果遇到右括号，记录索引，表示当前括号的内容计算完了，退出。
- 如果遇到左括号，那么计算左括号后面子串的内容得到数字，
i=i+(idx+2) 的意思是，跳到右括号后面第一个字符继续计算，+2 为什么是后面第一个字符呢？因为 substr(i+1) 了，这里向后移动了一位，对于 i 来说，+2 才是后面的第一位。
