算法练习 力扣 150. Evaluate Reverse Polish Notation

feellikelearning September 7, 2021 0 Comments

问题总结

这题比较简单，如果学过computer architecture，这个Reverse Polish Notation (RPN)基本就是个stack machine。很像汇编语言。用stack就可以解决。

坑

除法要求

that division between two integers should truncate toward zero.

测试数据里面有负数, python里面整数除法结果如果是小数，约成整数后是往小的方向约的。比如-0.4会变成-1，题目要求往0约，也就是-0.4变成0。用int(a/b)可解决。一个冷门知识。

Python解法

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        ops = {'+', '-', '*', '/'}
        for token in tokens:
            if token not in ops:
                stack.append(int(token))
            else:
                op = token
                num2 = stack.pop()
                num1 = stack.pop()
                res = self.evalSimple(num1, num2, op)
                stack.append(res)
        
        return stack.pop()
                
    def evalSimple(self, num1, num2, op):
        if op == '+':
            return num1 + num2
        elif op == '-':
            return num1 - num2
        elif op == '*':
            return num1 * num2
        elif op == '/':
            return int(num1 / num2)