Solutions

# Use a stack, push numbers, pop and compute when encountering an operator.
# stack

# Stack: O(n) time, O(n) space
def eval_rpn(tokens: list[int]):
    stack = []
    for t in tokens:
        if t == '+':
            stack.append(stack.pop() + stack.pop())
        elif t == '-':
            op1, op2 = stack.pop(), stack.pop()
            stack.append(op2 - op1)
        elif t == '*':
            stack.append(stack.pop() * stack.pop())
        elif t == '/':
            op1, op2 = stack.pop(), stack.pop()
            stack.append(int(op2 / op1))
        else:
            stack.append(int(t))

    return stack[0]


# DFS, recursion: O(n) time, O(n) space
def eval_rpn(self, tokens: list[str]) -> int:
    def dfs():
        token = tokens.pop()
        if token not in "+-*/":
            return int(token)

        right = dfs()
        left = dfs()

        if token == '+':
            return left + right
        elif token == '-':
            return left - right
        elif token == '*':
            return left * right
        elif token == '/':
            return int(left / right)

    return dfs()