LC224. 基本计算器

题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 示例 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 + 1"，输出 2；输入 "(1+(4+5+2)-3)+(6+8)"，输出 23。注意，这里没有乘除，只有加减，但括号会改变计算顺序。我们要写一个程序，能自动算出这种表达式的值。

思路是怎么来的

想象一下你平时算数学题：比如 5 - (2 + 3)，你会先算括号里的 2+3=5，然后 5-5=0。但计算机不能像人一样“一眼看出”括号，它只能一个一个字符地读。所以我们需要一个方法，让计算机也能处理括号。

核心想法：把减法变成加法。比如 5 - 3 可以看成 5 + (-3)。这样，整个表达式就全是加法了，只是有些数字前面带个负号。这样我们只需要记住“当前数字是正还是负”，然后一直累加就行。

括号怎么处理：遇到括号时，括号里面的计算规则和外面一样，但括号里的结果要跟括号外面的符号结合。比如 5 - (2+3)，括号外面是减号，所以括号里的结果要乘以 -1 再加到外面。我们可以用“栈”来帮忙：遇到左括号时，把当前已经算好的结果和当前的符号存起来，然后重新开始算括号里面的；遇到右括号时，把括号里的结果乘上之前存的符号，再加到之前存的结果上。

生活比喻：想象你在记账。你有一个本子记录总账（res），还有一个“当前符号”标签（sign），表示接下来要加的钱是正数还是负数。遇到左括号时，你把总账和符号先记到一张纸条上塞进抽屉（栈），然后拿出一个新本子，从零开始记括号里的账。遇到右括号时，你把新本子的结果乘以抽屉里纸条上的符号，再加到抽屉里纸条上的总账上，然后继续用这个总账记账。

代码逐步拆解

我们来看参考代码，一步一步解释。

Stack<Integer> stack = new Stack<Integer>();
int sign = 1;   // 当前符号，1 表示正，-1 表示负
int res = 0;    // 当前累计结果
int length = s.length();

• stack：用来存遇到左括号时的“旧结果”和“旧符号”。因为栈是后进先出，正好对应括号嵌套。
• sign：记录当前数字是加还是减。初始为 1，因为第一个数字默认是正数。
• res：当前已经算好的结果。初始为 0。

接下来遍历字符串的每个字符：

遇到数字

if (Character.isDigit(ch)) {
    int value = ch - '0';
    while (i + 1 < length && Character.isDigit(s.charAt(i + 1))) {
        i++;
        value = value * 10 + s.charAt(i) - '0';
    }
    res = res + sign * value;
}

• 如果当前字符是数字，先把它转成整数（ch - '0'）。
• 然后看下一个字符是不是数字，如果是，就拼成多位数（比如 123 要拼成一百二十三）。
• 最后把这个数字乘以当前符号，加到结果 res 上。比如 sign=1 就加正数，sign=-1 就加负数。

遇到加号或减号

} else if (ch == '+') {
    sign = 1;
} else if (ch == '-') {
    sign = -1;
}

• 很简单，更新符号。注意：这个符号会影响它后面紧跟着的数字（或括号结果）。

遇到左括号

} else if (ch == '(') {
    stack.push(res);
    stack.push(sign);
    res = 0;
    sign = 1;
}

• 先把当前结果 res 压栈，再把当前符号 sign 压栈。注意顺序：先压结果，再压符号，这样弹出时先弹出符号。
• 然后重置 res = 0 和 sign = 1，开始计算括号里面的内容。

为什么压栈：因为括号里的结果算完后，要跟括号外面的结果结合。栈里存的就是“外面的结果”和“外面的符号”。

遇到右括号

} else if (ch == ')') {
    int formerSign = stack.pop();
    int formerRes = stack.pop();
    res = formerRes + formerSign * res;
}

• 弹出栈顶的两个元素：先弹出的是符号（因为后压栈），再弹出的是结果。