Evaluate Reverse Polish Notation (Stack)

To evaluate Reverse Polish Notation, I would use a standard stack-based approach because it naturally handles the last-in-first-out nature of nested operations. First, I initialize an empty stack to store integers. Then, I iterate through the input tokens array. If a token is a number, I push it onto the stack. If it is an operator, I pop the top two elements; crucially, the first popped element is the right operand and the second is the left operand, especially important for subtraction and division. I perform the calculation and push the result back onto the stack. For example, with input [3, 4, +], I push 3, push 4, then pop 4 and 3 to calculate 7, pushing 7 back. After processing all tokens, the final result remains at the top of the stack. I must ensure to handle edge cases like division by zero or invalid expressions if the problem statement allows, though typically we assume valid RPN. In terms of efficiency, this runs in O(n) time because we visit each token exactly once. The space complexity is O(n) in the worst case where all inputs are numbers before any operators appear. This approach aligns well with Spotify's focus on scalable, efficient backend services where memory usage matters.