56.基本计算器

题目

给你一个字符串表达式 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 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位整数

思路

如果你是一个会计，老板给你一张纸条让你算:

1 - (2 + 3) + (...

你会怎么做?

先记住"1"
看到减号，记住"接下来括号里的结果要被减掉"
进入括号，算出 2 + 3 = 5
回来: 1 减掉 5 = -4

关键是第二步: 你在进括号之前，脑子里记住了两件事:

括号外已经算到了多了
括号的结果要加还是减

这两件事就是要压栈的内容。

整体的合并公式是这样的:

result = outerResult + outerSign * innerResult

这个公式本质上就是把括号展开:

1 - (2 + 3)     

= 1 + (-1) * (2 + 3)       // outerSign = -1 乘进去
= 1 + (-1) * 5
= -4

outerSign就是括号前面那个符号，它要乘给括号里整体的结果。

这里还有一个点就是多位数怎么处理?

假设字符串里每个字符单独出现， 123是三个字符'1','2','3'。

num = num * 10 + (c - '0')

读到'1': num = 0 * 10 + 1 = 1
读到'2': num = 1 * 10 + 2 = 12
读到'3': num = 12 * 10 + 3 = 123

总结:

sign记住下一个数字的符号，遇到数字就累积，遇到运算符就结算
遇到(左括号就把"算到哪里了和括号前的符号"压栈，然后从零重新算
遇到)右括号就用公式合并: 括号外的值 + 括号符号 * 括号内的值

class Solution {
    fun calculate(s: String): Int {
        // 存放括号外的状态
        val stack = ArrayDeque<Int>()
        // 当前层级已经算出来的值
        var result = 0
        // 下一个数字前面的符号，+1 或 -1，用它来乘，这样就能代表了正负
        var sign = 1
        // 正在读取的数字（可能多位）
        var num = 0

        for (c in s) {
            when {
                c.isDigit() -> {
                    // 构建多位数，例如"123" -> 1 -> 12 -> 123
                    num = num * 10 + (c - '0')
                }

                c == '+' || c == '-' -> {
                    // 遇到运算符，先把前一个数结算
                    result += sign * num
                    num = 0
                    sign = if (c == '+') 1 else -1
                }

                c == '(' -> {
                    // 进括号：把当前状态压栈(保存当前状态)，进入括号后重新开始
                    // 保存括号外算到的值
                    stack.addLast(result)
                    // 保存括号前的符号
                    stack.addLast(sign)     
                    // 重新开始
                    result = 0              
                    sign = 1
                }

                c == ')' -> {
                    // 出括号：先结算括号内最后一个数
                    result += sign * num
                    num = 0

                    // 取出括号外的状态
                    val outerSign = stack.removeLast()
                    val outerResult = stack.removeLast()

                    // 合并：括号外的值 + 括号符号 × 括号内的值
                    result = outerResult + outerSign * result
                }

                // 空格：什么都不做，自动跳过
            }
        }

        // 字符串结束后，结算最后一个数字
        // （最后一个数后面没有运算符来触发结算）
        result += sign * num

        return result
    }
}

【进阶补充】双栈解决通用「表达式计算」问题

我们可以使用两个栈 nums 和 ops:

nums ：存放所有的数字
ops ：存放所有的数字以外的操作，+/- 也看做是一种操作

然后从前往后做，对遍历到的字符做分情况讨论：

空格 : 跳过
( : 直接加入 ops 中，等待与之匹配的 )
) : 使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums
数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums
+/- : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉，使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums

一些细节：

由于第一个数可能是负数，为了减少边界判断。一个小技巧是先往 nums 添加一个 0 为防止 () 内出现的首个字符为运算符，将所有的空格去掉，并将 (- 替换为 (0-，(+ 替换为 (0+（当然也可以不进行这样的预处理，将这个处理逻辑放到循环里去做）

class Solution {
    public int calculate(String s) {
        // 存放所有的数字
        Deque<Integer> nums = new ArrayDeque<>();
        // 为了防止第一个数为负数，先往 nums 加个 0
        nums.addLast(0);
        // 将所有的空格去掉
        s = s.replaceAll(" ", "");
        // 存放所有的操作，包括 +/-
        Deque<Character> ops = new ArrayDeque<>();
        int n = s.length();
        char[] cs = s.toCharArray();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                // 计算到最近一个左括号为止
                while (!ops.isEmpty()) {
                    char op = ops.peekLast();
                    if (op != '(') {
                        calc(nums, ops);
                    } else {
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                if (isNum(c)) {
                    int u = 0;
                    int j = i;
                    // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                    while (j < n && isNum(cs[j])) u = u * 10 + (int)(cs[j++] - '0');
                    nums.addLast(u);
                    i = j - 1;
                } else {
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.addLast(0);
                    }
                    // 有一个新操作要入栈时，先把栈内可以算的都算了
                    while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
                    ops.addLast(c);
                }
            }
        }
        while (!ops.isEmpty()) calc(nums, ops);
        return nums.peekLast();
    }
    void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return;
        if (ops.isEmpty()) return;
        int b = nums.pollLast(), a = nums.pollLast();
        char op = ops.pollLast();
        nums.addLast(op == '+' ? a + b : a - b);
    }
    boolean isNum(char c) {
        return Character.isDigit(c);
    }
}

下一题

邮箱：charon.chui@gmail.com
Good Luck!