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)