Evaluate Reverse Polish Notation

📋

Problem

Imagine you are building a calculator app that only accepts expressions in Reverse Polish Notation (RPN), a postfix notation used in some calculators and compilers. You need to evaluate these expressions efficiently and correctly.

Given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation, evaluate the expression and return the result as an integer. Valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. Division between two integers should truncate toward zero.

1 ≤ tokens.length ≤ 10^5tokens[i] is either an operator: '+', '-', '*', or '/', or an integer in string formatThe given RPN expression is always valid

Edge cases: Single operand only → returns the operand itselfDivision resulting in negative number → truncates toward zeroLarge number of tokens → performance must be efficient

</>

IDE

def evalRPN(tokens: list[str]) -> int:public int evalRPN(String[] tokens)int evalRPN(vector<string>& tokens)function evalRPN(tokens)

def evalRPN(tokens):
    # Write your solution here
    pass

class Solution {
    public int evalRPN(String[] tokens) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
#include <string>
using namespace std;

int evalRPN(vector<string>& tokens) {
    // Write your solution here
    return 0;
}

function evalRPN(tokens) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Wrong integer division result (floor instead of truncate)Using floor division (e.g., // in Python) instead of truncation toward zero.✅ Replace floor division with int(left / right) to truncate toward zero.

Wrong: Incorrect result due to reversed operand orderPopping left operand before right operand from stack when applying operator.✅ Pop right operand first, then left operand before applying operator.

Wrong: Fails on single operand inputCode expects at least one operator and does not handle single token input.✅ If tokens length is 1, return int(tokens[0]) immediately.

Wrong: Timeout on large inputUsing recursive or exponential approach instead of iterative stack evaluation.✅ Implement iterative stack-based evaluation with O(n) time complexity.

✓

Test Cases

Focus on handling minimal inputs and division edge cases correctly.

Check operator application order and division truncation carefully.

Optimize your solution to run in linear time using a stack.

t1_01basic

Input["2","1","+","3","*"]

Expected9

⏱ Performance - must finish in 2000ms

((2 + 1) * 3) = 9

💡 Use a stack to store operands and apply operators as they appear.

💡 Push numbers onto the stack; when an operator appears, pop two operands and apply it.

💡 After processing all tokens, the stack's top is the final result.

Why it failed: Incorrect output means operator application or stack order is wrong. Fix by ensuring you pop right operand first, then left operand, then apply operator.

✓ Correctly evaluates the canonical example using stack-based evaluation.

t1_02basic

Input["4","13","5","/","+"]

Expected6

⏱ Performance - must finish in 2000ms

13 / 5 = 2 (truncate toward zero), then 4 + 2 = 6

💡 Remember division truncates toward zero, not floor division.

💡 Pop operands in correct order: right operand first, then left operand.

💡 Use int(left / right) in Python or equivalent to truncate toward zero.

Why it failed: Wrong division result likely due to floor division or operand order reversed. Fix by using truncation toward zero and correct operand order.

✓ Handles division truncation and operator precedence correctly.

t2_01edge

Input["42"]

Expected42

⏱ Performance - must finish in 2000ms

Single operand only returns the operand itself

💡 If only one token and it's a number, return it directly.

💡 No operators means no stack operations needed.

💡 Check for single token edge case before processing.

Why it failed: Failing this means code expects at least one operator. Fix by returning int(token) if tokens length is 1.

✓ Correctly handles single operand input.

t2_02edge

Input["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

Expected22

⏱ Performance - must finish in 2000ms

Complex expression with negative and multiple operators; division truncates toward zero

💡 Handle negative numbers and multiple operators carefully.

💡 Division truncation toward zero is critical here.

💡 Trace stack operations step-by-step to verify correctness.

Why it failed: Incorrect result often due to wrong division truncation or operator precedence. Fix by applying truncation toward zero and correct operand order.

✓ Handles complex expressions with negatives and multiple operators correctly.

t2_03edge

Input["0"]

Expected0

⏱ Performance - must finish in 2000ms

Single zero operand returns zero

💡 Zero is a valid operand and should be returned as is.

💡 No operators means no stack operations needed.

💡 Check for single token edge case before processing.

Why it failed: Failing this means code does not handle zero operand correctly. Fix by returning int(token) if tokens length is 1.

✓ Correctly handles zero operand input.

t3_01corner

Input["4","13","5","/","+","2","*"]

Expected12

⏱ Performance - must finish in 2000ms

((4 + (13 / 5)) * 2) = (4 + 2) * 2 = 12; tests correct operator order and stack usage

💡 Check that operators are applied in correct order with correct operands.

💡 Ensure stack pops right operand first, then left operand.

💡 Fix operand order in operator application if result is wrong.

Why it failed: Wrong output due to reversed operand order in operator application. Fix by popping right operand first, then left operand.

✓ Correctly applies operators with proper operand order.

t3_02corner

Input["3","4","+","2","*","7","/"]

Expected2

⏱ Performance - must finish in 2000ms

((3 + 4) * 2) / 7 = 14 / 7 = 2; tests correct truncation and operator precedence

💡 Division must truncate toward zero, not floor.

💡 Check operator precedence is handled by stack order.

💡 Use int(left / right) or equivalent truncation.

Why it failed: Incorrect division truncation or operator precedence causes wrong output. Fix by truncating division toward zero and applying operators in correct order.

✓ Correctly handles division truncation and operator precedence.

t3_03corner

Input["5","1","2","+","4","*","+","3","-"]

Expected14

⏱ Performance - must finish in 2000ms

5 + ((1 + 2) * 4) - 3 = 5 + 12 - 3 = 14; tests nested operations and stack correctness

💡 Nested operations require correct stack push/pop sequence.

💡 Ensure each operator applies to the last two operands on stack.

💡 Trace stack changes step-by-step to debug.

Why it failed: Wrong output due to incorrect stack push/pop or operator application. Fix by ensuring each operator pops two operands and pushes result.

✓ Correctly evaluates nested expressions with multiple operators.

t4_01performance

Input["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+","+"]

Expectednull

⏱ Performance - must finish in 2000ms

n=100 tokens with many additions; O(n) stack-based evaluation must complete within 2 seconds

💡 Use an iterative stack-based approach for O(n) time complexity.

💡 Avoid recursion or repeated string parsing inside loops.

💡 Pre-allocate stack or use efficient data structures.

Why it failed: TLE indicates exponential or quadratic complexity. Fix by implementing O(n) iterative stack evaluation.

✓ Efficient O(n) stack-based evaluation confirmed.

Practice

1. You are given a circular array of integers and need to find, for each element, the next greater element when traversing the array circularly. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Brute force nested loops checking each element's next greater by scanning forward twice

B. Greedy approach selecting next greater element by local comparisons only

C. Dynamic programming with memoization of next greater elements

D. Monotonic stack with explicit circular array copy to simulate circular traversal

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the next greater element for each item in a circular array, which means elements after the end wrap around to the start.

2. Step 2: Identify algorithmic pattern

   Brute force is O(n²), greedy/local comparisons fail on circular wrap, and DP is not naturally suited. Monotonic stack with explicit circular array copy simulates circular traversal efficiently in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Monotonic stack with doubled array -> O(n) time [OK]

Hint: Circular array + next greater -> monotonic stack with doubling [OK]

Common Mistakes:

• Assuming greedy local comparisons suffice for circular arrays
• Thinking DP applies directly without circular simulation
• Believing brute force is optimal for large inputs

2. Consider this buggy implementation of the pop method in the two-stack queue. What is the bug?

def pop(self) -> int:
    while self.push_stack:
        self.pop_stack.append(self.push_stack.pop())
    return self.pop_stack.pop()

medium

A. The push_stack should be cleared after transfer to avoid duplicates.

B. The pop_stack.pop() call should be replaced with pop_stack[-1] to peek instead of pop.

C. The transfer loop should only run if pop_stack is empty, otherwise elements are transferred every pop causing inefficiency.

D. The method should check if both stacks are empty before popping to avoid runtime errors.

Solution

1. Step 1: Identify transfer condition

   The code transfers elements from push_stack to pop_stack on every pop, regardless of pop_stack state.

2. Step 2: Understand impact

   This causes O(n) time on every pop, losing amortized O(1) efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Transfer only when pop_stack empty -> amortized O(1) [OK]

Hint: Transfer only if pop_stack empty to keep amortized O(1) [OK]

Common Mistakes:

• Transferring every pop causes O(n) pop time
• Not checking empty queue before pop

3. What is the time complexity of the push operation in the optimal one-queue implementation of a stack using queues, where the queue is rotated after each push to maintain stack order?

medium

A. O(1) amortized, because each element is enqueued once

B. O(log n), due to partial rotations of the queue

C. O(n^2), because rotations accumulate over multiple pushes

D. O(n), because after each push, the queue is rotated by dequeuing and enqueuing all previous elements

Solution

1. Step 1: Identify complexity of outer and inner loops

   Each push appends one element and then rotates the queue by moving all other elements (n-1) times.

2. Step 2: Check if rotations accumulate

   Each push costs O(n) individually, not O(n^2) overall, because rotations happen per push, not nested.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Rotation after push moves all existing elements once -> O(n) per push [OK]

Hint: Rotation moves all existing elements once per push -> O(n) [OK]

Common Mistakes:

• Assuming push is O(1) because enqueue is O(1)
• Confusing total cost over multiple pushes with single push cost
• Thinking rotations are partial and thus O(log n)

4. Consider this buggy code for the stock span problem. Which line contains the subtle bug that causes incorrect spans when prices are equal?

medium

A. Line 9: span calculation does not add 1 when stack is not empty

B. Line 11: appending price after appending index to stack

C. Line 6: while condition uses '<' instead of '<='

D. Line 7: popping from stack without checking if empty

Solution

1. Step 1: Identify the bug in while condition

   The condition uses '<' instead of '<=', so equal prices are not popped, causing incorrect spans.

2. Step 2: Confirm other lines are correct

   Span calculation correctly handles empty stack. Appending order is correct. Stack emptiness is checked before popping.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using '<=' ensures equal prices are popped for correct spans [OK]

Hint: Use '<=' in while to pop equal or smaller prices [OK]

Common Mistakes:

• Using '<' causes incorrect spans for equal prices
• Misplaced span calculation

5. Suppose the problem is modified so that the array is circular and you want to find the next greater element allowing repeated reuse of elements (i.e., you can wrap around multiple times). Which modification to the monotonic stack approach correctly handles this variant?

hard

A. Modify the stack to store values instead of indices to handle repeated reuse

B. Use a brute force nested loop with modulo indexing to simulate infinite wrap

C. Extend the doubled array to triple or more copies and run the same monotonic stack algorithm

D. Use a queue instead of a stack to process elements in order for multiple wraps

Solution

1. Step 1: Understand problem variant

   Allowing repeated reuse means next greater element might appear after multiple wraps, not just one.

2. Step 2: Modify approach accordingly

   Extending the array to triple or more copies simulates multiple wraps, allowing monotonic stack to find next greater elements beyond one wrap.

3. Step 3: Why other options fail

   Brute force is inefficient; storing values loses index mapping; queue does not maintain monotonic property needed.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Extending array copies simulates multiple wraps correctly [OK]

Hint: Multiple wraps -> extend array copies accordingly [OK]

Common Mistakes:

• Using brute force which is inefficient
• Storing values instead of indices losing position info
• Replacing stack with queue losing monotonic property