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 <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(') {
            st.push(c);
        } else if (c == ')') {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    std::string expr = "(()())";
    if (isBalanced(expr)) {
        std::cout << "Balanced" << std::endl;
    } else {
        std::cout << "Not Balanced" << std::endl;
    }
    return 0;
}

A Runtime Error

B Not Balanced

C Balanced

D Compilation Error

💡 Hint

Check how the stack is used to match opening and closing parentheses.

The code pushes '(' onto the stack and pops when it finds ')'. The string "(()())" is balanced, so the stack is empty at the end, resulting in "Balanced" output.

🧠 Conceptual

intermediate

Understanding Stack Usage in Balanced Parentheses

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

A Because it stores all parentheses in sorted order automatically.

B Because it allows checking the last opened parenthesis first, matching the last-in, first-out order needed.

C Because it uses less memory than arrays for this problem.

D Because it can count the total number of parentheses without iteration.

💡 Hint

Think about how parentheses must close in the reverse order they open.

A stack follows last-in, first-out order, which matches how parentheses must be closed in reverse order of opening. This makes it ideal for this problem.

🔧 Debug

advanced

Identify the Error in Parentheses Checking Code

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

DSA C++

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(') {
            st.push(c);
        } else if (c == ')') {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return true;
}

int main() {
    std::string expr = "(()";
    if (isBalanced(expr)) {
        std::cout << "Balanced" << std::endl;
    } else {
        std::cout << "Not Balanced" << std::endl;
    }
    return 0;
}

A The code causes a compilation error due to missing header files.

B The code prints "Not Balanced" correctly because the stack is empty at the end.

C The code causes a runtime error due to popping from an empty stack.

D The code prints "Balanced" incorrectly because it does not check if the stack is empty at the end.

💡 Hint

Check the return statement of the function and what it means for leftover opening parentheses.

The function returns true without checking if the stack is empty at the end, so leftover '(' are ignored, causing incorrect "Balanced" output.

❓ Predict Output

advanced

Output of Balanced Parentheses with Multiple Types

What is the output of this C++ code that checks balanced parentheses, brackets, and braces?

DSA C++

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            if ((c == ')' && top == '(') ||
                (c == '}' && top == '{') ||
                (c == ']' && top == '[')) {
                st.pop();
            } else {
                return false;
            }
        }
    }
    return st.empty();
}

int main() {
    std::string expr = "[{()}]";
    std::cout << (isBalanced(expr) ? "Balanced" : "Not Balanced") << std::endl;
    return 0;
}

A Balanced

B Not Balanced

C Compilation Error

D Runtime Error

💡 Hint

Check matching pairs for all three types of brackets.

The string "[{()}]" is correctly nested with matching pairs, so the output is "Balanced".

🧠 Conceptual

expert

Time Complexity of Balanced Parentheses Algorithm

What is the time complexity of checking balanced parentheses using a stack for a string of length n?

A O(n), because each character is processed once with push or pop operations.

B O(n^2), because nested loops are needed to match parentheses.

C O(log n), because the stack operations are logarithmic.

D O(1), because the stack size is fixed.

💡 Hint

Consider how many times each character is visited and how costly stack operations are.

Each character is processed once, and stack push/pop operations are O(1), so total time is O(n).

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

B. To sort the parentheses in ascending order

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

D. To reverse the order of parentheses

Solution

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

   A stack stores opening parentheses as they appear, so we can check if each closing parenthesis matches the last opened one.

2. Step 2: Explain why other options are incorrect

   Sorting or counting parentheses does not help in matching pairs correctly. Reversing order is unrelated to matching.

3. Final Answer:

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

4. Quick Check:

   Stack matches parentheses pairs = C [OK]

Hint: Stack stores last opened parenthesis to match closing one [OK]

Common Mistakes:

• Thinking stack sorts parentheses
• Using stack to count parentheses only
• Ignoring order of parentheses

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

easy

A. st.push(')');

