题目描述

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 .

给你一个字符串，其中包含圆括号、加减号、非负数和空格，实现简单的运算。

举个例子：

((24 + 8) - (10 - 2)) = 24

Update at 2020_0728

Thanks Y总，重新梳理下思路。

首先，我们需要两个栈，一个用来存放数字，另一个用来存放操作符。

然后，分为四种场景：

第一，如果当前字符为空格，直接跳过。

第二，如果当前字符是(、+或-，直接加入操作数栈中。

第三，如果当前字符是)，此时操作数栈顶必然是(，因此将其弹出。

然后判断操作数栈顶是否为空，且操作数不是(，也就是+或-

此时，从数字栈中弹出两个数字，并从操作数中弹出一个操作数，进行计算。

第四，如果当前是数字，注意两点，

第一点，该整数可能是多位的，所以需要借助while循环往后遍历。

第二点，遍历时，我们需要借助一个变量j，防止影响变量i，最后记得调整i的值。

完整实现如下：

class Solution {

    private void calc(ArrayDeque<Character> ops, ArrayDeque<Integer> nums){
        int a = nums.pop();
        int b = nums.pop();
        char c = ops.pop();
        if (c == '+') {
            nums.push(b + a);
        } else {
            nums.push(b - a);
        }
    }

    public int calculate(String s) {

        ArrayDeque<Integer>  nums = new ArrayDeque<>();
        ArrayDeque<Character> ops = new ArrayDeque<>();
        int n = s.length();
        char[] ch = s.toCharArray();

        for (int i = 0; i < n; i++){
            char c = ch[i];
            if (c == ' ') continue;
            else if (c == '(' || c == '+' || c == '-'){
                ops.push(c);
            } else if (c == ')'){
                // 弹出操作数栈顶的(
                ops.pop();
                // 如果操作数非空，且栈顶元素不是(
                // 那么操作数不是+就是-，则进行一次计算操作。
                if (!ops.isEmpty() && ops.peek() != '('){
                    calc(ops, nums);
                }
            } else {
                // 获取完整的整数，需要借助变量j，防止影响变量i
                int j = i;
                int cur = 0;
                while (j < n && ch[j] >= '0' && ch[j] <= '9'){
                    cur = cur * 10 + (ch[j] - '0') % 10;
                    j++;
                }
                // 借助j，调整i
                i = j - 1;
                // 将数字插入数字栈中
                nums.push(cur);
                // 如果操作数非空，且栈顶元素不是(
                // 那么操作数不是+就是-，则进行一次计算操作。
                if (!ops.isEmpty() && ops.peek() != '('){
                    calc(ops, nums);
                }
            }
        }
        return nums.peek();
    }
}