Balanced Parentheses Problem Using Stack in DSA Python - Execution Trace

Concept Flow - Balanced Parentheses Problem Using Stack

Start

↓

Read next char

↓

Is char '(' or '{' or '['?

Yes→Push to stack

No↓

Is char ')' or '}' or '

↓

Pop from stack

↓

Does popped match char?

No→Unbalanced

Yes↓

More chars?

Yes→Read next char

No↓

Stack empty?

Yes→Balanced

No↓

Unbalanced

The flow reads each character, pushes opening brackets, pops and checks matching closing brackets, and finally checks if stack is empty to decide balance.

Execution Sample

DSA Python

def is_balanced(s):
    stack = []
    pairs = {')':'(', '}':'{', ']':'['}
    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack

Checks if the input string s has balanced parentheses using a stack.

Execution Table

Step	Operation	Current Char	Stack Before	Stack After	Action	Visual State
1	Read char	(	[]	(	Push '('	Stack: (top) ['('] (bottom)
2	Read char	[	(	(, [	Push '['	Stack: (top) ['[', '('] (bottom)
3	Read char	]	(, [	(	Pop '[' and match with ']'	Stack: (top) ['('] (bottom)
4	Read char	)	(		Pop '(' and match with ')'	Stack: empty
5	End of string				Stack empty, balanced	Stack: empty

💡 End of string reached and stack is empty, so parentheses are balanced.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
stack	[]	(	(, [	(
current_char	None	(	[	]	)	None

Key Moments - 3 Insights

Why do we check if the stack is empty before popping?

Because popping from an empty stack causes error and means there is a closing bracket without a matching opening bracket, as shown in step 3 where stack is checked before pop.

Why do we return False if the popped bracket does not match the current closing bracket?

Because it means the brackets are not properly nested or matched, as in step 3 where popped '[' matches ']' but if it didn't, we would return False immediately.

Why do we check if the stack is empty at the end?

Because leftover opening brackets mean some brackets were not closed, so only an empty stack means balanced parentheses, as shown in step 5.

Visual Quiz - 3 Questions

Look at the execution table, what is the stack after reading the second character?

A ['(']

B ['(', '[']

C ['[']

D []

💡 Hint

Check the 'Stack After' column at Step 2 in the execution table.

At which step does the stack become empty again after pushing elements?

A Step 3

B Step 4

C Step 5

D Step 2

💡 Hint

Look at the 'Stack After' column and find when it changes to empty after being non-empty.

If the input string was '([)]', at which step would the function return False?

A After reading the third character

B After reading the second character

C After reading the fourth character

D At the end of the string

💡 Hint

Check when the popped bracket does not match the current closing bracket in the execution flow.

Concept Snapshot

Balanced Parentheses Using Stack:
- Push opening brackets onto stack.
- On closing bracket, pop and check match.
- If mismatch or empty stack on pop, return False.
- At end, if stack empty, return True (balanced).
- Else, return False (unbalanced).

Full Transcript

This visualization shows how to check balanced parentheses using a stack. We read each character of the string. If it is an opening bracket like '(', '{', or '[', we push it onto the stack. If it is a closing bracket like ')', '}', or ']', we check if the stack is empty. If empty, it means no matching opening bracket, so unbalanced. Otherwise, we pop the top of the stack and check if it matches the closing bracket. If it does not match, unbalanced. We continue until all characters are read. At the end, if the stack is empty, it means all brackets matched properly, so balanced. Otherwise, unbalanced. The execution table shows step-by-step how the stack changes with each character. The variable tracker shows the stack and current character values after each step. Key moments clarify why we check stack emptiness before popping, why mismatches cause failure, and why the stack must be empty at the end. The quiz tests understanding of stack states at different steps and when failure occurs.

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