Description

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

Note: Do not use the eval built-in library function.

Solution

DFS

class Solution {
    private int pos = 0;
    
    public int calculate(String s) {
        int pre = readNum(s);
        
        while (hasNext(s) && s.charAt(pos) != ')') {
            boolean isAdd = readOp(s);
            int curr = readNum(s);
            pre = isAdd ? (pre + curr) : (pre - curr);
        }
        
        return pre;
    }
    
    private int readNum(String s) {
        skipSpaces(s);
        
        if (pos == s.length()) {    // corner case for unexpected end
            return 0;
        }
        
        if (s.charAt(pos) != '(') {
            int num = 0;
            while (pos < s.length() && s.charAt(pos) >= '0' && s.charAt(pos) <= '9') {
                num = 10 * num + s.charAt(pos++) - '0';
            }

            return num;
        }
        ++pos;  // skip '('
        int num = calculate(s);
        ++pos;  // skip ')'
        return num;
    }
    
    private boolean readOp(String s) {
        skipSpaces(s);
        return s.charAt(pos++) == '+' ? true : false;
    }
    
    private void skipSpaces(String s) {
        while (pos < s.length() && s.charAt(pos) == ' ') {
            ++pos;
        }
    }
    
    private boolean hasNext(String s) {
        skipSpaces(s);
        return pos < s.length();
    }
}

Stack, time O(n), space O(n)

遇到左括号则将中间结果和符号入栈，遇到右括号则出栈。

另外一个比较巧妙的做法是用integer表示sign，1代表sum，-1代表minus，这样直接做乘法就能实现加减了。

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        char[] arr = s.toCharArray();
        int res = 0;
        int sign = 1;   // 1 means sum and -1 means minus
        int len = s.length();
        
        for (int i = 0; i < len; ++i) {
            if (Character.isDigit(arr[i])) {
                int num = arr[i] - '0';
                while (i + 1 < len && Character.isDigit(arr[i + 1])) {
                    num = 10 * num + arr[i++ + 1] - '0';
                }
                res += num * sign;
            } else if (arr[i] == '+') {
                sign = 1;
            } else if (arr[i] == '-') {
                sign = -1;
            } else if (arr[i] == '(') {
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1;
            } else if (arr[i] == ')') {
                res = res * stack.pop() + stack.pop();
            }
        }
        
        return res;
    }
}