224 Basic Calculator

1. Question

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open(and closing parentheses), the plus+or minus sign-, non-negative integers and empty spaces.
You may assume that the given expression is always valid.
Some examples:
1
"1 + 1" = 2
2
" 2-1 + 2 " = 3
3
"(1+(4+5+2)-3)+(6+8)" = 23
Copied!

2. Implementation

思路:这题输入的符号只有括号,加号,减号和数字,因为有括号,所以要运算优先级,括号里的表达式是一个整体,所以适合用stack做
1
class Solution {
2
public int calculate(String s) {
3
s.replace(" ", "");
4
int res = 0;
5
Stack<Integer> stack = new Stack<>();
6
stack.push(1);
7
int i = 0;
8
int sign = 1;
9
10
while (i < s.length()) {
11
char c = s.charAt(i);
12
if (Character.isDigit(c)) {
13
int val = 0;
14
15
while (i < s.length() && Character.isDigit(s.charAt(i))) {
16
val = 10 * val + s.charAt(i) - '0';
17
++i;
18
}
19
--i;
20
res += sign * val * stack.peek();
21
}
22
else if (c == '(') {
23
stack.push(sign * stack.peek());
24
sign = 1;
25
}
26
else if (c == ')') {
27
stack.pop();
28
}
29
else {
30
sign = c == '-' ? -1 : 1;
31
}
32
++i;
33
}
34
return res;
35
}
36
}
Copied!

3. Time & Space Complexity

时间和空间复杂度O(n)