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.