Description#
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "1 + 1"
Output: 2
Example 2:
Input: s = " 2-1 + 2 "
Output: 3
Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
Constraints:
1 <= s.length <= 3 * 105s consists of digits, '+', '-', '(', ')', and ' '.s represents a valid expression.'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).- There will be no two consecutive operators in the input.
- Every number and running calculation will fit in a signed 32-bit integer.
Solutions#
Solution 1: Stack#
We use a stack $stk$ to save the current calculation result and operator, a variable $sign$ to save the current sign, and a variable $ans$ to save the final calculation result.
Next, we traverse each character of the string $s$:
- If the current character is a number, we use a loop to read the following consecutive numbers, and then add or subtract it to $ans$ according to the current sign.
- If the current character is
'+', we change the variable $sign$ to positive. - If the current character is
'-', we change the variable $sign$ to negative. - If the current character is
'(', we push the current $ans$ and $sign$ into the stack, and reset them to empty and 1, and start to calculate the new $ans$ and $sign$. - If the current character is
')', we pop the top two elements of the stack, one is the operator, and the other is the number calculated before the bracket. We multiply the current number by the operator, and add the previous number to get the new $ans$.
After traversing the string $s$, we return $ans$.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string $s$.
Approach 1#
The below can be used in Basic Calculator III
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
| import collections
class Solution:
def calculate(self, s: str) -> int:
def helper(q):
stack = []
sign = '+'
num = 0
while q:
c = q.popleft()
if c.isdigit():
num = num*10 + int(c)
if c == '(':
num = helper(q)
if c in '+-)' or not q:
if sign == '+':
stack.append(num)
elif sign == '-':
stack.append(-num)
sign = c
num = 0
if c == ')':
break
return sum(stack)
q = collections.deque()
for c in s:
q.append(c)
return helper(q)
|
Python Code: Stack approach
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;
}
}
|
