Practice/Google/Leetcode 150. Evaluate Reverse Polish Notation

Leetcode 150. Evaluate Reverse Polish Notation

CodingOptional

Problem

You are given an array of strings representing an arithmetic expression written in postfix notation (also known as Reverse Polish Notation). In postfix notation, operators come after their operands.

Your task is to evaluate this expression and return the resulting integer value.

The expression will contain:

• Integer operands (which may be negative)
• Four binary operators: + (addition), - (subtraction), * (multiplication), / (division)

For division, you must truncate the result toward zero (not floor division). This means -3 / 2 should equal -1, not -2.

Requirements

1. Process the tokens from left to right
2. When you encounter a number, store it for later use
3. When you encounter an operator, apply it to the two most recent numbers
4. Division must truncate toward zero (use integer division that rounds toward zero)
5. Return the final computed value as an integer
6. The input expression is guaranteed to be valid and will always have a result

Constraints

• 1 ≤ tokens.length ≤ 10⁴
• Each token is either an operator ("+", "-", "*", "/") or an integer in the range [-200, 200]
• The expression is guaranteed to be a valid postfix expression
• All intermediate results will fit in a 32-bit integer
• Time complexity should be O(n) where n is the number of tokens
• Space complexity should be O(n) in the worst case

Examples

Example 1:

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

• Push 2 onto the stack
• Push 1 onto the stack
• Apply +: pop 1 and 2, compute 2 + 1 = 3, push 3
• Push 3 onto the stack
• Apply *: pop 3 and 3, compute 3 * 3 = 9, push 9
• Result: 9 `

Example 2:

` Input: tokens = ["4", "13", "5", "/", "+"] Output: 6 Explanation:

• Push 4, 13, 5
• Apply /: pop 5 and 13, compute 13 / 5 = 2 (integer division), push 2
• Apply +: pop 2 and 4, compute 4 + 2 = 6, push 6
• Result: 6 `

Example 3:

Input: tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: This evaluates to ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22