/**
1. 优先级 () > +-
2. 空格没用, 计算前全删掉
3. 用栈来缓存, 延迟计算+-:
    3.1 遍历到 (, + , - , 0~9 全都入栈
    3.2 遍历到 ) 一直出栈并计算 直到遇到 ( 为止
    3.3 遍历结束后计算栈中的值
*/

class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        Stack<String> stack = new Stack<>();
        char[] str = s.toCharArray();
        int n = s.length();
        for (int i = 0 ; i < n ; i++){
            if (str[i] == '(' || str[i] == '-' || str[i] == '+') {
                stack.push(String.valueOf(str[i]));
            } else if (str[i] == ')') {
                int result = 0;
                while (stack.size() > 0){
                    int x = Integer.valueOf(stack.pop());
                    String sign = stack.pop();
                    result += sign.equals("-") ? 0 - x : x;
                    if (sign.equals("(")) break;
                }
                stack.push(String.valueOf(result));
            } else {
                int y = 0;
                for (int j = i ; j < n && '0' <= str[j] && str[j] <= '9' ; i = j++) y = y * 10 + str[j] - '0';
                stack.push(String.valueOf(y));
            }
        }

        int result = 0;
        while (stack.size() > 1){
            int x = Integer.valueOf(stack.pop());
            String sign = stack.pop();
            result += sign.equals("+") ? x : 0 - x;
        }
        return result + Integer.parseInt(stack.pop());
    }
}