Balanced Parentheses Problem Using Stack in DSA C#

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 you are stacking plates; each time you see an opening bracket, you put a plate on the stack, and each closing bracket means you take the top plate off and check if it matches.

Stack: [] (empty)
Expression: ( [ { } ] )
↑ (start reading from left)

Dry Run Walkthrough

Input: expression: "({[]})"

Goal: Check if the parentheses in the expression are balanced and correctly nested

Step 1: Read '(' and push it onto the stack

Stack: ['(']
Expression: ({[]}) ↑

Why: We store the opening bracket to match it later with a closing one

Step 2: Read '{' and push it onto the stack

Stack: ['(', '{']
Expression: ({[]}) ↑

Why: Another opening bracket, so we add it to the stack

Step 3: Read '[' and push it onto the stack

Stack: ['(', '{', '[']
Expression: ({[]}) ↑

Why: Keep track of nested opening brackets

Step 4: Read ']' and check top of stack; top is '[' so pop it

Stack: ['(', '{']
Expression: ({[]}) ↑

Why: Closing bracket matches last opening bracket, so remove it

Step 5: Read '}' and check top of stack; top is '{' so pop it

Stack: ['(']
Expression: ({[]}) ↑

Why: Closing bracket matches last opening bracket, so remove it

Step 6: Read ')' and check top of stack; top is '(' so pop it

Stack: []
Expression: ({[]}) ↑

Why: Closing bracket matches last opening bracket, so remove it

Result:

Stack: []
All brackets matched, expression is balanced

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class BalancedParentheses
{
    public static bool IsBalanced(string expression)
    {
        Stack<char> stack = new Stack<char>();
        foreach (char ch in expression)
        {
            if (ch == '(' || ch == '{' || ch == '[')
            {
                stack.Push(ch); // push opening bracket
            }
            else if (ch == ')' || ch == '}' || ch == ']')
            {
                if (stack.Count == 0) return false; // no matching opening
                char top = stack.Pop(); // pop last opening
                if (!IsMatchingPair(top, ch)) return false; // mismatch
            }
        }
        return stack.Count == 0; // true if all matched
    }

    private static bool IsMatchingPair(char open, char close)
    {
        return (open == '(' && close == ')') ||
               (open == '{' && close == '}') ||
               (open == '[' && close == ']');
    }

    static void Main()
    {
        string expression = "({[]})";
        bool result = IsBalanced(expression);
        Console.WriteLine(result ? "Balanced" : "Not Balanced");
    }
}

stack.Push(ch); // push opening bracket

Add opening bracket to stack to track it

if (stack.Count == 0) return false; // no matching opening

If closing bracket found but stack empty, no match possible

char top = stack.Pop(); // pop last opening

Remove last opening bracket to check match

if (!IsMatchingPair(top, ch)) return false; // mismatch

Check if popped opening matches current closing bracket

return stack.Count == 0; // true if all matched

If stack empty at end, all brackets matched

Output

Balanced

Complexity Analysis

Time: O(n) because we scan each character once

Space: O(n) because in worst case all characters are opening brackets stored in stack

vs Alternative: Compared to checking pairs by scanning multiple times, stack approach is efficient and linear

Edge Cases

Empty string

Returns true because no brackets means balanced

DSA C#

return stack.Count == 0; // true if all matched

String with only opening brackets

Returns false because stack not empty at end

DSA C#

return stack.Count == 0; // true if all matched

String with closing bracket but no opening

Returns false immediately when stack is empty and closing bracket found

DSA C#

if (stack.Count == 0) return false; // no matching opening

When to Use This Pattern

When you see a problem asking if brackets or symbols are properly matched and nested, use a stack to track openings and verify closings.

Common Mistakes

Mistake: Not checking if stack is empty before popping on closing bracket
Fix: Add a condition to return false if stack is empty before popping

Mistake: Not verifying that the popped opening bracket matches the closing bracket
Fix: Use a helper function to check matching pairs and return false if mismatch

Summary

Checks if every opening bracket has a matching closing bracket in correct order.

Use when you need to validate expressions with nested brackets or symbols.

The stack holds opening brackets and ensures closings match the most recent opening.

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