Evaluate Reverse Polish Notation

The problem description can be found in LeetCode.

Approach

As for Valid Parentheses, a Stack can be used used to keep track of intermediate results.

In fact, as soon as we encounter an operator, we can assume that the stack contains at least 2 elements (based on Reverse Polish Notation definition) and proceed to apply the operator to the two numbers. The result will be at the top of the stack.

Solution

from typing import List


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

        for token in tokens:
            if token in ops:
                assert len(stack) > 1, f"{stack} ({len(stack)})"

                num2 = stack.pop()
                num1 = stack.pop()
                if token == "+":
                    stack.append(num1 + num2)
                elif token == "-":
                    stack.append(num1 - num2)
                elif token == "*":
                    stack.append(num1 * num2)
                elif token == "/":
                    stack.append(int(num1 / num2))
            else:
                stack.append(int(token))

        assert len(stack) == 1, f"{stack} ({len(stack)})"

        return stack[-1]

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the tokens list.