This problem requires evaluating a sequence of tokens representing a Reverse Polish Notation expression. Use a stack to push numbers and apply operators in order. Each operator pops the last two operands, computes the result, and pushes it back, ensuring correct handling of order and integer division for accuracy.
Problem Statement
You are given an array of strings, tokens, representing an arithmetic expression in Reverse Polish Notation. Each token is either an integer or one of the operators '+', '-', '*', or '/'. Evaluate the expression and return the integer result.
Ensure your solution correctly processes all tokens using a stack to manage intermediate values. Handle integer division by truncating toward zero and consider edge cases where operators may appear consecutively or numbers are negative.
Examples
Example 1
Input: tokens = ["2","1","+","3","*"]
Output: 9
((2 + 1) * 3) = 9
Example 2
Input: tokens = ["4","13","5","/","+"]
Output: 6
(4 + (13 / 5)) = 6
Example 3
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
((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
Constraints
- 1 <= tokens.length <= 104
- tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Solution Approach
Stack-Based Evaluation
Initialize an empty stack. Iterate through each token: if it is a number, push it onto the stack; if it is an operator, pop the last two numbers, apply the operator, and push the result back. Continue until all tokens are processed, then return the final value from the stack.
Integer Division Handling
For the division operator '/', ensure the result truncates toward zero rather than flooring. Convert the operands to integers before division, and handle negative values carefully to match problem requirements and avoid unexpected results.
Edge Case Considerations
Check for expressions with a single number, consecutive operators, or negative numbers. Avoid stack underflow by confirming two operands are available before applying an operator, and validate input length constraints to prevent runtime errors.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) because each token is processed exactly once. Space complexity is O(n) in the worst case due to the stack holding all operands before operators reduce them.
What Interviewers Usually Probe
- Asks about stack implementation details and handling integer division.
- Questions around edge cases with negative numbers or consecutive operators.
- Wants reasoning for why a stack is preferred over direct array manipulation.
Common Pitfalls or Variants
Common pitfalls
- Using float division instead of truncating toward zero, causing wrong integer results.
- Popping operands in the wrong order, reversing the operation result.
- Not handling edge cases like a single token or negative numbers correctly.
Follow-up variants
- Evaluate expressions with additional operators like modulus or exponentiation.
- Handle Reverse Polish Notation with variables replaced by lookup values.
- Compute expressions using a recursive approach instead of an explicit stack.
How GhostInterview Helps
- GhostInterview guides through stack operations step by step, showing push and pop sequences for each token.
- It highlights division truncation issues and helps ensure integer results match problem expectations.
- The solver points out edge cases and intermediate stack states to prevent common runtime errors.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the best approach for Evaluate Reverse Polish Notation?
Use a stack to push numbers and apply operators in order, popping two operands for each operator and pushing the result.
How should integer division be handled in this problem?
Division must truncate toward zero. Convert operands to integers before dividing and handle negative numbers carefully.
Can the input contain negative numbers or single-token expressions?
Yes, the solution must correctly handle negative numbers and expressions consisting of a single numeric token.
What is the time and space complexity?
Time complexity is O(n) because each token is processed once. Space complexity is O(n) due to the stack storing operands.
Why is a stack necessary for this pattern?
A stack efficiently manages the state of operands, allowing operators to access the most recent numbers in Reverse Polish Notation order.
Need direct help with Evaluate Reverse Polish Notation instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Evaluate Reverse Polish Notation from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the maximum number of points on a straight line in a 2D plane using array scanning and hash lookup.
Open problem page#189 Rotate ArrayRotate Array challenges you to shift elements right by k steps using precise two-pointer scanning and invariant tracking techniques.
Open problem page#204 Count PrimesCount all prime numbers less than a given integer n using efficient array and math-based enumeration techniques.
Open problem page