Basic Calculator (With Parentheses)

▶

Steps

setup

Initialize variables and stack

Initialize an empty stack, result = 0, sign = 1, and num = 0 before processing the input string.

💡 Setting up these variables is essential to accumulate the result and track signs and numbers as we parse the expression.

Line:

stack = []
result = 0
sign = 1
num = 0

💡 The algorithm starts with a clean state to process the expression character by character.

expand

Process '(' - push current result and sign

Encounter '(' at index 0: push current result (0) and sign (1) onto the stack, then reset result and sign for new sub-expression.

💡 Pushing saves the current context so the algorithm can evaluate the expression inside the parentheses independently.

Line:

stack.append(result)
stack.append(sign)
result = 0
sign = 1

💡 Stack now holds previous context; result and sign reset to start fresh inside parentheses.

fill_cells

Process digit '1' - build number

Encounter digit '1' at index 1: build the current number by multiplying previous num by 10 and adding digit value.

💡 Building multi-digit numbers is necessary to handle numbers larger than 9.

Line:

num = num * 10 + int(c)

💡 num is now 1, representing the current number being parsed.

compare

Process '+' - add number to result and update sign

Encounter '+' at index 2: add current number (1) multiplied by sign (1) to result, reset num, and update sign to +1.

💡 Adding the number to result finalizes the current number before moving on.

Line:

result += sign * num
num = 0
sign = 1 if c == '+' else -1

💡 Result is now 1, ready to process next number with positive sign.

expand

Process '(' - push current result and sign

Encounter '(' at index 3: push current result (1) and sign (1) onto the stack, then reset result and sign for new sub-expression.

💡 Again, pushing context to stack to handle nested parentheses.

Line:

stack.append(result)
stack.append(sign)
result = 0
sign = 1

💡 Stack now holds previous contexts for nested evaluation.

fill_cells

Process digit '4' - build number

Encounter digit '4' at index 4: build current number by multiplying previous num by 10 and adding digit value.

💡 Building the number inside nested parentheses.

Line:

num = num * 10 + int(c)

💡 num is now 4, ready to be added to result.

compare

Process '+' - add number to result and update sign

Encounter '+' at index 5: add current number (4) multiplied by sign (1) to result, reset num, and update sign to +1.

💡 Add completed number to result before processing next number.

Line:

result += sign * num
num = 0
sign = 1 if c == '+' else -1

💡 Result inside parentheses is now 4.

fill_cells

Process digit '5' - build number

Encounter digit '5' at index 6: build current number by multiplying previous num by 10 and adding digit value.

💡 Continuing to build numbers inside nested parentheses.

Line:

num = num * 10 + int(c)

💡 num is now 5.

compare

Process '+' - add number to result and update sign

Encounter '+' at index 7: add current number (5) multiplied by sign (1) to result, reset num, and update sign to +1.

💡 Add the last built number to the current result.

Line:

result += sign * num
num = 0
sign = 1 if c == '+' else -1

💡 Result inside parentheses is now 9 (4 + 5).

fill_cells

Process digit '2' - build number

Encounter digit '2' at index 8: build current number by multiplying previous num by 10 and adding digit value.

💡 Building the next number inside parentheses.

Line:

num = num * 10 + int(c)

💡 num is now 2.

shrink

Process ')' - add number and combine with stack

Encounter ')' at index 9: add current number (2) multiplied by sign (1) to result, reset num, then pop sign and previous result from stack and combine.

💡 Closing parentheses means combining the evaluated sub-expression with outer context.

Line:

result += sign * num
num = 0
result *= stack.pop()
result += stack.pop()

💡 Result inside parentheses is 11 (4+5+2), combined with outer context.

compare

Process '-' - add number to result and update sign

Encounter '-' at index 10: add current number (0) multiplied by sign (1) to result, reset num, and update sign to -1.

💡 Add any pending number before changing sign for subtraction.

Line:

result += sign * num
num = 0
sign = 1 if c == '+' else -1

💡 Result is now 11, sign updated for subtraction.

fill_cells

Process digit '3' - build number

Encounter digit '3' at index 11: build current number by multiplying previous num by 10 and adding digit value.

💡 Building number to subtract.

Line:

num = num * 10 + int(c)

💡 num is now 3.

shrink

Process ')' - add number and combine with stack

Encounter ')' at index 12: add current number (3) multiplied by sign (-1) to result, reset num, then pop sign and previous result from stack and combine.

💡 Closing outer parentheses, combine inner result with outer context.

Line:

result += sign * num
num = 0
result *= stack.pop()
result += stack.pop()

💡 Result is now 9 (0 + 11 - 3) combined with outer context 0.

compare

Process '+' - add number to result and update sign

Encounter '+' at index 13: add current number (0) multiplied by sign (1) to result, reset num, and update sign to +1.

💡 Add any pending number and prepare for addition.

Line:

result += sign * num
num = 0
sign = 1 if c == '+' else -1

💡 Result remains 9, sign updated for addition.

expand

Process '(' - push current result and sign

Encounter '(' at index 14: push current result (9) and sign (1) onto the stack, then reset result and sign for new sub-expression.

