LeetCode题解:150. 逆波兰表达式求值,栈,JavaScript,详细注释
Opened this issue · 0 comments
chencl1986 commented
原题链接:150. 逆波兰表达式求值
解题思路:
-
逆波兰表达式的计算方式,是先从左到右查找待计算的数字,当遇到算符后,将临近的两个数字取出进行相应计算,并将计算结果替换掉原数字和算符。
-
因此,这是一种先入后出的计算方式,可以使用栈解决:
- 遍历
tokens
,将数字都入栈。 - 如果遇到算符,从栈中取出两个数字进行相应计算。
- 算式中两个元素的顺序,总是
stack[stack.length - 2]
在前,stack[stack.length - 1]
在后。 - 将计算结果入栈,等待下一次计算。
- 完成所有计算后,栈中只有一个元素,即为最终结果。
- 遍历
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function (tokens) {
let stack = []; // 使用栈存储运算结果
// 从左到右遍历token,根据符号进行相应运算
for (const token of tokens) {
// 遇到算符,将栈顶两个元素弹出进行相应计算
if (token === '+' || token === '-' || token === '*' || token === '/') {
// 弹出两个元素,需要转换成数字运算
const num1 = Number(stack.pop());
const num2 = Number(stack.pop());
// 进行相应的运算,并将结果存入栈,等待下一次运算
// 由于减法或除法,都是将后一个元素,作为被减数或被除数进行运算
// 因此书写顺序统一num2在前,num1在后
switch (token) {
case '+':
stack.push(num2 + num1);
break;
case '-':
stack.push(num2 - num1);
break;
case '*':
stack.push(num2 * num1);
break;
case '/':
// 缓存除法的商
const quotient = num2 / num1;
// 只有整数可以参与运算,正数向下取整,负数向上取整
stack.push(quotient > 0 ? Math.floor(quotient) : Math.ceil(quotient));
break;
default:
break;
}
} else {
// 如果是数字,则存入栈,等待计算
stack.push(token);
}
}
// 完成计算后,栈中只有一个元素,即为最终结果
return stack.pop();
};