import math
class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        # operators = {
        #     '+': lambda x, y: x + y,
        #     '-': lambda x, y: x - y,
        #     '*': lambda x, y: x * y,
        #     '/': lambda x, y: x / y,
        # }
        # stack = [] # Space: O(n) 
        # for token in tokens: # Time: O(n)
        #     if token not in operators:
        #         stack.append(int(token))
        #     else:
        #         x = stack.pop(-2)
        #         y = stack.pop()
        #         stack.append(math.ceil(operators[token](x, y)))
        # return int(stack[-1])

        # Recursion Solution
        print(tokens)
        s = tokens[len(tokens) - 1]
        tokens.pop()
        if(s not in '+-/*'): return int(s)
        else:
            a = self.evalRPN(tokens)
            b = self.evalRPN(tokens)
            # print(a)
            # print(b)
            if(s == "+"): return a + b
            elif(s == "*"): return a * b
            elif(s == "-"): return b - a
            else: return int(float(b)/a)

obj = Solution()
print(obj.evalRPN(["2","1","+","3","*"])) # 9
print(obj.evalRPN(["4","13","5","/","+"])) # 6
# print(obj.evalRPN(["10","6","9","3","+","-11","*","/","*","17","+","5","+"])) # 22
# print(obj.evalRPN(["0","3","/"])) # 0
# print(obj.evalRPN(["3","11","+","5","-"])) # 9
# print(obj.evalRPN(["3","-4","+"])) # -1
# print(obj.evalRPN(["3","11","5","+","-"])) # -13