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

(1) Stack

思路：由于这题只有括号和加减两种运算，因此我们只需要一个stack，处理括号内的运算。我们用sign这个变量表示当前数字的正负，遇到加号时，sign是1，负号时，sign是-1。当我们遇到左括号时，说明有新的运算要运行，所以先将之前的运算结果res存入stack，然后也将sign存入stack。遇到右括号时，则说明括号内的运算结束，得到结果res后，将res乘以stack顶的符号，然后加上stack顶的数字

class Solution {
    int i = 0;
    public int calculate(String s) {
        Stack<Integer> stack = new Stack();
        int val = 0;
        int res = 0;
        int sign = 1;
        int n = s.length();

        int i = 0;

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

(2) Recursion

思路：recursion的思路比较明了，在括号内的运算其实是一个subproblem，所以我们维护一个全局变量i，表示当前在string的位置，遇到左括号时，则递归地call calculate这个function，遇到右括号时，将计算res，将res返回

class Solution {
    int i = 0;
    public int calculate(String s) {
        int sign = 1;
        int val = 0;
        int res = 0;
        int n = s.length();

        while (i < n) {
            char c = s.charAt(i);
            ++i;

            if (Character.isDigit(c)) {
                val = 10 * val + c - '0';
            }
            else if (c == '+' || c == '-') {
                res += val * sign;
                val = 0;
                sign = c == '+' ? 1 : -1;
            }
            else if (c == '(') {
                val = calculate(s);
            }
            else if (c == ')') {
                res += val * sign;
                return res;
            }
        }
        res += val * sign;
        return res;
    }
}

3. Time & Space Complexity

(1) Stack: 时间和空间复杂度都是O(n)

(2) Recursion: 时间复杂度O(n), 空间复杂度O(n)