逆波兰表达式求值 (opens new window)

Tip: 除号取整注意考虑正负

• 难度：Medium
• 标签：栈

刷题思路

• [x] 栈
• [ ] xx

方法 1 栈

• 复杂度：
  • 时间 O(n), 一次遍历.
  • 空间 O(n), stack空间 O(n).

var evalRPN = function(tokens) {
    const set = new Set(['+', '-', '*', '/'])
    const stack = []
    tokens.forEach(token => {
        if (set.has(token)) {
            const [right, left] = [stack.pop(), stack.pop()]
            let tmp = 0
            if (token === '+') tmp = left + right
            else if (token === '-') tmp = left - right
            else if (token === '*') tmp = left * right
            else if (token === '/') {
                tmp = left / right
                tmp = tmp > 0 ? Math.floor(tmp) : -Math.floor(-tmp)
            }
            stack.push(tmp)
        } else {
            stack.push(Number(token))
        }
    })
    return stack.pop()
};

方法 2

• 复杂度：
  • 时间 O()
  • 空间 O()

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~