Balanced Parentheses Problem Using Stack in DSA C++

Mental Model

We use a stack to keep track of opening brackets and check if each closing bracket matches the last opened one.

Analogy: Imagine stacking plates: you put a plate on top for every opening bracket, and remove the top plate when you see a matching closing bracket. If plates match perfectly, the stack ends empty.

Stack (top at right): []
Expression: ({[]})

Initial: Stack: empty

When '(' comes: Stack: ( ->
When '{' comes: Stack: ( -> { ->
When '[' comes: Stack: ( -> { -> [ ->

Dry Run Walkthrough

Input: expression: "({[]})"

Goal: Check if the expression has balanced parentheses

Step 1: Read '(' and push it onto the stack

Stack: (

Why: Opening bracket must be remembered to match later

Step 2: Read '{' and push it onto the stack

Stack: ( -> {

Why: Another opening bracket to match later

Step 3: Read '[' and push it onto the stack

Stack: ( -> { -> [

Why: Keep track of nested opening bracket

Step 4: Read ']' and pop from stack, check if top is '['

Stack: ( -> {

Why: Closing bracket must match last opening bracket

Step 5: Read '}' and pop from stack, check if top is '{'

Stack: (

Why: Match closing bracket with last opening

Step 6: Read ')' and pop from stack, check if top is '('

Stack: empty

Why: All brackets matched so far

Result:

Stack: empty
Expression is balanced

Annotated Code

DSA C++

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

bool isBalanced(const std::string& expr) {
    std::stack<char> s;
    for (char ch : expr) {
        if (ch == '(' || ch == '{' || ch == '[') {
            s.push(ch); // push opening bracket
        } else {
            if (s.empty()) return false; // no matching opening
            char top = s.top();
            if ((ch == ')' && top == '(') ||
                (ch == '}' && top == '{') ||
                (ch == ']' && top == '[')) {
                s.pop(); // matched pair, pop
            } else {
                return false; // mismatch
            }
        }
    }
    return s.empty(); // balanced if stack empty
}

int main() {
    std::string expr = "({[]})";
    if (isBalanced(expr)) {
        std::cout << "Expression is balanced\n";
    } else {
        std::cout << "Expression is not balanced\n";
    }
    return 0;
}

if (ch == '(' || ch == '{' || ch == '[') { s.push(ch); }

push opening bracket onto stack to remember it

if (s.empty()) return false;

if closing bracket found but stack empty, no match possible

if ((ch == ')' && top == '(') || (ch == '}' && top == '{') || (ch == ']' && top == '[')) { s.pop(); } else { return false; }

check if closing bracket matches last opening; pop if yes, else fail

return s.empty();

if stack empty at end, all brackets matched

Output

Expression is balanced

Complexity Analysis

Time: O(n) because we scan each character once

Space: O(n) in worst case if all characters are opening brackets stored in stack

vs Alternative: Without stack, checking balance would require complex counting or recursion, which is less efficient and harder to implement

Edge Cases

empty string

returns true because no brackets means balanced

DSA C++

return s.empty();

string with only opening brackets like "((("

returns false because stack not empty at end

DSA C++

return s.empty();

string with closing bracket first like ")("

returns false because stack empty when closing bracket found

DSA C++

if (s.empty()) return false;

When to Use This Pattern

When you see a problem asking if brackets or symbols are correctly paired and nested, use the stack pattern to track opening symbols and match them with closing ones.

Common Mistakes

Mistake: Not checking if stack is empty before popping
Fix: Always check if stack is empty before accessing top or popping to avoid errors

Mistake: Popping stack without verifying matching bracket
Fix: Check if the top of stack matches the closing bracket before popping

Summary

Checks if every opening bracket has a matching closing bracket in correct order using a stack.

Use when you need to verify balanced and properly nested parentheses or brackets in expressions.

The key insight is to push opening brackets and pop only when a matching closing bracket appears, ensuring order and pairing.

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