Balanced Parentheses Problem Using Stack in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to push an opening parenthesis onto the stack.

DSA C++

if (ch == '(') {
    stack.[1](ch);
}

Drag options to blanks, or click blank then click option'

Aempty

Bpush

Ctop

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() instead of push() to add elements.

Trying to access top() to add elements.

Using empty() which checks if stack is empty.

We use push() to add an element to the top of the stack.

2fill in blank

medium

Complete the code to check if the stack is empty before popping.

DSA C++

if (!stack.[1]()) {
    stack.pop();
}

Drag options to blanks, or click blank then click option'

Apush

Btop

Csize

Dempty

Attempts:

3 left

💡 Hint

Common Mistakes

Using top() which returns the top element, not a boolean.

Using size() which returns a number, not a boolean.

Using push() which adds elements instead of checking.

empty() returns true if the stack has no elements, so !empty() means stack is not empty.

3fill in blank

hard

Fix the error in the condition to match closing parentheses correctly.

DSA C++

if (ch == ')' && stack.[1]() == '(') {
    stack.pop();
}

Drag options to blanks, or click blank then click option'

Asize

Bempty

Ctop

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using empty() which returns a boolean, not the element.

Using size() which returns the number of elements.

Using push() which adds elements instead of checking.

top() returns the element at the top of the stack to compare with '('.

4fill in blank

hard

Fill both blanks to check for matching pairs of brackets.

DSA C++

if (ch == '[1]' && stack.top() == '[2]') {
    stack.pop();
}

Drag options to blanks, or click blank then click option'

A)

B]

C(

D[

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping opening and closing brackets.

Using brackets of different types incorrectly.

Checking wrong pairs like '(' with ']'

')' matches with '(' and ']' matches with '['. Here we check for parentheses pair.

5fill in blank

hard

Complete the code to complete the code snippet that counts bracket types.

DSA C++

std::map<char, int> counts;
for (char ch : input) {
    if (ch == '(' || ch == ')') {
        counts[ch][1];
    }
}

Drag options to blanks, or click blank then click option'

A(

B)

C++

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using decrement -- instead of increment ++.

Counting wrong bracket types.

Using wrong characters in conditions.

We count '(' and ')' characters by incrementing their counts in the map.

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