Balanced Parentheses Problem Using Stack in DSA Python

Mental Model

We use a stack to keep track of opening brackets and check if each closing bracket matches the last opened one.

Analogy: Imagine stacking plates; you put a plate on top for each opening bracket and remove the top plate when you see a matching closing bracket.

Stack (top at right): []
Expression: ( [ { } ] )
↑ start here

Dry Run Walkthrough

Input: expression: "({[]})"

Goal: Check if all parentheses in the expression are correctly balanced and matched.

Step 1: Read '(' and push it onto the stack

Stack: ['(']
Expression pointer at '{'

Why: We store opening brackets to match them later with closing ones

Step 2: Read '{' and push it onto the stack

Stack: ['(', '{']
Expression pointer at '['

Why: Keep track of nested opening brackets

Step 3: Read '[' and push it onto the stack

Stack: ['(', '{', '[']
Expression pointer at ']'

Why: Add the latest opening bracket to stack

Step 4: Read ']' and check top of stack: '[' matches, so pop it

Stack: ['(', '{']
Expression pointer at '}'

Why: Closing bracket matches last opening, so remove it

Step 5: Read '}' and check top of stack: '{' matches, so pop it

Stack: ['(']
Expression pointer at ')'

Why: Continue matching closing brackets with last opening

Step 6: Read ')' and check top of stack: '(' matches, so pop it

Stack: []
Expression pointer at end

Why: All brackets matched, stack is empty

Result:

Stack: []
Expression is balanced

Annotated Code

DSA Python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        return len(self.items) == 0

def is_balanced(expression: str) -> bool:
    stack = Stack()
    pairs = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':
            stack.push(char)  # push opening bracket
        elif char in ')]}':
            top = stack.pop()  # pop last opening bracket
            if top != pairs[char]:
                return False  # mismatch found
    return stack.is_empty()  # True if all matched

# Driver code
expr = "({[]})"
if is_balanced(expr):
    print("Expression is balanced")
else:
    print("Expression is not balanced")

stack.push(char) # push opening bracket

Add opening bracket to stack to match later

top = stack.pop() # pop last opening bracket

Remove last opening bracket to check match

if top != pairs[char]:

Check if popped bracket matches current closing bracket

return stack.is_empty() # True if all matched

If stack empty at end, all brackets matched

Output

Expression is balanced

Complexity Analysis

Time: O(n) because we scan the expression once, pushing and popping at most once per character

Space: O(n) because in worst case all characters are opening brackets stored in stack

vs Alternative: Compared to scanning multiple times or using counters, stack approach handles nested and mixed brackets correctly with linear time

Edge Cases

Empty string

Returns True because no brackets means balanced

DSA Python

return stack.is_empty()  # True if all matched

String with only opening brackets like "((("

Returns False because stack not empty at end

DSA Python

return stack.is_empty()  # True if all matched

String with mismatched brackets like "([)]"

Returns False when mismatch detected at pop

DSA Python

if top != pairs[char]:

When to Use This Pattern

When you see a problem asking if brackets or symbols are correctly paired and nested, use the stack pattern to track openings and match closings efficiently.

Common Mistakes

Mistake: Not checking if stack is empty before popping, causing errors
Fix: Always check stack is not empty before pop or use a safe pop method

Mistake: Comparing closing bracket directly to opening bracket without mapping pairs
Fix: Use a dictionary to map closing to opening brackets for correct matching

Summary

Checks if every opening bracket has a matching closing bracket in correct order.

Use when you need to verify balanced and properly nested parentheses or brackets.

The key insight is to push opening brackets and pop them when matching closing brackets appear, ensuring order and pairing.

Practice

1. What does the Balanced Parentheses problem using a stack check for in a string?

easy

A. Whether every opening bracket has a matching closing bracket in correct order

B. If the string contains only alphabets

C. If the string length is even

D. Whether the string contains any numbers

Solution

1. Step 1: Understand the problem goal

   The Balanced Parentheses problem checks if all opening brackets like '(' have a matching closing bracket ')' in the correct order.

