227. 基本计算器 II

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

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

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

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

• 1 <= s.length <= 3 * 10^5
• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
• s 表示一个 有效表达式
• 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
• 题目数据保证答案是一个 32-bit 整数

栈

一个栈存中间结果，一个变量sign存符号。可以实现把去掉空格的字符串加入一个双边队列中，这只是一个优化，不强制。每次从队列中弹出字符，如果该字符是数字，则计算它和前面的数字组成的数字，如果是运算符，则根据符号计算结果后入栈。以3+4+5为例，遇到了第二个符号c=+，说明前面的数字已结束，要处理前面的公式。此时的num是4，sign是第一个+，stack.pop是3。计算得7后入栈，此时要把num置为0，不然遇到5时是35而不是5，然后更新sign，下次遇到符号时会用到本轮的sign和下轮的num和本轮入栈的数字。先符号再数字。

空格是字符不是字符串，要用单引号。

每次循环都新开一个栈。

不要忘记 removeFirst 的条件：!deque.isEmpty()。

if 的顺序无所谓。

c - '0' 是为了把 c 从字符变成数字，和溢出无关

递归完不要忘记赋值。

本题没有要求括号，如果要求括号，就需要添加这两个判断

            if (c == '(') {
                num = helper(deque); // 递归完不要忘记赋值。注意括号里最终是一个数字。
            }

            if (c == ')') {
                // 跳出循环，计算栈内元素总和，然后返回，结束递归。
                break;
            }

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<>();
        char sign = '+';
        int num = 0;

        while (!deque.isEmpty()) { // 不要忘记 removeFirst 的条件：!deque.isEmpty()
            char c = deque.removeFirst();

            // 遇到数字就计算num，等遇到符号时再把num入栈。
            if (Character.isDigit(c)) { // if 的顺序无所谓。
                num = num * 10 + (c - '0'); // c - '0' 是为了把 c 从字符变成数字，和溢出无关
            }
            if (!Character.isDigit(c) || deque.isEmpty()) {
                // 以3+4+5为例，遇到了第二个符号c=+，说明前面的数字已结束，要处理前面的公式。
                // 此时的num是4，sign是第一个+，stack.pop是3。计算得7后入栈，此时要把num置为0，
                // 不然遇到5时是35而不是5，然后更新sign，下次遇到符号时会用到本轮的sign和下轮的num和本轮入栈的数字。先符号再数字。
                // 遇到+-，直接入栈，遇到乘除，先计算，再入栈，最后进行总的求和。
                if (sign == '+')
                    stack.push(num);
                else if (sign == '-')
                    stack.push(-num);
                else if (sign == '*')
                    stack.push(stack.pop() * num);
                else if (sign == '/')
                    stack.push(stack.pop() / num);

                // 每次用完数据之后一定要更新一下数据
                if (!deque.isEmpty()) {
                    // 这里的sign下一轮才能用到。
                    sign = c;
                    num = 0;
                }
            }
        }

        // 接下来对栈中的元素求和
        int res = 0;
        for (Integer i : stack) {
            res += i;
        }
        return res;
    }
}

• 时间复杂度：O(n)，其中 n 为字符串 s 的长度。需要遍历字符串 s 一次，计算表达式的值。
• 空间复杂度：O(n)，其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间，栈的元素个数不超过 n。