leetcode/150_polish_notation.py at main · motdam/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
"""
Topics
- stack
"""

from operator import add, sub, mul, truediv
from typing import List

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operators = {"+": add, "-":sub, "*":mul, "/":truediv}
        stack = []

        if len(tokens) == 1:

            if tokens[0] in operators:
                return 0
            else:
                return int(tokens[0])

        for i, token in enumerate(tokens):
            if not token in operators:
                stack.append(int(token))
            else:
                a, b = stack.pop(), stack.pop()
                total = int(operators[token](b, a))
                stack.append(total)
        return int(total)

solution = Solution()
print(solution.evalRPN(["18"])) # shoulzd be 6
print(solution.evalRPN(["4","13","5","/","+"])) # shoulzd be 6
print(solution.evalRPN(tokens=[
    "10","6","9","3","+","-11","*","/","*","17","+","5","+"
])) # should be 22