栈
解题思路
如果遇到操作数，则将操作数入栈；
如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈；
复杂度
-
时间复杂度：
O(n)，其中 n 是数组 tokens 的长度，需要遍历数组 tokens 一次，计算逆波兰表达式的值； -
空间复杂度：
O(n)，其中 n 是数组 tokens 的长度，使用栈存储计算过程中的数，栈内元素个数不会超过逆波兰表达式的长度；
代码实现
var evalRPN = function (tokens) {
const stack = [];
const calc = {
'+': (a, b) => Number(a) + Number(b),
'-': (a, b) => Number(b) - Number(a),
'*': (a, b) => Number(a) * Number(b),
'/': (a, b) => (Number(b) / Number(a)) | 0, // | 0 直接去掉正负数小数点后面的
};
for (const item of tokens) {
if (item in calc) {
stack.push(calc[item](stack.pop(), stack.pop()));
} else {
stack.push(item);
}
}
return stack.pop();
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 889. 根据前序和后序遍历构造二叉树
上一篇
评论
