表达式求值的通用解法

宋正兵 on 2021-09-24

题目大意

【NC137 表达式求值】

请写一个整数计算器,支持加减乘三种运算和括号。

示例1:

1
2
输入:"(2*(3-4))*5"
返回值:-10

示例2:

1
2
输入:"3+2*3*4-1"
返回值:26

解题思路

对于【表达式求值】这一类问题,都可以使用这套思路来解决。

我们定义两个栈 numsopsnums 存放所有的数字,ops 存放所有的数字以外的操作。

然后从前往后,对遍历到的字符做分情况讨论:

  • (:直接加入 ops 中,等待与之匹配的 )
  • ):使用现有的 opsnums 进行计算,直到遇到左边最近的左括号为止,计算结果存回 nums
  • 数字:从当前位置开始继续往后取,将多位数字整体取出,加入 nums
  • + - * / ^ %:将操作符放入 ops 中,放入之前先把 ops 栈内能算的先算了,注意只有栈内运算符比当前运算符优先级高/同等,才进行计算,直到没有操作符或者遇到左括号,计算结果放到 nums

因为一次遍历就能解决问题,所以时间复杂度是 $O(n)$。

代码

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
import java.util.*;
public class Solution {
public int solve (String s) {
// 存放操作符的优先级
Map<Character, Integer> map = new HashMap<>();
map.put('+', 1);
map.put('-', 1);
map.put('*', 2);
// 一个数字栈,一个操作符栈
/* 1)'(':直接加入ops中
2)')':使用现有的nums和ops进行计算,直到遇到左边第一个最近的左括号为止,结果存放回nums
3)'+'、'-'、'*':先把栈内可以算的都算掉(栈内运算符比当前运算符优先级高/同等,才进行计算),
使用现有的nums和ops计算,直到没有操作符/遇到左括号为止,将结果放入nums
*/
Stack<Integer> nums = new Stack<>();
Stack<Character> ops = new Stack<>();
char[] arr = s.toCharArray();
// 防止第一个数是负数
nums.add(0);
for (int i = 0; i < arr.length; i++) {
char ch = arr[i];
if (ch == '(') {
ops.push(arr[i]);
} else if (arr[i] == ')') {
// 计算到最近一个左括号为止
while (!ops.isEmpty()) {
if (ops.peek() != '(') {
cal(nums, ops);
} else {
// 左括号出栈
ops.pop();
break;
}
}
} else {
// 连续数字整体取出,加入 nums
if (Character.isDigit(ch)) {
int j = i;
int num = 0;
while (j < arr.length && Character.isDigit(arr[j])) {
num = num * 10 + arr[j++] - '0';
}
nums.push(num);
i = j - 1;
} else {
// 先把栈内可以算的都算掉
while (!ops.isEmpty() && ops.peek() != '(') {
char prev = ops.peek();
if (map.get(prev) >= map.get(ch)) {
cal(nums, ops);
} else {
break;
}
}
ops.push(ch);
}
}
}
// 把栈内剩余的计算完毕
while (!ops.isEmpty()) {
cal(nums, ops);
}
return nums.peek();
}

public static void cal(Stack<Integer> nums, Stack<Character> ops) {
if (ops.isEmpty() || nums.isEmpty() || nums.size() < 2) {
return;
}
char op = ops.pop();
int b = nums.pop();
int a = nums.pop();
switch (op) {
case '+': a = a + b; break;
case '-': a = a - b; break;
case '*': a = a * b; break;
}
nums.push(a);
}
}