难度困难
题目描述
实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。
你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足 [-231, 231 - 1] 。
注意：你不能使用任何将字符串作为表达式求值的内置函数，比如 eval() 。
示例 1：
输入：s = "1+1"
输出：2
示例 2：
输入：s = "6-4/2"
输出：4
示例 3：
输入：s = "2*(5+5*2)/3+(6/2+8)"
输出：21
提示：
1 <= s <= 104s 由整数、'+'、'-'、'*'、'/'、'(' 和 ')' 组成s 是一个 有效的 表达式
解法
方法一
思考
表达式含加减乘除与括号，长度 \(10^4\)，需要按优先级求值。乘除应立即与栈顶结合，加减只把带符号的数入栈，最后求和。
括号相当于子表达式：遇到 ( 递归算完到 )，返回值当作当前数字。队列顺序消费字符，避免反复切片。
\(\textit{sign}\) 记下上一个运算符，在运算符或结束时把 \(\textit{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 | class Solution:
def calculate(self, s: str) -> int:
def dfs(q):
num, sign, stk = 0, "+", []
while q:
c = q.popleft()
if c.isdigit():
num = num * 10 + int(c)
if c == "(":
num = dfs(q)
if c in "+-*/)" or not q:
match sign:
case "+":
stk.append(num)
case "-":
stk.append(-num)
case "*":
stk.append(stk.pop() * num)
case "/":
stk.append(int(stk.pop() / num))
num, sign = 0, c
if c == ")":
break
return sum(stk)
return dfs(deque(s))
|
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 | class Solution {
public int calculate(String s) {
Deque<Character> q = new ArrayDeque<>();
for (char c : s.toCharArray()) {
q.offer(c);
}
return dfs(q);
}
private int dfs(Deque<Character> q) {
long num = 0;
char sign = '+';
List<Long> stk = new ArrayList<>();
while (!q.isEmpty()) {
char c = q.poll();
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if (c == '(') {
num = dfs(q);
}
if ("+-*/)".indexOf(c) >= 0 || q.isEmpty()) {
if (sign == '+') {
stk.add(num);
} else if (sign == '-') {
stk.add(-num);
} else if (sign == '*') {
stk.set(stk.size() - 1, stk.get(stk.size() - 1) * num);
} else {
stk.set(stk.size() - 1, stk.get(stk.size() - 1) / num);
}
num = 0;
sign = c;
}
if (c == ')') {
break;
}
}
long ans = 0;
for (long x : stk) {
ans += x;
}
return (int) 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 | class Solution {
public:
int calculate(string s) {
queue<char> q;
for (char c : s) {
q.push(c);
}
return dfs(q);
}
private:
int dfs(queue<char>& q) {
long long num = 0;
char sign = '+';
vector<long long> stk;
while (!q.empty()) {
char c = q.front();
q.pop();
if (isdigit(c)) {
num = num * 10 + (c - '0');
}
if (c == '(') {
num = dfs(q);
}
if (c == '+' || c == '-' || c == '*' || c == '/' || c == ')' || q.empty()) {
if (sign == '+') {
stk.push_back(num);
} else if (sign == '-') {
stk.push_back(-num);
} else if (sign == '*') {
stk.back() *= num;
} else {
stk.back() /= num;
}
num = 0;
sign = c;
}
if (c == ')') {
break;
}
}
return accumulate(stk.begin(), stk.end(), 0LL);
}
};
|
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 | func calculate(s string) int {
q := []byte(s)
var dfs func() int
dfs = func() int {
num, sign := 0, byte('+')
var stk []int
for len(q) > 0 {
c := q[0]
q = q[1:]
if c >= '0' && c <= '9' {
num = num*10 + int(c-'0')
}
if c == '(' {
num = dfs()
}
if c == '+' || c == '-' || c == '*' || c == '/' || c == ')' || len(q) == 0 {
switch sign {
case '+':
stk = append(stk, num)
case '-':
stk = append(stk, -num)
case '*':
stk[len(stk)-1] *= num
default:
stk[len(stk)-1] /= num
}
num, sign = 0, c
}
if c == ')' {
break
}
}
ans := 0
for _, x := range stk {
ans += x
}
return ans
}
return dfs()
}
|