In this problem, we are given an array of strings called tokens, which represents a valid arithmetic expression written in Reverse Polish Notation.

Reverse Polish Notation is also called postfix notation. In this format, the operator comes after the operands.

For example:

["1", "2", "+", "3", "*", "4", "-"]

This represents:

((1 + 2) * 3) - 4

So the output is:

5

Main Idea

The best way to solve this problem is by using a stack.

We process each token one by one:

• If the token is a number, push it into the stack.
• If the token is an operator, pop the last two numbers from the stack.
• Apply the operator.
• Push the result back into the stack.

At the end, the stack will contain only one value, which is the final answer.

Why Stack Works

Reverse Polish Notation naturally works with a stack because every operator uses the two most recent operands.

For example:

["1", "2", "+"]

We push 1, then push 2.

When we see +, we pop both numbers and calculate:

1 + 2 = 3

Then we push 3 back into the stack.

Code

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for c in tokens:
            if c == "+":
                stack.append(stack.pop() + stack.pop())

            elif c == "-":
                a = stack.pop()
                b = stack.pop()
                stack.append(b - a)

            elif c == "*":
                stack.append(stack.pop() * stack.pop())

            elif c == "/":
                a = stack.pop()
                b = stack.pop()
                stack.append(int(b / a))

            else:
                stack.append(int(c))

        return stack.pop()

Important Detail: Order Matters

For addition and multiplication, the order does not matter:

a + b == b + a
a * b == b * a

So we can directly pop twice.

But for subtraction and division, the order matters.

For example, if the stack has:

[5, 2]

And the operator is -, we should calculate:

5 - 2

The first popped value is 2, and the second popped value is 5.

That is why we write:

a = stack.pop()
b = stack.pop()
stack.append(b - a)

The same logic applies to division:

a = stack.pop()
b = stack.pop()
stack.append(int(b / a))

Division Truncates Toward Zero

The problem states that integer division should truncate toward zero.

In Python, using // is not always correct for negative numbers because it rounds down.

For example:

-3 // 2 == -2

But truncating toward zero should give:

-1

So we use:

int(b / a)

This correctly truncates toward zero.

Walkthrough

Input:

tokens = ["1", "2", "+", "3", "*", "4", "-"]

Steps:

Push 1        -> [1]
Push 2        -> [1, 2]
Apply +       -> [3]
Push 3        -> [3, 3]
Apply *       -> [9]
Push 4        -> [9, 4]
Apply -       -> [5]

Final answer:

5

Time and Space Complexity

Time Complexity

O(n)

We go through each token once.

Space Complexity

O(n)

In the worst case, we may store many numbers in the stack.

Final Thoughts

This problem is a great example of how useful stacks are when evaluating expressions. Since Reverse Polish Notation places operators after operands, a stack helps us easily keep track of the values needed for each operation.