# Make a calculator using Reverse Polish Notation. Use recursion.
# The Reverse Polish syntax completely removes the need for parentheses.
#
# Syntax examples:
# "3 + 2" -> ["3", "2", "+"]
# "3 * 4 + 2" -> ["3", "4", "*", "2", "+"]
# "3 * (4 + 2)" -> ["3", "4", "2", "+", "*"]
#
# Example for how to evaluate ["3", "4", "2", "+", "*"]:
# Start with "4 2 +" -> "6"
# Then "3 6 *" -> "18"
# Start with the "innermost" expression and work backwards (this is the recursion part)
#
# For help, email me@bchen.dev

# Sample solution below

# Facts:
# The last element of the list must always be an operator; otherwise there is only one element

def rpn(expression: list[str]) -> int:
    operators = "+-*/"

    def eval(expression: list[str]) -> tuple[int, int]:
        """
        Evaluate RPN and return an index value pointing to the first token in the expression.
        """
        for i in range(len(expression) - 1, -1, -1):
            token = expression[i]

            if token in operators:
                right, right_token_index = eval(expression[:i])

                # for left, we need the index of the token that comes after right
                left, left_token_index = eval(expression[:right_token_index])

                if token == "+":
                    return left + right, left_token_index
                elif token == "-":
                    return left - right, left_token_index
                elif token == "*":
                    return left * right, left_token_index
                else:
                    return int(left / right), left_token_index
            else:
                # evaluate as a literal
                literal = int(token)
                return literal, i

        return (0, 0)
    
    return eval(expression)[0]


# The following test cases should pass (please copy this into your code):
tests = [
    (["3", "2", "+"], 5),
    (["3", "4", "*"], 12),
    (["3", "4", "2", "+", "*"], 18),
    ([], 0),
    (["50", "2", "/"], 25),
    (["5", "2", "/"], 2),  # for division, cast to int using int(num)
    (["5", "4", "3", "-", "*"], 5),
    (["5", "4", "6", "2", "10", "+", "*", "-", "-"], 73),
    (["3", "2", "+", "5", "*"], 25)
]
for case in tests:
    result = rpn(case[0])
    expected = case[1]
    if result == expected:
        print(f"PASS: expected {expected}, got {result} for {case[0]}")
    else:
        print(f"FAIL: expected {expected}, got {result} for {case[0]}")