224 Basic Calculator
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" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
2. Implementation
思路:这题输入的符号只有括号,加号,减号和数字,因为有括号,所以要运算优先级,括号里的表达式是一个整体,所以适合用stack做
class Solution {
public int calculate(String s) {
s.replace(" ", "");
int res = 0;
Stack<Integer> stack = new Stack<>();
stack.push(1);
int i = 0;
int sign = 1;
while (i < s.length()) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int val = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
val = 10 * val + s.charAt(i) - '0';
++i;
}
--i;
res += sign * val * stack.peek();
}
else if (c == '(') {
stack.push(sign * stack.peek());
sign = 1;
}
else if (c == ')') {
stack.pop();
}
else {
sign = c == '-' ? -1 : 1;
}
++i;
}
return res;
}
}
3. Time & Space Complexity
时间和空间复杂度O(n)
Last updated
Was this helpful?