解题思路逆波兰表达式后缀表达式天然适合用栈来求解遍历 tokens遇到数字压入栈遇到运算符从栈中弹出两个操作数先弹出的是右操作数后弹出的是左操作数计算后将结果压回栈遍历结束后栈中唯一的元素就是答案代码实现/** * param {string[]} tokens * return {number} */varevalRPNfunction(tokens){conststack[];constoperatorsnewSet([,-,*,/]);for(consttokenoftokens){if(!operators.has(token)){stack.push(Number(token));}else{constrightstack.pop();constleftstack.pop();letresult;switch(token){case:resultleftright;break;case-:resultleft-right;break;case*:resultleft*right;break;case/:// 向零截断resultMath.trunc(left/right);break;}stack.push(result);}}returnstack.pop();};关键点说明要点 说明操作数顺序 left - right 和 left / right 不能颠倒。第一个 pop() 是右操作数除法截断 JS 的 / 会得到小数要用 Math.trunc() 向零截断。不要用 | 0因为它在数值超过 32 位时会出错数字判断 用 Set 判断是否为运算符比 isNaN 更直观高效类型转换 token 是字符串需要 Number(token) 转成数字复杂度分析· 时间复杂度O(n)每个 token 只处理一次· 空间复杂度O(n)栈的深度示例验证输入: [2,1,,3,*] 过程: 2 → push 2 stack: [2] 1 → push 1 stack: [2, 1] → 213, push 3 stack: [3] 3 → push 3 stack: [3, 3] * → 3*39, push 9 stack: [9] 输出: 9输入: [4,13,5,/,] 过程: 5 和 13 弹出13/52.6 → trunc → 2 4 2 6 输出: 6