2. Step 2: Role of stack in checking

   A stack helps track opening brackets and ensures each one is closed properly in sequence.

3. Final Answer:

   Whether every opening bracket has a matching closing bracket in correct order -> Option A

4. Quick Check:

   Balanced parentheses = matching pairs in order [OK]

Hint: Stack tracks openings; match with closings in order [OK]

Common Mistakes:

• Thinking it checks string length
• Confusing with character types
• Ignoring order of brackets

2. Which of the following is the correct way to push an element 'x' onto a stack named 'stack' in Python?

easy

A. stack.push(x)

B. stack.append(x)

C. stack.add(x)

D. stack.insert(x)

Solution

1. Step 1: Recall Python list methods for stack

   Python uses list to implement stack; to add an element on top, use append().

2. Step 2: Check each option

   add() and push() are not list methods; insert() adds at specific index, not top.

3. Final Answer:

   stack.append(x) -> Option B

4. Quick Check:

   Use append() to push in Python stack [OK]

Hint: Use append() to push in Python stack [OK]

Common Mistakes:

• Using push() which is not a Python list method
• Using add() which is for sets
• Using insert() without index

3. What will be the output of the following code snippet?

def is_balanced(s):
    stack = []
    for char in s:
        if char == '(': stack.append(char)
        elif char == ')':
            if not stack: return False
            stack.pop()
    return not stack

print(is_balanced('(()())'))
print(is_balanced('(()'))

medium

A. True\nFalse

B. False\nTrue

C. True\nTrue

D. False\nFalse

Solution

1. Step 1: Trace first input '(()())'

   Push '(' three times, pop ')' three times, stack empty at end, returns True.

2. Step 2: Trace second input '(()'

   Push '(' twice, one ')' pops one '(', stack not empty at end, returns False.

3. Final Answer:

   True\nFalse -> Option A

4. Quick Check:

   Balanced string returns True, unbalanced returns False [OK]

Hint: Empty stack at end means balanced parentheses [OK]

Common Mistakes:

• Not checking stack empty at end
• Returning true too early
• Ignoring unmatched openings

4. Find the error in this code snippet for checking balanced parentheses:

def check_balance(s):
    stack = []
    for ch in s:
        if ch == '(': stack.push(ch)
        elif ch == ')':
            if stack == []: return False
            stack.pop()
    return len(stack) == 0

medium

A. Using '==' to check empty stack is wrong

B. Missing return statement inside the loop

C. stack.push(ch) is invalid; use stack.append(ch) instead

D. pop() should be called before checking stack empty

Solution

1. Step 1: Identify stack method error

   Python list has no push() method; append() should be used to add elements.

2. Step 2: Verify other parts

   Return statements and empty checks are correct; pop() after check is correct.

3. Final Answer:

   stack.push(ch) is invalid; use stack.append(ch) instead -> Option C

4. Quick Check:

   Use append() to add in Python list stack [OK]

Hint: Use append() not push() for Python list stack [OK]

Common Mistakes:

• Using push() instead of append()
• Checking stack emptiness incorrectly
• Calling pop() without checking stack

5. Given the string s = '{[()()]}', which modification is needed in the balanced parentheses stack algorithm to correctly check this string?

hard

A. Only check for parentheses '()' and ignore other brackets

B. Count total number of brackets without matching pairs

C. Use a queue instead of a stack to check balance

D. Add support for multiple types of brackets and match pairs accordingly

Solution

1. Step 1: Identify bracket types in string

   The string contains curly braces {}, square brackets [], and parentheses ().

2. Step 2: Modify algorithm for multiple bracket types

   The stack algorithm must track each opening bracket type and match it with the correct closing bracket type.

3. Final Answer:

   Add support for multiple types of brackets and match pairs accordingly -> Option D

4. Quick Check:

   Match bracket types correctly for balanced check [OK]

Hint: Match each opening bracket with its correct closing type [OK]

Common Mistakes:

• Checking only parentheses and ignoring others
• Using queue instead of stack
• Counting brackets without matching