[!info] related notes 算法面试题型 MOC 栈 逆波兰表达式求值

基本计算器

题目链接：https://leetcode.cn/problems/basic-calculator/

题型判断

这是表达式求值栈的进阶题。

和逆波兰表达式不同，这里是中缀表达式，并且带括号。

所以关键不是单纯维护数字栈，而是维护：

• 当前层已经算到哪一步
• 进入括号前的结果
• 进入括号前的符号

核心思路

遍历字符串，维护三个变量：

• res：当前层累计结果
• num：当前正在读取的数字
• sign：当前数字前面的符号，取 1 或 -1

再额外用一个栈保存括号外的上下文。

处理逻辑：

• 遇到数字：持续组装 num
• 遇到 + / -：先把前一个数字结算进 res，再更新 sign
• 遇到 (：把当前 res 和 sign 压栈，进入新一层
• 遇到 )：先结算当前层，再和括号外结果合并

为什么这里适合用栈

因为括号意味着“进入一层新上下文”，而离开括号时又要恢复上一层上下文。

这种“进入 / 返回”的过程，本质上就是栈。

JavaScript

var calculate = function(s) {
    const stack = [];
    let res = 0;
    let num = 0;
    let sign = 1;

    for (const ch of s) {
        if (ch >= '0' && ch <= '9') {
            num = num * 10 + Number(ch);
        } else if (ch === '+') {
            res += sign * num;
            num = 0;
            sign = 1;
        } else if (ch === '-') {
            res += sign * num;
            num = 0;
            sign = -1;
        } else if (ch === '(') {
            stack.push(res);
            stack.push(sign);
            res = 0;
            num = 0;
            sign = 1;
        } else if (ch === ')') {
            res += sign * num;
            num = 0;
            res *= stack.pop();
            res += stack.pop();
        }
    }

    res += sign * num;
    return res;
};

易错点

• 别忘了遍历结束后，还要把最后一个 num 加进 res
• ( 之前的 res 和 sign 都要保存，不然括号外上下文会丢
• 这题有空格，直接跳过即可

一句话总结

括号不是局部重新算一遍那么简单，而是“保存旧上下文，进入新上下文，出来后再恢复旧上下文”。