「亚麻 + 高频」看完世界杯接着刷 150 ～ 验证 Reverse Polish notation

基本信息

• 题号：150
• 题厂：亚麻
• 难度系数：中

已知一个数组，根据规则计算结果……

例如 tokens = ["2","1","+","3","*"]
返回 9：((2 + 1) * 3) = 9

解题思路

• Reverse Polish Notation 貌似是一道有维基百科的学术问题……Reverse Polish Notation 前世今生是啥不重要，关键这里把题做出来
• 懂不懂 Reverse Polish Notation 没关系，看到一个数组，在哪 pop 又 加减乘除地，有没有想起一些似曾相识的题目？？？是的，就是我们亲爱的「stack」
• 于是本题转换到数据机构层面后，就是如何引入「stack」解决问题。
• 研究和安插「stack」需要研究已知数组的 pattern——研究 pattern 发现规律：当遇到「+」「-」「*」「/」后才做一次运算，要运算的对象是放在「stack」的最后两个。

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        # 做遍历时，遇上加减乘除，从 stack pop 2 元素运算；如果不是加减乘除，说明遇上了数字，直接存入 stack
        # 做完加减乘除还要要运算后的结果再重新放回 stack 用于下一次运算
        for item in tokens:
            if item == "+":
                stack.append(stack.pop() + stack.pop())
            elif item == "-":
                a, b = stack.pop(), stack.pop()
                stack.append(b - a)
            elif item == "*":
                stack.append(stack.pop() * stack.pop())
            elif item == "/":
                a, b = stack.pop(), stack.pop()
                # python int() round towards 0
                stack.append(int(b / a))
            else:
                stack.append(int(item))
        
        # 遍历结束后，stack 一定只剩一个元素，pop 返回即可        
        return stack.pop()

Constraints

• 1 <= tokens.length <= 104
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

考试前可以向考官讨论，数组是有效的——不会出现遇上运算符号但 stack 内数字元素不足 2 的情况

测试

• 加减乘除分别测试一次
• 出现多重运算时
• 运算符号变化位置时
• ……

总结

• 不知道 stack 和刷题，是不可能做出这道题的——考试遇上注定歇菜
• 做了这么多 stack 题，发现简单 stack 就适合解决这些问题，什么配对验证之类的……