💡 Push context before evaluating new parentheses.

Line:

stack.append(result)
stack.append(sign)
result = 0
sign = 1

💡 Stack now holds context for last parentheses.

fill_cells

Process digit '6' - build number

Encounter digit '6' at index 15: build current number by multiplying previous num by 10 and adding digit value.

💡 Start building number inside last parentheses.

Line:

num = num * 10 + int(c)

💡 num is now 6.

compare

Process '+' - add number to result and update sign

Encounter '+' at index 16: add current number (6) multiplied by sign (1) to result, reset num, and update sign to +1.

💡 Add number before processing next number.

Line:

result += sign * num
num = 0
sign = 1 if c == '+' else -1

💡 Result inside parentheses is now 6.

fill_cells

Process digit '8' - build number

Encounter digit '8' at index 17: build current number by multiplying previous num by 10 and adding digit value.

💡 Build last number inside parentheses.

Line:

num = num * 10 + int(c)

💡 num is now 8.

shrink

Process ')' - add number and combine with stack

Encounter ')' at index 18: add current number (8) multiplied by sign (1) to result, reset num, then pop sign and previous result from stack and combine.

💡 Close last parentheses and combine with outer result.

Line:

result += sign * num
num = 0
result *= stack.pop()
result += stack.pop()

💡 Result is now 23 (9 + (6 + 8)).

reconstruct

Add any remaining number and return result

After processing all characters, add any remaining number (0) multiplied by sign (1) to result and return the final result.

💡 Final step ensures all numbers are accounted for in the result.

Line:

result += sign * num
return result

💡 Final result is 23, the evaluated value of the expression.

def calculate(s: str) -> int:
    stack = []  # STEP 1
    result = 0  # STEP 1
    sign = 1  # STEP 1
    num = 0  # STEP 1
    for i, c in enumerate(s):
        if c.isdigit():  # STEP 3,6,8,10,13,17,19
            num = num * 10 + int(c)  # STEP 3,6,8,10,13,17,19
        elif c in '+-':  # STEP 4,7,9,12,15
            result += sign * num  # STEP 4,7,9,12,15
            num = 0  # STEP 4,7,9,12,15
            sign = 1 if c == '+' else -1  # STEP 4,7,9,12,15
        elif c == '(':  # STEP 2,5,16
            stack.append(result)  # STEP 2,5,16
            stack.append(sign)  # STEP 2,5,16
            result = 0  # STEP 2,5,16
            sign = 1  # STEP 2,5,16
        elif c == ')':  # STEP 11,14,20
            result += sign * num  # STEP 11,14,20
            num = 0  # STEP 11,14,20
            result *= stack.pop()  # STEP 11,14,20
            result += stack.pop()  # STEP 11,14,20
    result += sign * num  # STEP 21
    return result  # STEP 21

📊

Basic Calculator (With Parentheses) - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the stack stores intermediate results and signs, making it easier to understand how nested expressions are evaluated.

no_op

Stack (top→bottom)

empty

pushElement[0]: (

Stack (top→bottom)

1

0

↑ pushed: 01

no_opElement[1]: 1

Stack (top→bottom)

1

0

no_opElement[2]: +

Stack (top→bottom)

1

0

Contributes: 1

pushElement[3]: (

Stack (top→bottom)

1

1

1

0

↑ pushed: 11

no_opElement[4]: 4

Stack (top→bottom)

1

1

1

0

no_opElement[5]: +

Stack (top→bottom)

1

1

1

0

Contributes: 4

no_opElement[6]: 5

Stack (top→bottom)

1

1

1

0

no_opElement[7]: +

Stack (top→bottom)

1

1

1

0

Contributes: 9

no_opElement[8]: 2

Stack (top→bottom)

1

1

1

0

popElement[9]: )

Stack (top→bottom)

1

0

↓ popped: [1, 1]

Contributes: 11

no_opElement[10]: -

Stack (top→bottom)

1

0

Contributes: 11

no_opElement[11]: 3

Stack (top→bottom)

1

0

popElement[12]: )

Stack (top→bottom)

empty

↓ popped: [1, 0]

Contributes: 9

no_opElement[13]: +

Stack (top→bottom)

empty

Contributes: 9

pushElement[14]: (

Stack (top→bottom)

1

9

↑ pushed: 91

no_opElement[15]: 6

Stack (top→bottom)

1

9

no_opElement[16]: +

Stack (top→bottom)

1

9

Contributes: 6

no_opElement[17]: 8

Stack (top→bottom)

1

9

popElement[18]: )

Stack (top→bottom)

empty

↓ popped: [1, 9]

Contributes: 23

no_op

Stack (top→bottom)

empty

Contributes: 23

Key Takeaways

✓ The stack stores previous results and signs to handle nested parentheses correctly.

This insight is hard to see from code alone because the stack operations are interleaved with number and sign processing.

✓ Numbers are built digit-by-digit and added to the result only when an operator or parenthesis is encountered.

Watching the incremental building of numbers clarifies how multi-digit numbers are handled.

✓ When a closing parenthesis is encountered, the algorithm pops the sign and previous result from the stack and combines them with the current result.

