Balanced Parentheses Problem Using Stack in DSA C - Execution Trace

Concept Flow - Balanced Parentheses Problem Using Stack

Start

↓

Read next character

↓

Is it an opening bracket?

Yes→Push to stack

↓

Stack updated

↓

Is it a closing bracket?

Yes→Is stack empty?

↓

Pop from stack

↓

Ignore other chars

↓

Stack updated

↓

More characters?

Yes→Repeat

↓

End

↓

Is stack empty?

Yes→Balanced

The flow reads each character, pushes opening brackets onto the stack, pops for matching closing brackets, and checks stack emptiness at the end to decide balance.

Execution Sample

DSA C

#include <stdio.h>
#include <string.h>
#define MAX 100

int isBalanced(char *expr) {
    char stack[MAX];
    int top = -1;
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        if (c == '(' || c == '{' || c == '[') {
            stack[++top] = c;
        } else if (c == ')' || c == '}' || c == ']') {
            if (top == -1) return 0;
            char topChar = stack[top--];
            if ((c == ')' && topChar != '(') ||
                (c == '}' && topChar != '{') ||
                (c == ']' && topChar != '['))
                return 0;
        }
    }
    return top == -1;
}

This code checks if the input string has balanced parentheses using a stack.

Execution Table

Step	Operation	Current Char	Stack Before	Stack After	Pointer Changes	Visual State
1	Read char	(		(	top: -1 -> 0	( ) -> ( )
2	Push	(	(	((	top: 0 -> 1	( ( )
3	Read char	)	((	(	top: 1 -> 0	( )
4	Pop and match	)	((	(	top: 1 -> 0	( )
5	Read char	[	(	([	top: 0 -> 1	( [ )
6	Push	[	([	([	top: 1 -> 1	( [ )
7	Read char	]	([	(	top: 1 -> 0	( )
8	Pop and match	]	([	(	top: 1 -> 0	( )
9	Read char	{	(	({	top: 0 -> 1	( { )
10	Push	{	({	({	top: 1 -> 1	( { )
11	Read char	}	({	(	top: 1 -> 0	( )
12	Pop and match	}	({	(	top: 1 -> 0	( )
13	End of string		(	(	top: 0	( )
14	Check stack empty		(	(	top: 0	Stack not empty - Unbalanced

💡 Stack not empty at end means parentheses are unbalanced.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
top	-1	0	0	1	0	1	0	0
stack	""	"("	"("	"(["	"("	"({"	"("	"("

Key Moments - 3 Insights

Why do we push only opening brackets onto the stack?

Because opening brackets mark places where we expect matching closing brackets later. This is shown in execution_table steps 1, 5, and 9 where '(' '[' '{' are pushed.

What happens if we find a closing bracket but the stack is empty?

It means there is no matching opening bracket, so the expression is unbalanced. This is checked in the code and would cause an immediate return 0, as seen in execution_table step 4 if top was -1.

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

If the stack is not empty, it means some opening brackets were never matched. Execution_table step 14 shows this final check.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the stack content after reading '['?

A "(("

B "(["

C "("

D "["

💡 Hint

Refer to the 'Stack After' column in execution_table row 5.

At which step does the stack pointer 'top' first return to 0 after being incremented?

A Step 11

B Step 7

C Step 3

D Step 14

💡 Hint

Check variable_tracker for 'top' values after each step.

If the input string ended after step 11, what would the final stack state be?

A Stack with one '('

B Empty stack

C Stack with one '{'

D Stack with '(' and '{'

💡 Hint

Look at execution_table step 13 and variable_tracker final stack content.

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, unbalanced.
- At end, stack empty means balanced.
- Use stack pointer 'top' to track stack state.

Full Transcript

This visualization shows how to check balanced parentheses using a stack. We read each character of the input string. When we see an opening bracket like '(', '{', or '[', we push it onto the stack. When we see a closing bracket like ')', '}', or ']', we check if the stack is empty. If empty, it means no matching opening bracket, so the string is unbalanced. Otherwise, we pop the top of the stack and check if it matches the closing bracket. If it does not match, the string is unbalanced. After processing all characters, if the stack is empty, the parentheses are balanced; if not, they are unbalanced. The execution table shows each step with the stack content and pointer changes. The variable tracker shows how the stack pointer 'top' and stack content change over time. Key moments clarify why we push only opening brackets, what happens if the stack is empty on closing bracket, and why we check stack emptiness at the end. The quiz tests understanding of stack content and pointer changes at specific steps.