Evaluate Reverse Polish Notation

▶

Steps

setup

Initialize operator functions and empty stack

The algorithm sets up a dictionary mapping operators to their corresponding functions and initializes an empty stack to hold operands and intermediate results.

💡 This setup is essential because it defines how operators will be applied and prepares the data structure to store values.

Line:

ops = {
    '+': operator.add,
    '-': operator.sub,
    '*': operator.mul,
    '/': lambda x, y: int(x / y),
}
stack = []

💡 Operators are mapped to functions for quick application; the stack starts empty to build results.

traverse

Start processing first token: '2'

The algorithm reads the first token '2' from the input array.

💡 Each token is processed in order to evaluate the expression.

Line:

for i, token in enumerate(tokens):

💡 Tokens are processed sequentially, and the type of token determines the stack operation.

traverse

Push number '2' onto the stack

Since '2' is a number, it is converted to integer and pushed onto the stack.

💡 Numbers are pushed onto the stack to be used later by operators.

Line:

else:
    stack.append(int(token))

💡 Operands accumulate on the stack until an operator is encountered.

traverse

Start processing second token: '1'

The algorithm reads the second token '1' from the input array.

💡 Each token is processed in order to evaluate the expression.

Line:

for i, token in enumerate(tokens):

💡 Tokens are processed sequentially, and the type of token determines the stack operation.

traverse

Push number '1' onto the stack

Since '1' is a number, it is converted to integer and pushed onto the stack.

💡 Each number is pushed to the stack to be available for future operations.

Line:

else:
    stack.append(int(token))

💡 Stack now holds two operands, ready for an operator to apply.

compare

Start processing third token: '+'

The algorithm reads the third token '+', which is an operator.

💡 Operators trigger popping operands and applying operations.

Line:

if token in ops:

💡 Operators cause the stack to be transformed by applying operations on top operands.

compare

Pop right operand for '+'

Pop the top element (right operand) from the stack to apply the '+' operator.

💡 Operators consume operands by popping them from the stack.

Line:

right = stack.pop()

💡 The right operand is the last pushed number on the stack.

compare

Pop left operand for '+'

Pop the next top element (left operand) from the stack to apply the '+' operator.

💡 Operators consume operands by popping them from the stack.

Line:

left = stack.pop()

💡 Operands are popped in reverse order of pushing: right then left.

compare

Apply '+' operator and push result

Apply the '+' operator to operands 2 and 1, compute 3, and push it back onto the stack.

💡 Operators replace operands with their computed result on the stack.

Line:

stack.append(ops[token](left, right))

💡 The stack is reduced by replacing two operands with one result.

traverse

Start processing fourth token: '3'

The algorithm reads the fourth token '3' from the input array.

💡 Each token is processed in order to evaluate the expression.

Line:

for i, token in enumerate(tokens):

💡 Tokens are processed sequentially, and the type of token determines the stack operation.

traverse

Push number '3' onto the stack

Since '3' is a number, it is converted to integer and pushed onto the stack.

💡 Numbers continue to be pushed onto the stack to be used by upcoming operators.

Line:

else:
    stack.append(int(token))

💡 Stack now holds the intermediate result and a new operand.

compare

Start processing fifth token: '*'

The algorithm reads the fifth token '*', which is an operator.

💡 Operators trigger popping operands and applying operations.

Line:

if token in ops:

💡 Operators cause the stack to be transformed by applying operations on top operands.

compare

Pop right operand for '*'

Pop the top element (right operand) from the stack to apply the '*' operator.

💡 Operators consume operands by popping them from the stack.

Line:

right = stack.pop()

💡 The right operand is the last pushed number on the stack.

compare

Pop left operand for '*'

Pop the next top element (left operand) from the stack to apply the '*' operator.

💡 Operators consume operands by popping them from the stack.

Line:

left = stack.pop()

💡 Operands are popped in reverse order of pushing: right then left.

compare

Apply '*' operator and push result

Apply the '*' operator to operands 3 and 3, compute 9, and push it back onto the stack.

