Evaluate Reverse Polish Notation

Reverse Polish Notation (RPN), also known as postfix notation, is a mathematical notation that avoids the use of parentheses. Instead, operators follow their operands. This challenge asks you to implement a function that evaluates an expression given in RPN format. This is a fundamental problem in compiler design and demonstrates stack-based computation.

Problem Description

You are given a list of tokens representing a Reverse Polish Notation (RPN) expression. The tokens can be either numbers (integers) or operators (+, -, *, /). Your task is to evaluate the expression and return the result.

What needs to be achieved:

• Parse the RPN expression represented as a list of tokens.
• Use a stack to store operands.
• When an operator is encountered, pop the necessary number of operands from the stack, perform the operation, and push the result back onto the stack.
• After processing all tokens, the final result should be the only element remaining on the stack.

Key Requirements:

• The input list will contain only valid RPN expressions.
• Division should truncate towards zero (e.g., 5 / 2 = 2).
• Handle potential errors gracefully (though the problem statement specifies valid input, consider how you would handle invalid input in a real-world scenario).

Expected Behavior:

The function should return an integer representing the result of the RPN expression.

Edge Cases to Consider:

• Empty input list (should return 0, or throw an error - clarify in your implementation).
• Single number in the input list (should return that number).
• Expressions with multiple operators and operands.
• Division by zero (though the problem states valid input, consider how you would handle this).

Examples

Example 1:

Input: [2, 1, "+", 3, "*"]
Output: 9
Explanation: 2 + 1 = 3.  3 * 3 = 9.

Example 2:

Input: [4, 13, 5, "/", "+"]
Output: 6
Explanation: 5 / 5 = 1.  4 + 1 = 5.

Example 3:

Input: [10, 6, 9, "3", "+", "-11", "*", "/", "*", 17, "+", 5, "+"]
Output: 22
Explanation: (10 * (6 / ((9 + 3) * -11))) + 17 + 5 = 22.  This demonstrates a more complex expression.

Constraints

• The input list will contain integers and strings representing operators.
• The number of tokens in the input list will be between 1 and 1000.
• The integers in the input list will be within the range of -1000 to 1000.
• The operators will be '+', '-', '*', and '/'.
• Performance: The solution should have a time complexity of O(n), where n is the number of tokens in the input list.

Notes

Consider using a stack data structure (e.g., a list used as a stack) to efficiently evaluate the expression. The key is to process the tokens from left to right, pushing operands onto the stack and performing operations when an operator is encountered. Remember to handle the order of operations correctly based on the postfix notation. Think about how you would represent the stack and how you would push and pop elements.