栈：表达式计算
睡不醒的鲤鱼 2021-07-28 每日一题 LeetCode
# 0150. 逆波兰表达式求值 (opens new window)
题目
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
解析
遍历逆波兰表达式，使用一个栈来辅助，当遇到一个运算符时，从栈中弹出左右两个操作数，运算之后再入栈，这样遍历结束时，栈中的唯一数字就是运算结果。
代码
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
int num1, num2;
for (int i = 0; i < tokens.size(); i ++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
num2 = stk.top(); stk.pop();
num1 = stk.top(); stk.pop();
}
if (tokens[i] == "+") {
stk.push(num1 + num2);
} else if (tokens[i] == "-") {
stk.push(num1 - num2);
} else if (tokens[i] == "*") {
stk.push(num1 * num2);
} else if (tokens[i] == "/") {
stk.push(num1 / num2);
} else {
stk.push(stoi(tokens[i]));
}
}
return stk.top();
}
};
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 0224. 基本计算器 (opens new window)
题目
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
解析
计算器的实现可使用一个通用模板（参考 【宫水三叶】使用「双栈」解决「究极表达式计算」问题 (opens new window)），具体算法如下：
对于「任何表达式」而言，我们都使用两个栈 nums 和 ops：
- nums ： 存放所有的数字；
- ops ：存放所有的数字以外的操作。
然后从前往后做，对遍历到的字符做分情况讨论：
- 空格：跳过；
(：直接加入 ops 中，等待与之匹配的)；)：使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums；- 数字：从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums；
+ - * / ^ %：需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉（只有「栈内运算符」比「当前运算符」优先级高 / 同等，才进行运算），使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums。
注意
- 由于第一个数可能是负数，为了减少边界判断。一个小技巧是先往 nums 添加一个 0；
- 为防止
()内出现的首个字符为运算符，将所有的空格去掉，并将(-替换为(0-，(+替换为(0+； - 从理论上分析，nums 最好存放的是 long，而不是 int。因为可能存在中间结果溢出，最终答案不溢出的情况。
代码
class Solution {
unordered_map<char, int> level = {
{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'%', 2}, {'^', 3}
};
public:
int calculate(string s) {
// 存放所有数字，为了防止第一个数为负数，先添加一个 0
stack<long> nums;
nums.push(0);
// 存放所有非数字的操作符
stack<char> ops;
int n = s.length();
for (int i = 0; i < n; i++) {
if (s[i] == ' ') {
continue;
} else if (s[i] == '(') {
ops.push(s[i]);
} else if (s[i] == ')') {
// 计算到最近一个左括号为止
while (!ops.empty()) {
if (ops.top() == '(') {
ops.pop();
break;
}
_calc(nums, ops);
}
} else if (isdigit(s[i])) {
int num = s[i++] - '0';
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while (i < n && isdigit(s[i])) {
num = num * 10 + (s[i++] - '0');
}
nums.push(num);
i--;
} else {
if (i > 0 && s[i - 1] == '(') {
nums.push(0);
}
// 有一个新操作要入栈时，先把栈内可以算的都算了
// 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
while (!ops.empty() && ops.top() != '(') {
if (level[ops.top()] < level[s[i]]) {
break;
}
_calc(nums, ops);
}
ops.push(s[i]);
}
}
// 将剩余的计算完
while (!ops.empty()) _calc(nums, ops);
return nums.top();
}
void _calc(stack<long>& nums, stack<char>& ops) {
if (ops.size() < 1 || nums.size() < 2) return;
int num2 = nums.top(); nums.pop();
int num1 = nums.top(); nums.pop();
int oper = ops.top(); ops.pop();
int ans = 0;
if (oper == '+') {
ans = num1 + num2;
} else if (oper == '-') {
ans = num1 - num2;
} else if (oper == '*') {
ans = num1 * num2;
} else if (oper == '/') {
ans = num1 / num2;
} else if (oper == '%') {
ans = num1 % num2;
} else if (oper == '^') {
ans = pow(num1, num2);
}
nums.push(ans);
}
};
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
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
# 0227. 基本计算器 II (opens new window)
题目
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
解析
见 0224. 基本计算器。
代码
点击查看代码
class Solution {
unordered_map<char, int> level = {
{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'%', 2}, {'^', 3}
};
public:
int calculate(string s) {
// 存放所有数字，为了防止第一个数为负数，先添加一个 0
stack<long> nums;
nums.push(0);
// 存放所有非数字的操作符
stack<char> ops;
int n = s.length();
for (int i = 0; i < n; i++) {
if (s[i] == ' ') {
continue;
} else if (s[i] == '(') {
ops.push(s[i]);
} else if (s[i] == ')') {
// 计算到最近一个左括号为止
while (!ops.empty()) {
if (ops.top() == '(') {
ops.pop();
break;
}
_calc(nums, ops);
}
} else if (isdigit(s[i])) {
int num = s[i++] - '0';
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while (i < n && isdigit(s[i])) {
num = num * 10 + (s[i++] - '0');
}
nums.push(num);
i--;
} else {
if (i > 0 && s[i - 1] == '(') {
nums.push(0);
}
// 有一个新操作要入栈时，先把栈内可以算的都算了
// 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
while (!ops.empty() && ops.top() != '(') {
if (level[ops.top()] < level[s[i]]) {
break;
}
_calc(nums, ops);
}
ops.push(s[i]);
}
}
// 将剩余的计算完
while (!ops.empty()) _calc(nums, ops);
return nums.top();
}
void _calc(stack<long>& nums, stack<char>& ops) {
if (ops.size() < 1 || nums.size() < 2) return;
int num2 = nums.top(); nums.pop();
int num1 = nums.top(); nums.pop();
int oper = ops.top(); ops.pop();
int ans = 0;
if (oper == '+') {
ans = num1 + num2;
} else if (oper == '-') {
ans = num1 - num2;
} else if (oper == '*') {
ans = num1 * num2;
} else if (oper == '/') {
ans = num1 / num2;
} else if (oper == '%') {
ans = num1 % num2;
} else if (oper == '^') {
ans = pow(num1, num2);
}
nums.push(ans);
}
};
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
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
# 0439. 三元表达式解析器 (opens new window)
题目
给定一个以字符串表示的任意嵌套的三元表达式，计算表达式的值。你可以假定给定的表达式始终都是有效的并且只包含数字 0-9, ?, :, T 和 F (T 和 F 分别表示真和假）。
注意：
- 给定的字符串长度 ≤ 10000。
- 所包含的数字都只有一位数。
- 条件表达式从右至左结合（和大多数程序设计语言类似）。
- 条件是 T 和 F其一，即条件永远不会是数字。
- 表达式的结果是数字 0-9, T 或者 F。
解析
和 0150. 逆波兰表达式求值 思路类似，不同点在于本题需要从后向前遍历。
代码
class Solution {
public:
string parseTernary(string expression) {
stack<char> stk;
for (int i = expression.length() - 1; i >= 0; i--) {
if (!stk.empty() && stk.top() == '?') {
stk.pop();
char first = stk.top(); stk.pop();
stk.pop();
char second = stk.top(); stk.pop();
if (expression[i] == 'T') {
stk.push(first);
} else {
stk.push(second);
}
} else {
stk.push(expression[i]);
}
}
return string{stk.top()};
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 0772. 基本计算器 III (opens new window)
题目
实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。
你可以假定给定的表达式总是有效的。所有的中间结果的范围为 [, - 1] 。
解析
见 0224. 基本计算器。
代码
点击查看代码
class Solution {
unordered_map<char, int> level = {
{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'%', 2}, {'^', 3}
};
public:
int calculate(string s) {
// 存放所有数字，为了防止第一个数为负数，先添加一个 0
stack<long> nums;
nums.push(0);
// 存放所有非数字的操作符
stack<char> ops;
int n = s.length();
for (int i = 0; i < n; i++) {
if (s[i] == ' ') {
continue;
} else if (s[i] == '(') {
ops.push(s[i]);
} else if (s[i] == ')') {
// 计算到最近一个左括号为止
while (!ops.empty()) {
if (ops.top() == '(') {
ops.pop();
break;
}
_calc(nums, ops);
}
} else if (isdigit(s[i])) {
int num = s[i++] - '0';
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while (i < n && isdigit(s[i])) {
num = num * 10 + (s[i++] - '0');
}
nums.push(num);
i--;
} else {
if (i > 0 && s[i - 1] == '(') {
nums.push(0);
}
// 有一个新操作要入栈时，先把栈内可以算的都算了
// 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
while (!ops.empty() && ops.top() != '(') {
if (level[ops.top()] < level[s[i]]) {
break;
}
_calc(nums, ops);
}
ops.push(s[i]);
}
}
// 将剩余的计算完
while (!ops.empty()) _calc(nums, ops);
return nums.top();
}
void _calc(stack<long>& nums, stack<char>& ops) {
if (ops.size() < 1 || nums.size() < 2) return;
int num2 = nums.top(); nums.pop();
int num1 = nums.top(); nums.pop();
int oper = ops.top(); ops.pop();
int ans = 0;
if (oper == '+') {
ans = num1 + num2;
} else if (oper == '-') {
ans = num1 - num2;
} else if (oper == '*') {
ans = num1 * num2;
} else if (oper == '/') {
ans = num1 / num2;
} else if (oper == '%') {
ans = num1 % num2;
} else if (oper == '^') {
ans = pow(num1, num2);
}
nums.push(ans);
}
};
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
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