This step is crucial and can be confusing without seeing how the stack context is restored and combined.

Practice

1. You need to design a data structure that supports push, pop, top, and retrieving the minimum element in constant time. Which approach guarantees all operations run in O(1) time without scanning the entire stack for the minimum each time?

easy

A. Use a brute force stack and scan the entire stack to find the minimum on each getMin call.

B. Use a dynamic programming table to store minimums for all sub-stacks and update it on each push/pop.

C. Keep two stacks: one for all elements and one for minimum elements, pushing to the min stack only when a new minimum is found.

D. Maintain a single stack that stores the difference between the pushed value and the current minimum, updating the minimum accordingly.

Solution

1. Step 1: Understand the problem constraints

   The goal is to achieve O(1) time for all operations including getMin, without scanning the entire stack.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n), dynamic programming is unnecessary and inefficient, two stacks approach works but uses extra space. The single stack with encoded differences stores relative values and updates min in O(1) time and space efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single stack encoding achieves O(1) time and O(n) space with one stack [OK]

Hint: Single stack encoding stores differences for O(1) min retrieval [OK]

Common Mistakes:

• Thinking scanning stack for min is acceptable
• Confusing two-stack approach as optimal space
• Assuming DP is needed for min tracking

2. Consider this buggy version of the decodeString function. Which line contains the subtle bug that causes incorrect decoding for inputs with multiple bracketed substrings?

medium

A. Line appending current_string to string_stack

B. Line popping count from count_stack

C. Line resetting k after '[' is missing

D. Line appending characters to current_string

Solution

1. Step 1: Identify where repeat count is reset

   After pushing k to count_stack on '[', k must be reset to 0 to avoid carryover to next substring.

2. Step 2: Locate missing reset

   The code comment indicates missing reset of k after pushing it, causing subsequent repeats to accumulate incorrectly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting k prevents repeat count carryover bugs [OK]

Hint: Repeat count must reset after pushing to stack [OK]

Common Mistakes:

• Forgetting to reset repeat count after '['
• Mismanaging stack push/pop order

3. What is the time complexity of the dequeue operation in the optimal circular queue implementation using a fixed-size array with head, tail pointers, and a size variable?

medium

A. O(n), because elements need to be shifted after dequeue

B. O(log n), due to pointer arithmetic

C. O(1), because head pointer moves forward with modulo wrap-around

D. O(n), because size variable needs to be updated

Solution

1. Step 1: Identify complexity of pointer movement

   Dequeue moves head pointer forward by one position modulo capacity, which is a constant time operation.

2. Step 2: Check if any other operations add complexity

   No shifting of elements or complex calculations occur; size variable update is O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Dequeue is O(1) due to simple pointer increment and size decrement [OK]

Hint: Pointer increment modulo capacity is O(1) [OK]

Common Mistakes:

• Assuming shifting elements is needed
• Confusing pointer arithmetic with logarithmic time
• Thinking size update is costly

4. The following code attempts to implement a stack using two queues with a costly push operation:

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        # Missing swap here

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return not self.q1

What is the subtle bug in this code?

medium

A. The push method is missing swapping q1 and q2 after transferring elements.

B. The empty method should check both q1 and q2 for emptiness.

C. The top method should peek at q2 instead of q1.

D. The pop method should dequeue from q2 instead of q1.

Solution

1. Step 1: Analyze push method

   Elements are moved from q1 to q2, but q1 and q2 are never swapped, so q1 remains empty after push.

2. Step 2: Consequence on pop and top

   Pop and top operate on q1, which is empty, causing errors or incorrect behavior.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping queues after push is essential to maintain main queue reference [OK]

Hint: Missing queue swap after push breaks main queue reference [OK]

Common Mistakes:

• Forgetting to swap queues after push
• Accessing wrong queue in pop or top
• Checking emptiness incorrectly

5. Suppose the calculator must now support expressions where numbers can be reused multiple times (e.g., "2*2*2") and the input length can be very large. Which modification to the optimal approach is necessary to handle this efficiently?

hard

A. Switch to a brute force left-to-right evaluation ignoring precedence to reduce complexity.

B. Implement memoization to cache results of subexpressions to avoid recomputation.

C. Use a stack to immediately evaluate multiplication and division, but keep track of last_num to handle repeated operations efficiently.

D. Use recursion with backtracking to explore all possible reuse combinations.

Solution

1. Step 1: Understand reuse impact

   Repeated multiplication/division requires immediate evaluation to maintain precedence and efficiency.

2. Step 2: Identify suitable approach

   Using a stack or stack-like variables to immediately compute * and / handles repeated operations efficiently without extra overhead.

3. Step 3: Reject alternatives

   Brute force ignores precedence, memoization is unnecessary for linear evaluation, recursion/backtracking is inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Immediate evaluation with stack variables handles reuse and large inputs efficiently [OK]

Hint: Immediate evaluation with stack variables handles repeated ops efficiently [OK]

Common Mistakes:

• Ignoring precedence in reuse
• Using recursion unnecessarily
• Trying brute force for efficiency