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做，但要注意的是这里的stack存的是符号(1 或者 -1)。需要考虑的cases:

(1) 可能会连续得到的字符都是数字，所以我们通过num得到最后的数字

(2) 如果当前的字符是 '+', '-'， sign要根据当前的字符更新，并将num变为0

(3) 如果当前字符是'(', 将sign压栈

(4) 如果当前字符是')', 将当前sign出栈

class Solution {
    public int calculate(String s) {
        int res = 0;
        int num = 0, sign = 1;

        Stack<Integer> stack = new Stack<>();
        stack.push(sign);

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = 10 * num + (c - '0');
            }
            else if (c == '+' || c == '-') {
                res += sign * num;
                sign = stack.peek() * (c == '+' ? 1 : -1);
                num = 0;
            }
            else if (c == '(') {
                stack.push(sign);
            }
            else if (c == ')') {
                stack.pop();
            }
        }
        res += sign * num;
        return res;
    }
}

3. Time & Space Complexity

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