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.