LeetCode 224：基本计算器

技术文档

LeetCode 224：基本计算器

问题本质：处理嵌套表达式的计算逻辑

给定仅包含 加减号、括号、数字和空格 的表达式，要求手动实现计算器（禁止使用 eval）。核心挑战是：

处理 多位数（如 \"123+45\"）；
处理 括号嵌套（如 \"(1+(2-3))\"）；
高效维护计算顺序（括号改变运算优先级）。

核心思路：栈 + 状态维护

利用栈保存括号外的计算状态（包括当前结果和符号），遍历过程中动态维护：

res：当前已计算的结果；
num：当前解析的数字（处理多位数）；
sign：当前数字/表达式的符号（+1 或 -1）。

通过栈，我们可以在遇到括号时“暂停”外部计算，进入括号内的上下文；遇到右括号时，“恢复”外部状态并合并结果。

算法步骤详解

1. 变量初始化

Stack<Integer> stack = new Stack<>(); // 保存括号外的 (res, sign)int res = 0; // 当前计算结果（括号内或外部的中间结果）int num = 0; // 当前解析的数字（处理多位数，如 \"123\"）int sign = 1; // 当前符号：+1 表示加，-1 表示减

2. 遍历字符，分情况处理

遍历表达式的每个字符，根据字符类型执行不同逻辑：

（1）数字：累积多位数

若字符是数字，需处理多位数（如 \"123\" 需解析为 123）：

if (Character.isDigit(c)) { num = num * 10 + (c - \'0\'); // 逐位构建数字}

（2）运算符 `+`/`-`：计算当前数字，更新符号

遇到运算符时，先将之前累积的数字按当前符号计入 res，再更新符号：

else if (c == \'+\' || c == \'-\') { res += sign * num; // 先计算：将当前num按sign加到res num = 0; // 重置num，准备解析下一个数字 sign = (c == \'+\') ? 1 : -1; // 更新符号}

（3）左括号 `(`：保存当前状态，进入新上下文

遇到左括号时，当前的 res 和 sign 是括号外的状态，需要保存到栈中，然后重置 res 和 sign，处理括号内的子表达式：

else if (c == \'(\') { stack.push(res); // 保存括号外的结果 stack.push(sign); // 保存括号外的符号 res = 0;  // 重置res，开始计算括号内的结果 sign = 1; // 重置符号（括号内默认是正）}

（4）右括号 `)`：合并括号内结果，恢复外部状态

遇到右括号时，括号内的计算已完成（res 是括号内的结果），需：

计算括号内的最后一个数字（若有）；
从栈中弹出括号外的符号和括号外的结果，合并得到最终结果。

else if (c == \')\') { res += sign * num; // 计算括号内的最后一个数字 num = 0;  // 重置num int prevSign = stack.pop(); // 弹出括号外的符号 int prevRes = stack.pop(); // 弹出括号外的结果 res = prevRes + prevSign * res; // 合并：括号外结果 + 符号×括号内结果}

（5）空格：直接跳过

else if (c == \' \') { continue;}

3. 处理剩余数字（遍历结束后）

遍历结束后，可能存在未计算的数字（如表达式末尾的数字），需补充计算：

res += sign * num;

示例拆解：以 `\"(1+(4+5+2)-3)+(6+8)\"` 为例

目标：计算结果 23，分步解析如下：

字符操作 res num sign stack 说明 ( 压入 res=0、sign=1；重置 res=0、sign=1 0 0 1 [0, 1] 进入括号内，保存外部状态 1 累积数字：num=1 0 1 1 [0, 1] + res += 1×1 → res=1；num=0；sign=1 1 0 1 [0, 1] 计算当前数字 ( 压入 res=1、sign=1；重置 res=0、sign=1 0 0 1 [0, 1, 1, 1] 进入内层括号 4 累积数字：num=4 0 4 1 [0, 1, 1, 1] + res += 1×4 → res=4；num=0；sign=1 4 0 1 [0, 1, 1, 1] 5 累积数字：num=5 4 5 1 [0, 1, 1, 1] + res += 1×5 → res=9；num=0；sign=1 9 0 1 [0, 1, 1, 1] 2 累积数字：num=2 9 2 1 [0, 1, 1, 1] ) res += 1×2 → res=11；num=0；弹出 prevSign=1、prevRes=1；res=1+1×11=12 12 0 1 [0, 1] 内层括号计算完成 - res += 1×12 → res=12；num=0；sign=-1 12 0 -1 [0, 1] 处理减号 3 累积数字：num=3 12 3 -1 [0, 1] ) res += (-1)×3 → res=9；num=0；弹出 prevSign=1、prevRes=0；res=0+1×9=9 9 0 1 [] 外层括号计算完成 + res += 1×9 → res=9；num=0；sign=1 9 0 1 [] 处理加号 ( 压入 res=9、sign=1；重置 res=0、sign=1 0 0 1 [9, 1] 进入新括号 6 累积数字：num=6 0 6 1 [9, 1] + res += 1×6 → res=6；num=0；sign=1 6 0 1 [9, 1] 8 累积数字：num=8 6 8 1 [9, 1] ) res += 1×8 → res=14；num=0；弹出 prevSign=1、prevRes=9；res=9+1×14=23 23 0 1 [] 最后括号计算完成结束 res += 1×0 → res=23（无剩余数字，实际此处num为0，不影响） 23 0 1 [] 最终结果

完整代码（Java）

import java.util.Stack;class Solution { public int calculate(String s) { Stack<Integer> stack = new Stack<>(); // 保存括号外的 (res, sign) int res = 0; // 当前计算结果 int num = 0; // 当前解析的数字（处理多位数） int sign = 1; // 当前符号：+1 表示加，-1 表示减 for (char c : s.toCharArray()) { if (Character.isDigit(c)) { // 处理多位数：逐位构建数字 num = num * 10 + (c - \'0\'); } else if (c == \'+\' || c == \'-\') { // 计算当前数字，更新符号 res += sign * num; num = 0; sign = (c == \'+\') ? 1 : -1; } else if (c == \'(\') { // 保存当前状态，进入括号内计算 stack.push(res); // 括号外的结果 stack.push(sign); // 括号外的符号 res = 0;  // 重置res，计算括号内 sign = 1; // 重置符号 } else if (c == \')\') { // 计算括号内的最后一个数字，合并结果 res += sign * num; num = 0; int prevSign = stack.pop(); // 括号外的符号 int prevRes = stack.pop(); // 括号外的结果 res = prevRes + prevSign * res; } else if (c == \' \') { // 跳过空格 continue; } } // 处理遍历结束后剩余的数字 res += sign * num; return res; }}

复杂度分析

时间复杂度：O(n)，每个字符仅处理一次（包括数字的累积，本质是逐位处理）。
空间复杂度：O(n)，栈的最大深度为括号的嵌套层数（最坏情况如 ((((...)))))，深度为 n）。

关键设计思想

符号化处理：将加减运算转化为 符号 sign 的切换，统一处理数字的正负，简化逻辑。
栈的状态保存：括号的嵌套本质是上下文的嵌套，栈能高效保存和恢复上下文（外部的 res 和 sign）。
多位数解析：通过 num = num * 10 + (c - \'0\') 逐位构建数字，避免字符串截取的开销。

LeetCode 224：基本计算器