Balanced Parentheses Problem Using Stack in DSA C# - Execution Trace

Concept Flow - Balanced Parentheses Problem Using Stack

Start

↓

Read next character

↓

Is character '(' or opening bracket?

Yes→Push to stack

No↓

Is character ')' or closing bracket?

Yes→Stack empty?

↓

Pop from stack

↓

More characters?

Yes→Read next character

No↓

Stack empty?

Yes→Balanced

No↓

Unbalanced

↓

End

We read each character, push opening brackets on stack, pop for closing brackets, and check stack emptiness to decide balance.

Execution Sample

DSA C#

string input = "(()[])";
Stack<char> stack = new Stack<char>();
foreach (char c in input) {
  if (c == '(' || c == '[') stack.Push(c);
  else if (c == ')') {
    if (stack.Count == 0 || stack.Pop() != '(') return false;
  } else if (c == ']') {
    if (stack.Count == 0 || stack.Pop() != '[') return false;
  }
}
return stack.Count == 0;

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

Execution Table

Step	Operation	Character	Stack Before	Stack After	Visual State
1	Read character	(		(	( )
2	Read character	(	(	(, (	( ( )
3	Read character	)	(, (	(	( )
4	Read character	[	(	(, [	( [ )
5	Read character	]	(, [	(	( )
6	Read character	)	(
7	End of input	-			Empty stack means balanced

💡 Stack is empty after processing all characters, so parentheses are balanced.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
stack		(	(, (	(	(, [	(
input	"(()[])"	"(()[])"	"(()[])"	"(()[])"	"(()[])"	"(()[])"	"(()[])"	"(()[])"

Key Moments - 3 Insights

Why do we push only opening brackets and pop on closing brackets?

Because opening brackets mark places to match later. When we see a closing bracket, we pop the last opening bracket to check if it matches. See execution_table steps 1, 2 (push) and 3, 5, 6 (pop).

What happens if we try to pop from an empty stack?

It means there's a closing bracket without a matching opening bracket, so the string is unbalanced. In execution_table step 3, if stack was empty, we would stop and say unbalanced.

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

If stack is not empty, it means some opening brackets were never matched by closing ones. In execution_table step 7, empty stack means balanced.

Visual Quiz - 3 Questions

Look at the execution_table, what is the stack after step 4?

A ['(','(']

B ['(']

C ['(', '[']

D []

💡 Hint

Check the 'Stack After' column in row with Step 4.

At which step does the stack become empty again after being non-empty?

A Step 6

B Step 3

C Step 5

D Step 7

💡 Hint

Look for the first step where 'Stack After' is empty after some pushes.

If the input was "(()", what would be the final stack state?

A Empty stack

B Stack with one '('

C Stack with two '('

D Stack with one ')'

💡 Hint

Think about unmatched opening brackets left after processing all characters.

Concept Snapshot

Balanced Parentheses Using Stack:
- Push opening brackets '(' '[' onto stack
- On closing brackets ')' ']', pop stack and check match
- If pop fails or stack not empty at end, unbalanced
- Stack empty at end means balanced
- Works for nested and sequential brackets

Full Transcript

The balanced parentheses problem uses a stack to track opening brackets. We read each character in the input 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 the string is unbalanced. Otherwise, we pop the top of the stack. After processing all characters, if the stack is empty, the parentheses are balanced; if not, they are unbalanced. This method ensures every opening bracket has a matching closing bracket in the correct order.

Practice

1. What is the main purpose of using a stack in the Balanced Parentheses Problem?

easy

A. To count the total number of parentheses in the string

B. To keep track of opening parentheses and match them with closing ones

C. To reverse the order of parentheses in the string

D. To sort the parentheses based on their type

Solution

1. Step 1: Understand the role of stack in parentheses matching

   A stack helps keep track of opening parentheses so that each closing parenthesis can be matched correctly in order.

2. Step 2: Identify why other options are incorrect

   Counting or reversing parentheses does not solve the matching problem, and sorting is unrelated to balance checking.

3. Final Answer:

   To keep track of opening parentheses and match them with closing ones -> Option B

4. Quick Check:

   Stack tracks openings for matching closings [OK]

Hint: Stack stores openings to match closings in order [OK]

Common Mistakes:

• Thinking stack counts parentheses instead of matching
• Confusing stack with queue for this problem
• Assuming stack reverses parentheses order

2. Which of the following C# code snippets correctly pushes an opening parenthesis onto a stack named stack?

easy

A. stack.Push('(');

B. stack.Add('(');

C. stack.Insert('(');

D. stack.Enqueue('(');

Solution

1. Step 1: Recall stack method to add elements

   In C#, the method to add an element to a stack is Push().

2. Step 2: Identify incorrect methods

   Add() and Insert() are not stack methods; Enqueue() is for queues.

3. Final Answer:

   stack.Push('('); -> Option A

4. Quick Check:

   Use Push() to add to stack [OK]

Hint: Use Push() to add elements to stack in C# [OK]

Common Mistakes:

• Using queue methods like Enqueue() on stack
• Trying to use Add() or Insert() which don't exist for stack
• Confusing stack with list methods

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

string input = "({[]})";
Stack<char> stack = new Stack<char>();
foreach (char c in input) {
  if (c == '(' || c == '{' || c == '[') {
    stack.Push(c);
  } else {
    if (stack.Count == 0) {
      Console.WriteLine("Unbalanced");
      return;
    }
    char top = stack.Pop();
    if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
      Console.WriteLine("Unbalanced");
      return;
    }
  }
}
if (stack.Count == 0) Console.WriteLine("Balanced"); else Console.WriteLine("Unbalanced");

medium

A. Runtime Error

B. Unbalanced

C. No Output

D. Balanced

Solution

1. Step 1: Trace the input string character by character

   Opening brackets '(', '{', '[' are pushed onto the stack. Closing brackets pop and check matching. The input "({[]})" is perfectly nested.

2. Step 2: Check stack emptiness after processing

   After processing all characters, stack is empty, so output is "Balanced".

3. Final Answer:

   Balanced -> Option D

4. Quick Check:

   All pairs matched, stack empty = Balanced [OK]

Hint: Match each closing with last opening using stack [OK]

Common Mistakes:

• Not checking stack empty before popping
• Mismatching bracket pairs
• Ignoring stack emptiness at end

4. Identify the bug in the following C# code snippet for checking balanced parentheses:

Stack<char> stack = new Stack<char>();
foreach (char c in input) {
  if (c == '(' || c == '{' || c == '[') {
    stack.Push(c);
  } else {
    char top = stack.Pop();
    if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
      return false;
    }
  }
}
return stack.Count == 0;

medium

A. Not returning true when balanced

B. Incorrect matching of parentheses pairs

C. Missing check if stack is empty before Pop()

D. Using stack.Push() instead of Pop() for closing brackets

Solution

1. Step 1: Check for stack underflow before popping

   The code pops from stack without checking if it's empty, which can cause runtime error if closing bracket appears first.

2. Step 2: Confirm matching logic is correct

   Matching pairs are correctly checked, and return false if mismatch occurs.

3. Final Answer:

   Missing check if stack is empty before Pop() -> Option C

4. Quick Check:

   Always check stack empty before Pop() [OK]

Hint: Check stack empty before Pop() to avoid errors [OK]

Common Mistakes:

• Popping from empty stack causing exceptions
• Ignoring stack.Count == 0 before Pop()
• Confusing Push and Pop methods

5. Given the string "[{()}]({[]})", which of the following modifications to the balanced parentheses algorithm will correctly handle this input and return true?

Options:
A) Ignore all characters except parentheses.
B) Use a stack and match pairs as usual.
C) Use two stacks, one for opening and one for closing parentheses.
D) Use a queue instead of a stack to track parentheses.

hard

A. Use a stack and match pairs as usual.

B. Ignore all characters except parentheses.

C. Use two stacks, one for opening and one for closing parentheses.

D. Use a queue instead of a stack to track parentheses.

Solution

1. Step 1: Understand the input and algorithm

   The input contains only parentheses characters. The standard stack-based matching algorithm works for nested and sequential pairs.

2. Step 2: Evaluate each option's correctness

   Use a stack and match pairs as usual. is correct as it uses the standard stack approach. Ignore all characters except parentheses. is irrelevant since input has only parentheses. Use two stacks, one for opening and one for closing parentheses. complicates unnecessarily. Use a queue instead of a stack to track parentheses. fails because queue does not track last opening bracket.

3. Final Answer:

   Use a stack and match pairs as usual. -> Option A

4. Quick Check:

   Standard stack method handles nested pairs [OK]

Hint: Standard stack method works for all balanced parentheses [OK]

Common Mistakes:

• Trying to use queue which breaks matching order
• Overcomplicating with multiple stacks
• Ignoring characters that are not parentheses