💡 Operators replace operands with their computed result on the stack.

Line:

stack.append(ops[token](left, right))

💡 The stack is reduced by replacing two operands with one result.

reconstruct

End of tokens: pop final result

All tokens have been processed. The algorithm pops the last remaining element from the stack, which is the final result of the expression evaluation.

💡 The last element on the stack is the answer to the Reverse Polish Notation expression.

Line:

return stack.pop()

💡 The stack now contains only the final computed value, which is returned as the answer.

import operator

class Solution:
    def evalRPN(self, tokens):
        # STEP 1: Initialize operator functions and stack
        ops = {
            '+': operator.add,  # STEP 4 and 6 apply
            '-': operator.sub,
            '*': operator.mul,
            '/': lambda x, y: int(x / y),
        }
        stack = []

        for i, token in enumerate(tokens):
            if token in ops:
                # STEP 4 and 6: Pop two operands and apply operator
                right = stack.pop()  # pop right operand
                left = stack.pop()   # pop left operand
                stack.append(ops[token](left, right))  # push result
            else:
                # STEP 2,3,5: Push number onto stack
                stack.append(int(token))

        # STEP 7: Pop final result
        return stack.pop()

📊

Evaluate Reverse Polish Notation - Watch the Algorithm Execute, Step by Step

Watching each token processed and how the stack changes is the fastest way to understand how Reverse Polish Notation evaluation works, especially how operators consume operands and produce intermediate results.

no_op

Stack (top→bottom)

empty

no_opElement[0]: 2

Stack (top→bottom)

empty

pushElement[0]: 2

Stack (top→bottom)

2

↑ pushed: 2

no_opElement[1]: 1

Stack (top→bottom)

2

pushElement[1]: 1

Stack (top→bottom)

1

2

↑ pushed: 1

no_opElement[2]: +

Stack (top→bottom)

1

2

popElement[2]: +

Stack (top→bottom)

2

↓ popped: [1]

popElement[2]: +

Stack (top→bottom)

empty

↓ popped: [2]

pushElement[2]: +

Stack (top→bottom)

3

↑ pushed: 3

↓ popped: [1, 2]

Contributes: 3

no_opElement[3]: 3

Stack (top→bottom)

3

pushElement[3]: 3

Stack (top→bottom)

3

3

↑ pushed: 3

no_opElement[4]: *

Stack (top→bottom)

3

3

popElement[4]: *

Stack (top→bottom)

3

↓ popped: [3]

popElement[4]: *

Stack (top→bottom)

empty

↓ popped: [3]

pushElement[4]: *

Stack (top→bottom)

9

↑ pushed: 9

↓ popped: [3, 3]

Contributes: 9

pop

Stack (top→bottom)

empty

↓ popped: [9]

Contributes: 9

Key Takeaways

✓ The stack holds operands and intermediate results, and operators reduce the stack by combining the top two elements.

This insight is hard to see from code alone because the stack changes dynamically and the flow of pushing and popping is easier to grasp visually.

✓ Each operator triggers a pop-pop-apply-push sequence, which transforms the stack and builds the final result step-by-step.

Seeing this sequence repeatedly helps understand the core mechanism of RPN evaluation.

✓ The final answer is the single remaining element on the stack after all tokens are processed.

This clarifies why the algorithm returns stack.pop() at the end and why the stack must have exactly one element then.

Practice

1. You receive a continuous stream of lowercase letters and need to report the first character that appears exactly once at each step. Which approach guarantees an optimal O(n) time solution with constant space for this problem?

easy

A. Use a dynamic programming approach to store subproblems of unique characters at each prefix of the stream.

B. Use a brute force scan of the entire stream so far to find the first unique character after each new letter.

C. Maintain a fixed-size frequency array for all lowercase letters and a queue to track potential unique characters, updating both as new letters arrive.

D. Use a greedy approach that picks the first character that hasn't appeared before without tracking frequencies.

Solution

1. Step 1: Understand problem constraints

   The stream consists of lowercase letters only, so a fixed-size frequency array of length 26 suffices.

