演算法練習 力扣 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)