题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "1 + 1"
输出：2
示例 2：
输入：s = " 2-1 + 2 "
输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
提示：
1 <= s.length <= 3 * 105s 由数字、'+'、'-'、'('、')'、和 ' ' 组成s 表示一个有效的表达式- '+' 不能用作一元运算(例如， "+1" 和
"+(2 + 3)" 无效)
- '-' 可以用作一元运算(即 "-1" 和
"-(2 + 3)" 是有效的)
- 输入中不存在两个连续的操作符
- 每个数字和运行的计算将适合于一个有符号的 32位 整数
解法
方法一：栈
我们用一个栈 $stk$ 来保存当前的计算结果和操作符，用一个变量 $sign$ 保存当前的符号，变量 $ans$ 保存最终的计算结果。
接下来，我们遍历字符串 $s$ 的每一个字符：
- 如果当前字符是数字，那么我们用一个循环将后面的连续数字都读进来，然后用当前的符号将其加或者减到 $ans$ 中。
- 如果当前字符是
'+'，我们修改变量 $sign$ 为正号。
- 如果当前字符是
'-'，我们修改变量 $sign$ 为负号。
- 如果当前字符是
'('，我们把当前的 $ans$ 和 $sign$ 入栈，并分别置空置 1，重新开始计算新的 $ans$ 和 $sign$。
- 如果当前字符是
')'，我们弹出栈顶的两个元素，一个是操作符，一个是括号前计算好的数字，我们将当前的数字乘上操作符，再加上之前的数字，作为新的 $ans$。
遍历完字符串 $s$ 之后，我们返回 $ans$。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $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 | class Solution:
def calculate(self, s: str) -> int:
stk = []
ans, sign = 0, 1
i, n = 0, len(s)
while i < n:
if s[i].isdigit():
x = 0
j = i
while j < n and s[j].isdigit():
x = x * 10 + int(s[j])
j += 1
ans += sign * x
i = j - 1
elif s[i] == "+":
sign = 1
elif s[i] == "-":
sign = -1
elif s[i] == "(":
stk.append(ans)
stk.append(sign)
ans, sign = 0, 1
elif s[i] == ")":
ans = stk.pop() * ans + stk.pop()
i += 1
return 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 | class Solution {
public int calculate(String s) {
Deque<Integer> stk = new ArrayDeque<>();
int sign = 1;
int ans = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int j = i;
int x = 0;
while (j < n && Character.isDigit(s.charAt(j))) {
x = x * 10 + s.charAt(j) - '0';
j++;
}
ans += sign * x;
i = j - 1;
} else if (c == '+') {
sign = 1;
} else if (c == '-') {
sign = -1;
} else if (c == '(') {
stk.push(ans);
stk.push(sign);
ans = 0;
sign = 1;
} else if (c == ')') {
ans = stk.pop() * ans + stk.pop();
}
}
return 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 | class Solution {
public:
int calculate(string s) {
stack<int> stk;
int ans = 0, sign = 1;
int n = s.size();
for (int i = 0; i < n; ++i) {
if (isdigit(s[i])) {
int x = 0;
int j = i;
while (j < n && isdigit(s[j])) {
x = x * 10 + (s[j] - '0');
++j;
}
ans += sign * x;
i = j - 1;
} else if (s[i] == '+') {
sign = 1;
} else if (s[i] == '-') {
sign = -1;
} else if (s[i] == '(') {
stk.push(ans);
stk.push(sign);
ans = 0;
sign = 1;
} else if (s[i] == ')') {
ans *= stk.top();
stk.pop();
ans += stk.top();
stk.pop();
}
}
return 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 | func calculate(s string) (ans int) {
stk := []int{}
sign := 1
n := len(s)
for i := 0; i < n; i++ {
switch s[i] {
case ' ':
case '+':
sign = 1
case '-':
sign = -1
case '(':
stk = append(stk, ans)
stk = append(stk, sign)
ans, sign = 0, 1
case ')':
ans *= stk[len(stk)-1]
stk = stk[:len(stk)-1]
ans += stk[len(stk)-1]
stk = stk[:len(stk)-1]
default:
x := 0
j := i
for ; j < n && '0' <= s[j] && s[j] <= '9'; j++ {
x = x*10 + int(s[j]-'0')
}
ans += sign * x
i = j - 1
}
}
return
}
|
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 | function calculate(s: string): number {
const stk: number[] = [];
let sign = 1;
let ans = 0;
const n = s.length;
for (let i = 0; i < n; ++i) {
if (s[i] === ' ') {
continue;
}
if (s[i] === '+') {
sign = 1;
} else if (s[i] === '-') {
sign = -1;
} else if (s[i] === '(') {
stk.push(ans);
stk.push(sign);
ans = 0;
sign = 1;
} else if (s[i] === ')') {
ans *= stk.pop() as number;
ans += stk.pop() as number;
} else {
let x = 0;
let j = i;
for (; j < n && !isNaN(Number(s[j])) && s[j] !== ' '; ++j) {
x = x * 10 + (s[j].charCodeAt(0) - '0'.charCodeAt(0));
}
ans += sign * x;
i = j - 1;
}
}
return 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 | public class Solution {
public int Calculate(string s) {
var stk = new Stack<int>();
int sign = 1;
int n = s.Length;
int ans = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == ' ') {
continue;
}
if (s[i] == '+') {
sign = 1;
} else if (s[i] == '-') {
sign = -1;
} else if (s[i] == '(') {
stk.Push(ans);
stk.Push(sign);
ans = 0;
sign = 1;
} else if (s[i] == ')') {
ans *= stk.Pop();
ans += stk.Pop();
} else {
int num = 0;
while (i < n && char.IsDigit(s[i])) {
num = num * 10 + s[i] - '0';
++i;
}
--i;
ans += sign * num;
}
}
return ans;
}
}
|