Problem Statement

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

Additional information

• 1 <= tokens.length <= 10^4
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Example 1:

Input: tokens = ["2","1","+","3","*"]

Output: 9

Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]

Output: 6

Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

Output: 22

Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Stack (Optimal)

Intuition
Reverse Polish Notation (also known as Postfix Notation) is designed to be easily evaluated by a computer using a stack. The rule is simple: when we encounter a number, we push it onto the stack. When we encounter an operator, we pop the top two numbers from the stack, perform the operation, and push the result back.

Algorithm

1. Initialize an empty stack.
2. Iterate through each token t in the input list.
3. If t is an operator (+, -, *, /):

• Pop the top element (this is the second operand, b).
• Pop the next element (this is the first operand, a).
• Perform the operation: a op b.
• Crucial Note for Python: For division, standard // behaves like "floor division" (rounds down towards negative infinity). The problem requires "truncation towards zero". Use int(a / b) to achieve this.
• Push the result back onto the stack.

4. If t is a number, convert it to an integer and push it onto the stack.
5. After processing all tokens, the stack will contain exactly one element. Return it.

def eval_rpn(tokens: list[str]) -> int:
    stack = []
    
    for t in tokens:
        if t == "+":
            stack.append(stack.pop() + stack.pop())
        elif t == "-":
            a, b = stack.pop(), stack.pop()
            stack.append(b - a)
        elif t == "*":
            stack.append(stack.pop() * stack.pop())
        elif t == "/":
            a, b = stack.pop(), stack.pop()
            # Truncate towards zero using int() casting
            stack.append(int(b / a))
        else:
            stack.append(int(t))
            
    return stack[0]

Time & Space Complexity

• Time complexity: O(n)

• Reason: We iterate through the tokens exactly once. Each push and pop operation takes O(1).

• Space complexity: O(n)

• Reason: In the worst case (e.g., 1 2 3 4 + + +), the stack can grow to hold O(n) numbers.