Balanced Parentheses Problem Using Stack in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced Parentheses Check

What is the output of the following C code that checks if the parentheses in the string are balanced?

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; i < strlen(expr); i++) {
        char ch = expr[i];
        if (ch == '(') {
            stack[++top] = ch;
        } else if (ch == ')') {
            if (top == -1) return 0;
            top--;
        }
    }
    return top == -1;
}

int main() {
    char expr[] = "((())())";
    if (isBalanced(expr))
        printf("Balanced\n");
    else
        printf("Not Balanced\n");
    return 0;
}

A Not Balanced

B Runtime Error

C Compilation Error

D Balanced

💡 Hint

Check how the stack is used to track opening parentheses and matched with closing ones.

The code uses a stack to push '(' characters and pop when ')' is found. If the stack is empty at the end, parentheses are balanced.

❓ Predict Output

intermediate

Output for Unbalanced Parentheses

What will the following C program print when checking the string "(()" for balanced parentheses?

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; i < strlen(expr); i++) {
        char ch = expr[i];
        if (ch == '(') {
            stack[++top] = ch;
        } else if (ch == ')') {
            if (top == -1) return 0;
            top--;
        }
    }
    return top == -1;
}

int main() {
    char expr[] = "(()";
    if (isBalanced(expr))
        printf("Balanced\n");
    else
        printf("Not Balanced\n");
    return 0;
}

A Compilation Error

B Balanced

C Not Balanced

D Runtime Error

💡 Hint

Count how many '(' are left unmatched at the end.

The stack will have one '(' left unmatched, so the function returns 0 and prints "Not Balanced".

🧠 Conceptual

advanced

Why Use a Stack for Balanced Parentheses?

Why is a stack the best data structure to check for balanced parentheses in an expression?

A Because it allows checking pairs in the correct nested order using Last-In-First-Out behavior

B Because it stores all characters and sorts them alphabetically

C Because it uses First-In-First-Out behavior like a queue

D Because it can store unlimited characters without memory limits

💡 Hint

Think about how parentheses open and close in nested order.

A stack follows Last-In-First-Out (LIFO), which matches how the most recent '(' must be closed first by a ')'.

🔧 Debug

advanced

Find the Bug in Parentheses Checker

What error will the following code produce when checking the string ")(" for balanced parentheses?

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; i < strlen(expr); i++) {
        char ch = expr[i];
        if (ch == '(') {
            stack[++top] = ch;
        } else if (ch == ')') {
            top--;
        }
    }
    return top == -1;
}

int main() {
    char expr[] = ")(";
    if (isBalanced(expr))
        printf("Balanced\n");
    else
        printf("Not Balanced\n");
    return 0;
}

A The code will cause a compilation error

B The code will cause a stack underflow (access invalid index)

C The code will print "Balanced"

D The code will print "Not Balanced"

💡 Hint

Look at what happens when ')' is found but stack is empty.

The code decrements top without checking if the stack is empty, causing top to become -2 and invalid memory access.

🚀 Application

expert

Count Balanced Parentheses Substrings

Given the string "()()()", how many balanced parentheses substrings of length 2 are there?

A 3

B 2

C 1

D 0

💡 Hint

Look for every pair of characters that form "()".

Substrings of length 2 are: "()", "()", "()" at positions 0-1, 2-3, 4-5 respectively. All are balanced.

Practice

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

easy

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

B. To count the total number of parentheses in the expression

C. To reverse the order of parentheses in the expression

D. To store only the closing parentheses encountered

Solution

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

   A stack helps to remember the last opening parenthesis to match it with the next closing one.

2. Step 2: Identify why other options are incorrect

   Counting or reversing parentheses does not solve matching pairs; storing only closing parentheses misses the matching logic.

3. Final Answer:

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

4. Quick Check:

   Stack tracks openings for matching = B [OK]

Hint: Stack remembers last opening bracket for matching [OK]

