Leetcode 224. Basic Calculator

方法1: 从后往前遍历string，用一个stack。详细解释直接参考lc官方解答1。时间复杂n，空间复杂n，n为string的长度。

class Solution {
    public int calculate(String s) {
        if (s.charAt(0) == '-') s = "0" + s;
        int operand = 0;
        int n = 0;
        Stack<Object> stack = new Stack<>();
        
        for(int i = s.length()-1; i >= 0; i--){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                operand = (int)Math.pow(10, n) * (int)(c - '0') + operand;
                n++;
            }else if(c != ' '){
                if(n != 0){
                    stack.push(operand);
                    n = 0;
                    operand = 0;
                }
                if(c == '('){
                    int res = evaluateExpr(stack);
                    stack.pop();
                    stack.push(res);
                }else{
                    stack.push(c);
                }
            }
        }
        if(n != 0) stack.push(operand);
        return evaluateExpr(stack);
    }
    
    public int evaluateExpr(Stack<Object> stack){
        int res = 0;
        if(!stack.isEmpty()){
            res = (int) stack.pop();
        }
        
        while(!stack.isEmpty() && !((char)stack.peek() == ')')){
            char sign = (char) stack.pop();
            if(sign == '+'){
                res += (int) stack.pop();
            }else{
                res -= (int) stack.pop();
            }
        }
        return res;
    }
}

总结：

• 还有一个方法2，自己去lc上看。