Balanced Parentheses Problem Using Stack in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

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

beginner

Which characters are typically checked in the Balanced Parentheses Problem?

Opening characters like '(', '{', '[' and their corresponding closing characters ')', '}', ']' are checked for correct matching.

beginner

What happens if a closing parenthesis is found but the stack is empty?

It means there is no matching opening parenthesis, so the parentheses are not balanced.

intermediate

Why do we check the top of the stack when a closing parenthesis is found?

Because the top of the stack holds the most recent unmatched opening parenthesis, which should match the current closing parenthesis.

beginner

What does it mean if the stack is not empty after processing the entire string?

It means there are unmatched opening parentheses left, so the parentheses are not balanced.

What data structure is best suited for checking balanced parentheses?

A Queue

B Linked List

C Array

D Stack

A stack follows Last-In-First-Out order, which matches how parentheses must be closed in reverse order.

What should you do when you encounter an opening parenthesis in the string?

A Push it onto the stack

B Pop from the stack

C Ignore it

D Replace it with a closing parenthesis

Opening parentheses are pushed onto the stack to wait for their matching closing parentheses.

If the current character is a closing parenthesis, what is the first step?

A Push it onto the stack

B Check if the stack is empty

C Ignore it

D Add it to the output

If the stack is empty, there is no matching opening parenthesis, so the string is unbalanced.

Which of these pairs is NOT a matching pair of parentheses?

A (]

B {}

C []

D ()

The pair '(]' mixes different types and is not a valid matching pair.

What does it mean if after processing the entire string, the stack is empty?

A There were no parentheses

B Parentheses are unbalanced

C Parentheses are balanced

D The string is empty

An empty stack means all opening parentheses were matched and closed properly.

Explain step-by-step how a stack is used to check if parentheses in a string are balanced.

Think about how you match pairs in reverse order.

Describe what conditions cause the parentheses to be considered unbalanced when using a stack.

Consider what happens when matches fail or remain unmatched.

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