给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

• 1 <= s.length <= 3 * 10^5
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式
• '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
• '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

递归+栈，分类处理，聚类递归

• 把字符分成四类，分类处理
• 把括号里的字符看成一个整体，聚成一类，开一个子递归处理。

class Solution {
     public int calculate(String s) {
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            // 入队的时候就把空格排除在外，省的接下来再额外判断。注意用单引号。
            if (s.charAt(i) != ' ') {
                deque.addLast(s.charAt(i));
            }
        }
        return helper(deque);
    }
    
    private int helper(Deque<Character> deque) { 
        // 每次递归都会都新开一个栈，存储本次递归的中间数，本次递归中会计算栈中的总和。
        // 每次递归都在处理同一个队列，只不过是不同的括号中的数。
        Deque<Integer> stack = new LinkedList<>();
        // 每次递归开始时都把 sign 初始化为 +。
        char sign = '+';
        int num = 0;
        
        while (deque.size() > 0) {
            // 顺序移除队首元素，直到遇到右括号。本次递归就是在计算这些被移除的元素的和。
            char c = deque.removeFirst();
            // if 的顺序无所谓
            if (isdigit(c)) {
                // c - '0' 是为了把 c 从字符变成数字，和溢出无关
                // 解析出连续的数字
                num = num * 10 + (c - '0');
            }
            if (c == '(') {
                // 注意不存在乘法，所以不用担心 3(f) 时 num 先等于 3 再被括号内的值覆盖的问题，即括号前面一定是 sign 而不是 num
                num = helper(deque);
            }
            // 遇到新运算符或者要收尾时处理积存的 sign 和 num。重点。
            if (!isdigit(c) || deque.size() == 0) {
                if (sign == '+') {
                    // sign 和 num 都是上一轮的数据，例如 (1+3)+6，初始时 sign 是 +，表示 1 前面的默认符号。此时遇到新的 +，要把 +1 入栈。
                    stack.addLast(num);
                } else if (sign == '-') {
                    stack.addLast(-num);
                }
                // 更新 sign 和 num。收尾时没必要做下面的两个操作，但是做了也没事，所以就把这两种情况合在一起了。
                num = 0;
                sign = c;
            }
            if (c == ')') {
                // 子递归是在计算括号内的数的和，整个表达式的和就是这些子递归的和。相当于把括号内的数当成一个整体。
                break;
            }
        }
        
        // 计算本次递归中的栈的数字和
        int res = 0;
        while (stack.size() > 0) {
            int top = stack.removeLast();
            res += top;
        }
        return res;
    }
    
    private boolean isdigit(char c) {
        if (c >= '0' && c <= '9') {
            return true;
        }
        return false;
    }
}

• 时间复杂度: $O(n)$，因为只顺序遍历了一次。
• 空间复杂度: $O(n)$，所有递归栈之和。