逆波兰表达式求值-150
sl1673495 opened this issue · 0 comments
sl1673495 commented
150.逆波兰表达式求值
根据逆波兰表示法,求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1:
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
示例 2:
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6
https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
思路
提前声明好运算符对应的运算函数,当遇到数字时就放进栈中,遇到运算符,就 pop
出栈中的两个数据,对它们使用运算函数,把结果继续放入栈中即可。
运算到最后,栈中剩下的唯一元素就是最后的结果。
/**
* @param {string[]} tokens
* @return {number}
*/
let opMap = {
"+": (a, b) => b + a,
"-": (a, b) => b - a,
"*": (a, b) => b * a,
"/": (a, b) => parseInt(b / a, 10),
}
let evalRPN = function (tokens) {
let stack = []
for (let token of tokens) {
let op = opMap[token]
if (op) {
let a = parseInt(stack.pop())
let b = parseInt(stack.pop())
let res = op(a, b)
stack.push(res)
} else {
stack.push(token)
}
}
return stack[0]
}