Common Mistakes:

• Thinking stack counts parentheses instead of matching
• Using stack to store only closing parentheses
• Ignoring order of parentheses

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

easy

A. push(stack, '(');

B. stack.push('(');

C. stack->push('(');

D. push('(', stack);

Solution

1. Step 1: Recognize typical C stack push syntax

   In C, stack operations are usually functions like push(stack, element).

2. Step 2: Analyze each option

   push(stack, '('); matches the common C function call syntax. Options B and C use dot or arrow notation typical in C++ or OOP, not plain C. push('(', stack); has arguments reversed.

3. Final Answer:

   push(stack, '('); -> Option A

4. Quick Check:

   C stack push syntax = A [OK]

Hint: In C, use push(stack, element) function call [OK]

Common Mistakes:

• Using C++ style stack.push() in C
• Reversing arguments in push function
• Using arrow operator on non-pointer stack

3. What will be the output of the following C code snippet that checks balanced parentheses?

char expr[] = "({[]})";
int result = isBalanced(expr);
printf("%d", result);

Assume isBalanced returns 1 if balanced, 0 otherwise.

medium

A. Runtime error

B. 0

C. Compilation error

D. 1

Solution

1. Step 1: Analyze the expression "({[]})"

   The expression has matching pairs: '(' with ')', '{' with '}', '[' with ']'. All are properly nested.

2. Step 2: Understand isBalanced function behavior

   Since the expression is balanced, isBalanced returns 1, so printf prints 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Balanced expression returns 1 = A [OK]

Hint: Balanced nested pairs return 1 from isBalanced [OK]

Common Mistakes:

• Assuming only () pairs are valid
• Confusing balanced with equal count
• Expecting 0 for nested but balanced

4. Identify the bug in this C function snippet for checking balanced parentheses:

int isBalanced(char* expr) {
  Stack s;
  for (int i = 0; expr[i] != '\0'; i++) {
    if (expr[i] == '(') push(&s, '(');
    else if (expr[i] == ')') {
      if (isEmpty(&s)) return 0;
      pop(&s);
    }
  }
  return isEmpty(&s);
}

medium

A. Return statement should be inside the loop

B. Stack s is not initialized before use

C. pop() is called without checking if stack is empty

D. The function does not check for other types of brackets

Solution

1. Step 1: Check stack initialization

   The stack variable 's' is declared but not initialized, so push/pop operations may fail.

2. Step 2: Verify other parts

   Other options are less critical: checking only () is a limitation but not a bug; pop is called after empty check; return outside loop is correct.

3. Final Answer:

   Stack s is not initialized before use -> Option B

4. Quick Check:

   Uninitialized stack causes errors = D [OK]

Hint: Always initialize stack before push/pop [OK]

Common Mistakes:

• Ignoring stack initialization
• Assuming pop safe without empty check
• Thinking return must be inside loop

5. Given the expression "[{()}](({}))", which of the following modifications to the isBalanced function will correctly handle all types of brackets: (), {}, and []?

hard

A. Ignore brackets inside quotes and only check outer brackets

B. Count total opening and closing brackets separately and compare counts

C. Push opening brackets and check matching closing brackets by popping and comparing types

D. Replace all brackets with parentheses before checking

Solution

1. Step 1: Understand bracket matching logic

   To handle multiple bracket types, push opening brackets and on closing bracket, pop and check if types match.

2. Step 2: Evaluate other options

   Counting brackets ignores order; ignoring brackets inside quotes is unrelated; replacing brackets loses type info.

3. Final Answer:

   Push opening brackets and check matching closing brackets by popping and comparing types -> Option C

4. Quick Check:

   Match types by push/pop for all brackets = C [OK]

Hint: Match each closing bracket with last opening of same type [OK]

Common Mistakes:

• Counting brackets without order check
• Ignoring bracket types
• Replacing brackets loses matching info