[!info] related notes 算法面试题型 MOC 栈

逆波兰表达式求值

题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/

题型判断

这是表达式求值栈的基础题。

后缀表达式的特点是：

• 数字出现时，先记下来
• 运算符出现时，立刻用前面最近的两个数字计算

所以天然适合用栈保存操作数。

核心思路

• 遇到数字：入栈
• 遇到运算符：弹出两个数 b 和 a
• 计算 a op b
• 把结果再压回栈

最后栈里只剩一个结果。

易错点

• 顺序不能写反：一定是先弹 b，再弹 a
• 除法要按题意向 0 取整

JavaScript

var evalRPN = function(tokens) {
    const stack = [];

    for (const token of tokens) {
        if (token === '+' || token === '-' || token === '*' || token === '/') {
            const b = stack.pop();
            const a = stack.pop();
            let res = 0;

            if (token === '+') res = a + b;
            if (token === '-') res = a - b;
            if (token === '*') res = a * b;
            if (token === '/') res = Math.trunc(a / b);

            stack.push(res);
        } else {
            stack.push(Number(token));
        }
    }

    return stack[0];
};

一句话总结

遇到运算符时，最近入栈的两个数字正好就是当前这一步要计算的操作数。