B. st.push("(");

C. st.push((int)'(');

D. st.push('(');

Solution

1. Step 1: Identify correct syntax for pushing a char onto stack

   In C++, single quotes denote a char literal. So st.push('('); correctly pushes the '(' character.

2. Step 2: Explain why other options are incorrect

   st.push("("); uses double quotes which is a string, not char. st.push((int)'('); uses wrong cast to int for char stack. st.push(')'); pushes a closing parenthesis, not opening.

3. Final Answer:

   st.push('('); -> Option D

4. Quick Check:

   Use single quotes for char push = A [OK]

Hint: Use single quotes for chars in C++ stack push [OK]

Common Mistakes:

• Using double quotes instead of single quotes
• Pushing wrong parenthesis character
• Using wrong cast type

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

std::stack<char> st;
std::string s = "({[]})";
for(char c : s) {
  if(c == '(' || c == '{' || c == '[') st.push(c);
  else {
    if(st.empty()) { std::cout << "Not Balanced"; return 0; }
    char top = st.top(); st.pop();
    if((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
      std::cout << "Not Balanced"; return 0;
    }
  }
}
if(st.empty()) std::cout << "Balanced";
else std::cout << "Not Balanced";

medium

A. Balanced

B. Not Balanced

C. Compilation Error

D. Runtime Error

Solution

1. Step 1: Trace the loop for each character in the string

   Opening brackets are pushed onto the stack. For each closing bracket, the code checks if the top matches the corresponding opening bracket. The string "({[]})" is perfectly balanced.

2. Step 2: Check stack emptiness after loop

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

3. Final Answer:

   Balanced -> Option A

4. Quick Check:

   Matching pairs and empty stack = Balanced [OK]

Hint: Stack empty after matching means balanced parentheses [OK]

Common Mistakes:

• Not checking stack empty at end
• Mismatching pairs logic
• Ignoring early return on mismatch

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

std::stack<char> st;
std::string s = "(()";
for(char c : s) {
  if(c == '(') st.push(c);
  else if(c == ')') {
    if(st.empty()) return false;
    st.pop();
  }
}
return true;

medium

A. Pushes closing parentheses onto stack

B. Does not check if stack is empty after loop

C. Uses wrong data type for stack

D. Returns true too early inside loop

Solution

1. Step 1: Analyze loop behavior on input "(()"

   Two '(' are pushed, one ')' pops one '('. After loop, one '(' remains on stack.

2. Step 2: Check final return statement

   Code returns true without checking if stack is empty, so it incorrectly says balanced.

3. Final Answer:

   Does not check if stack is empty after loop -> Option B

4. Quick Check:

   Final stack empty check missing = A [OK]

Hint: Always check stack empty after processing all characters [OK]

Common Mistakes:

• Missing final stack empty check
• Returning inside loop incorrectly
• Pushing wrong characters

5. Given the string s = "[{()}]({[]})", which of the following modifications to the balanced parentheses algorithm will correctly handle this input and also ignore any non-parenthesis characters like letters or digits?

hard

A. Add a condition to skip characters that are not '(', ')', '{', '}', '[' or ']'

B. Push all characters onto the stack regardless of type

C. Remove the stack and just count opening and closing parentheses

D. Only check the first half of the string for balanced parentheses

Solution

1. Step 1: Understand the need to ignore non-parenthesis characters

   To handle strings with other characters, the algorithm must skip them and only process parentheses.

2. Step 2: Explain why other options fail

   Pushing all characters breaks logic. Counting only is insufficient. Checking half string misses pairs.

3. Final Answer:

   Add a condition to skip characters that are not '(', ')', '{', '}', '[' or ']' -> Option A

4. Quick Check:

   Process only parentheses characters = D [OK]

Hint: Process only parentheses characters, skip others [OK]

Common Mistakes:

• Pushing non-parenthesis chars onto stack
• Counting parentheses without matching pairs
• Checking only part of the string