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

Code

public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();
        int i = 0;
        StringBuilder sb = new StringBuilder();
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c == ' ') {
                i++;
                continue;
            }
            if (c == '(') {
                i++;
                ops.push(c);
                continue;
            }
            if (c == ')') {
                i++;
                char op = ops.pop();
                while (op != '(') {
                    int b = nums.pop();
                    int a = nums.pop();
                    nums.push(calculate(a, b, op));
                    op = ops.pop();
                }
                continue;
            }
            if (c == '+' || c == '-') {
                while (!ops.isEmpty() && (ops.peek() == '+' || ops.peek() == '-')) {
                    char op = ops.pop();
                    int b = nums.pop();
                    int a = nums.pop();
                    nums.push(calculate(a, b, op));
                }
                ops.push(c);
                i++;
                continue;
            }
            if ((c >= '0' && c <= '9')) {
                sb.append(c);
                i++;
                for (; i < s.length(); i++) {
                    char ci = s.charAt(i);
                    if (ci >= '0' && ci <= '9') {
                        sb.append(ci);
                    } else {
                        break;
                    }
                }
                nums.push(Integer.parseInt(sb.toString()));
                sb.delete(0, sb.length());
            }
        }
        
        while (!ops.isEmpty()) {
            char op = ops.pop();
            int b = nums.pop();
            int a = nums.pop();
            nums.push(calculate(a, b, op));
        }
        
        return nums.pop();
    }
    
    public int calculate(int a, int b, char op) {
        if (op == '+') return a + b;
        return a - b;
    }
}

Solution

维护两个栈：数字栈和符号栈。

扫描整个字符串，遇到数字直接入数字栈。遇到其他字符分类讨论：
（1）' '：跳过
（2）'('：入符号栈
（3）')'：对符号栈不断出栈，每弹出一个符号进行一次计算，计算时将数字栈中两个数字出栈，将计算结果入栈，直到'('出栈。
（4）'+' '-'：对符号栈不断出栈，每弹出一个符号进行一次计算，计算时将数字栈中两个数字出栈，将计算结果入栈，直到栈为空或者栈顶元素为'('。将当前符号入栈。

遍历完成后需对符号栈中剩余的符号进行计算。