Evaluate Reverse Polish Notation

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 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. For example, tokens = ["2","1","+","3","*"], Output: 9, because ((2 + 1) * 3) = 9. As another example, tokens = ["4","13","5","/","+"], Output: 6 because (4 + (13 / 5)) = 6.

# Evaluate Reverse Polish Notation

## Problem Description

You are given an array of strings `tokens` that represents an arithmetic expression in Reverse Polish Notation (RPN).

Evaluate the expression and return an integer representing the value of the expression.

**Note:**

*   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 RPN.
*   The answer and all intermediate calculations can be represented in a 32-bit integer.

**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

## Brute Force Solution (Less Efficient)

A brute force solution would involve repeatedly scanning the tokens array for operators.  When an operator is found, perform the operation on the two preceding operands, replace the three tokens with the result, and repeat.  This is less efficient because of repeated scans and array modifications.

## Optimal Solution

The optimal solution uses a stack to store operands. When an operator is encountered, pop the top two operands from the stack, perform the operation, and push the result back onto the stack. At the end, the stack will contain the final result.

```python
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operators = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "*": lambda a, b: a * b,
            "/": lambda a, b: int(a / b)
        }

        for token in tokens:
            if token in operators:
                operand2 = stack.pop()
                operand1 = stack.pop()
                result = operators[token](operand1, operand2)
                stack.append(result)
            else:
                stack.append(int(token))

        return stack[0]

Big(O) Run-time Analysis

The run-time complexity is O(n), where n is the number of tokens in the input array. This is because each token is visited and processed exactly once.

Big(O) Space Usage Analysis

The space complexity is O(n) in the worst case, where n is the number of tokens. This occurs when the input expression contains only operands, and all operands are pushed onto the stack before any operators are encountered. In the average case, the space complexity will be less than O(n) because operators will cause operands to be popped off the stack.

Edge Cases

1. Empty Input: The problem statement specifies that 1 <= tokens.length <= 10^4, so we don't need to handle empty input. If we did, we would simply return 0.
2. Single Operand: If the input contains only one token, and it's an operand, the algorithm correctly returns the operand's value.
3. Large Numbers: The problem states that the answer and all intermediate calculations can be represented in a 32-bit integer. The provided code handles truncation towards zero for division, as required.
4. Negative Numbers: The code handles negative numbers correctly, as int() can parse negative integer strings.
5. Division by Zero: The problem states that there will not be any division by zero, so we don't need to handle this case.