Balanced Parentheses Problem Using Stack in DSA C++ - Execution Trace

Concept Flow - Balanced Parentheses Problem Using Stack

Start

↓

Read next char

↓

Is char '(' or '{' or '['?

Yes→Push to stack

↓

Is char ')' or '}' or '

↓

Stack empty?

Yes→Unbalanced

↓

Pop from stack

↓

Does popped match char?

↓

Unbalanced

↓

More chars?

Yes→Read next char

No↓

Stack empty?

Yes→Balanced

No↓

Unbalanced

The flow reads each character, pushes opening brackets onto the stack, pops and checks matching for closing brackets, and finally checks if stack is empty to decide balanced or not.

Execution Sample

DSA C++

string code = "()[]{}";
stack<char> s;
for (char c : code) {
  if (c=='('||c=='{'||c=='[') s.push(c);
  else {
    if (s.empty() || !matches(s.top(), c)) return false;
    s.pop();
  }
}
return s.empty();

Checks if the string of parentheses is balanced using a stack.

Execution Table

Step	Operation	Current Char	Stack Before	Stack After	Action	Visual State
1	Read char	(		(	Push '('	( ) [] {}
2	Read char	)	(		Pop '(' and match with ')'	[] [] {}
3	Read char	[		[	Push '['	[] [ ] {}
4	Read char	]	[		Pop '[' and match with ']'	[] [] {}
5	Read char	{		{	Push '{'	[] [] { }
6	Read char	}	{		Pop '{' and match with '}'	[] [] []
7	End of string				Stack empty, balanced	[]

💡 All characters processed and stack is empty, so parentheses are balanced.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
stack		(		[		{
current_char	none	(	)	[	]	{	}	none

Key Moments - 3 Insights

Why do we check if the stack is empty before popping when we see a closing bracket?

Because if the stack is empty, it means there is no matching opening bracket for this closing one, so the string is unbalanced. See step 4 where stack is checked before pop.

Why do we push only opening brackets onto the stack?

Because only opening brackets need to be matched later. Closing brackets trigger popping and matching. See steps 1, 3, and 5 where push happens only for '(', '[', '{'.

What does it mean if the stack is not empty after processing all characters?

It means there are unmatched opening brackets left, so the parentheses are unbalanced. See step 7 where stack emptiness decides the result.

Visual Quiz - 3 Questions

Look at the execution table, what is the stack content after step 3?

A ['(']

B ['[']

C []

D ['{']

💡 Hint

Check the 'Stack After' column in row with Step 3.

At which step does the stack become empty for the first time?

A Step 2

B Step 4

C Step 6

D Step 7

💡 Hint

Look at 'Stack After' column and find first empty stack.

If the input string was "([)]", at which step would the algorithm detect unbalanced parentheses?

A After reading ']'

B After reading ')'

C After reading '['

D After reading '('

💡 Hint

Think about when popping from stack and matching fails, see matching logic in execution.

Concept Snapshot

Balanced Parentheses Using Stack:
- Push opening brackets '(' '{' '[' onto stack
- On closing brackets ')', '}', ']', pop and check match
- If mismatch or stack empty on pop, unbalanced
- After processing all chars, if stack empty → balanced
- Else → unbalanced

Full Transcript

This concept uses a stack to check if parentheses in a string are balanced. We read each character: if it is an opening bracket, we push it onto the stack. If it is a closing bracket, we check if the stack is empty; if yes, it's unbalanced. Otherwise, we pop the top and check if it matches the closing bracket. If not, unbalanced. After processing all characters, if the stack is empty, the parentheses are balanced; otherwise, they are not.

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