LeetCode-150.逆波兰表达式求值

题目详解

相关链接

• 代码随想录

思路

• 遍历tokens：
  • 如果遇到数字入栈
  • 如果遇到运算符，连续出栈两个数字进行运算，再将运算结果入栈用于后续计算

看完代码随想录之后的想法

• get了二进制取整小tip

实现过程中遇到的困难

• 出栈两次得到的两个数字顺序与运算顺序时相反的
• 除法取整时需要处理一下

代码

TypeScript

function evalRPN(tokens: string[]): number {
  const stack: number[] = []
  // 注意调用时传入的两个数字是依次出栈得到的，顺序是反的
  const map = {
    '+': (a: number, b: number) => b + a,
    '-': (a: number, b: number) => b - a,
    '*': (a: number, b: number) => b * a,
    '/': (a: number, b: number) => (b / a) | 0,
  }
  for (const c of tokens) {
    if (c in map) stack.push(map[c](stack.pop(), stack.pop()))
    else stack.push(+c)
  }
  return stack[0]
}

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

收获