2. Step 2: Identify optimal approach

   Using a frequency array plus a queue to track candidates for first unique character allows O(1) updates per character and O(n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Frequency array + queue approach is standard for this problem [OK]

Hint: Frequency array + queue yields O(n) time and O(1) space [OK]

Common Mistakes:

• Thinking brute force scanning is efficient enough
• Assuming DP applies here
• Using greedy without frequency tracking

2. You are given an array of integers and need to find, for each element, the closest smaller element that appears before it in the array. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Monotonic stack maintaining indexes of elements in increasing order

B. Dynamic Programming with memoization to store previous results

C. Greedy approach scanning from left to right without extra data structures

D. Sorting the array and using binary search to find smaller elements

Solution

1. Step 1: Understand the problem requirement

   We need to find the closest smaller element to the left for each element efficiently.

2. Step 2: Identify the approach that supports O(n) time

   Monotonic stacks maintain a strictly increasing sequence of indexes, allowing popping of larger or equal elements and pushing current index, ensuring each element is pushed and popped at most once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is well-known for O(n) time in previous smaller element problems [OK]

Hint: Monotonic stacks solve closest smaller element in O(n) [OK]

Common Mistakes:

• Assuming greedy scanning without stack is enough
• Thinking sorting helps since order matters
• Confusing DP with this problem

3. What is the time and space complexity of the optimal stack-less solution for evaluating a Basic Calculator II expression of length n?

medium

A. O(n) time and O(1) space because it processes the string once and uses only a few variables.

B. O(n^2) time and O(n) space due to repeated string slicing and stack usage.

C. O(n) time and O(n) space because it uses a stack to store intermediate results.

D. O(n log n) time due to sorting operators by precedence and O(1) space.

Solution

1. Step 1: Identify time complexity

   The algorithm scans the input string once, performing constant-time operations per character, so time is O(n).

2. Step 2: Identify space complexity

   Only a fixed number of variables are used (total, last_num, current_num, current_op), so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass and constant variables confirm O(n) time and O(1) space [OK]

Hint: Single pass with fixed vars means O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming stack usage means O(n) space
• Confusing recursion stack with iteration
• Thinking sorting operators is needed

4. What is the time complexity of the getMin() operation in the single stack with encoded minimum values approach for the Minimum Stack problem, and why?

medium

A. O(1), because the minimum value is stored and updated during push and pop operations.

B. O(n), because it needs to scan the entire stack to find the minimum.

C. O(log n), because the stack maintains a balanced structure to track minimums.

D. O(n), because the encoded differences require decoding all elements to find the minimum.

Solution

1. Step 1: Understand getMin() operation

   In the encoded stack approach, minVal is updated on every push/pop, so getMin() just returns minVal.

2. Step 2: Analyze complexity

   Since getMin() returns a stored variable without iteration, it runs in O(1) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   getMin() is a direct variable access, no loops [OK]

Hint: getMin() returns stored minVal updated on push/pop [OK]

Common Mistakes:

• Assuming getMin scans stack
• Confusing encoded values require decoding
• Thinking balanced tree needed for min tracking

5. What is the time complexity of the optimal monotonic stack algorithm for finding the previous smaller element in an array of size n, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because each element is pushed and popped at most once from the stack

B. O(n^2) because each element can be compared with all previous elements in worst case

C. O(n log n) due to repeated stack operations resembling binary search

D. O(n) but with O(n^2) auxiliary space due to storing intermediate results

Solution

1. Step 1: Identify the operations per element

   Each element is pushed once and popped at most once from the stack, so total stack operations are O(n).

2. Step 2: Understand why O(n^2) is a common misconception

   Nested loops in brute force suggest O(n^2), but monotonic stack avoids repeated comparisons by popping larger elements immediately.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack operations linear in n, no nested iteration causing quadratic time [OK]

Hint: Each element pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Confusing brute force nested loops with stack approach
• Assuming stack operations cost log n each
• Forgetting stack pops amortize total cost