# LeetCode Medium 150. Evaluate Reverse Polish Notation

tags: leetcode

問題

• Explore
• Problems

アイデア

｢ポーランド記法で記述された数式を評価しろ｣という問題です｡

数式はいつも正しく解くことが出来るそうで､特にエラー処理についか考える必要はなさそうです｡

解法

そのままやるだけですが､プログラミング言語によって負の値での除算の結果が変わるのでそこは注意しましょう｡

計算量

配列の大きさを$N$とします｡

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Python

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        results = []
        for token in tokens:
            try:
                results.append(int(token))
            except ValueError:
                if len(results) > 1:
                    a = results.pop()
                    b = results.pop()
                    if token == "+":
                        results.append(a + b)
                    if token == "-":
                        results.append(b - a)
                    if token == "*":
                        results.append(a * b)
                    if token == "/":
                        results.append(int(float(b) / a))
                else:
                    raise Exception("Error: The list size is not enough.")
        return results[-1]