Balanced Parentheses Problem Using Stack in DSA C++ - Deep Dive

Overview - Balanced Parentheses Problem Using Stack

What is it?

Balanced parentheses problem checks if every opening bracket in a string has a matching closing bracket in the correct order. It involves symbols like (), {}, and []. The goal is to ensure the brackets are properly nested and closed. This helps verify if expressions or code blocks are correctly formed.

Why it matters

Without checking balanced parentheses, programs or expressions can have syntax errors causing crashes or wrong results. It helps compilers, calculators, and editors understand the structure of code or math expressions. Without this, software would fail to parse or run code reliably, leading to bugs and confusion.

Where it fits

Before this, learners should know basic data structures like stacks and strings. After this, they can explore parsing algorithms, expression evaluation, and syntax checking in compilers.

Mental Model

Core Idea

Use a stack to track opening brackets and ensure each closing bracket matches the most recent unmatched opening bracket.

Think of it like...

Imagine stacking plates: you put plates on top when you see an opening bracket, and you remove the top plate when you see a closing bracket. If you try to remove a plate when none is left or the plate doesn't match, the stack is unbalanced.

Input: { [ ( ) ] }
Stack operations:
  Read '{' -> push '{'        Stack: { 
  Read '[' -> push '['        Stack: { [ 
  Read '(' -> push '('        Stack: { [ ( 
  Read ')' -> pop '('         Stack: { [ 
  Read ']' -> pop '['         Stack: { 
  Read '}' -> pop '{'         Stack: (empty)
Result: Balanced

Build-Up - 7 Steps

1

Foundation

Understanding Parentheses Types

Concept: Introduce the different types of parentheses and their roles.

There are three common types of parentheses: round (), square [], and curly {}. Each type must be matched with the same type to be balanced. For example, '(' matches only with ')', not with ']' or '}'.

Result

Learner knows the symbols to check and that matching types matter.

Knowing the types prevents mixing different brackets, which is a common source of errors.

2

Foundation

Basics of Stack Data Structure

Concept: Introduce stack as a last-in, first-out container to help track parentheses.

A stack lets you add items on top and remove the most recent item added. Think of it like a pile of books: you can only take the top book off. This behavior fits perfectly for matching parentheses because the last opened bracket must be closed first.

Result

Learner understands why stack is the right tool for this problem.

Recognizing the LIFO nature of stacks aligns perfectly with nested parentheses structure.

3

Intermediate

Algorithm to Check Balanced Parentheses

🤔Before reading on: do you think we should check all characters or only parentheses? Commit to your answer.

Concept: Use stack operations to process the string and verify matching pairs.

1. Scan the string from left to right. 2. When you see an opening bracket, push it onto the stack. 3. When you see a closing bracket, check if the stack is empty. - If empty, it's unbalanced. - Otherwise, pop the top and check if it matches the closing bracket. 4. If all characters are processed and stack is empty, parentheses are balanced. 5. Otherwise, unbalanced.

Result

Algorithm correctly identifies balanced and unbalanced strings.

Understanding the step-by-step process clarifies how the stack tracks unmatched openings.

4

Intermediate

Handling Edge Cases in Parentheses Checking

🤔Before reading on: do you think an empty string is balanced or not? Commit to your answer.

Concept: Consider special cases like empty strings, strings without parentheses, or strings with only one bracket.

Empty string has no parentheses, so it is balanced. Strings with no parentheses are balanced by default. Strings with only one bracket (opening or closing) are unbalanced. Algorithm must handle these gracefully without errors.

Result

Algorithm robustly handles all input variations.

Knowing edge cases prevents bugs and ensures reliable real-world use.

5

Advanced

Implementing Balanced Parentheses in C++

🤔Before reading on: do you think using a standard stack container or a custom array is better? Commit to your answer.

Concept: Write complete C++ code using the standard stack container to solve the problem.

#include #include #include bool isBalanced(const std::string& expr) { std::stack s; for (char ch : expr) { if (ch == '(' || ch == '[' || ch == '{') { s.push(ch); } else if (ch == ')' || ch == ']' || ch == '}') { if (s.empty()) return false; char top = s.top(); s.pop(); if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) { return false; } } } return s.empty(); } int main() { std::string test1 = "{[()]}"; std::string test2 = "{[(])}"; std::cout << (isBalanced(test1) ? "Balanced" : "Not Balanced") << std::endl; std::cout << (isBalanced(test2) ? "Balanced" : "Not Balanced") << std::endl; return 0; }

Result

Output: Balanced Not Balanced

Seeing the full code connects theory to practice and shows how to implement the logic efficiently.

6

Advanced

Time and Space Complexity Analysis

🤔Before reading on: do you think the algorithm runs faster than O(n) or slower? Commit to your answer.

Concept: Analyze how the algorithm performs as input size grows.

The algorithm scans the string once, so time complexity is O(n), where n is string length. Each character is pushed or popped at most once. Space complexity is O(n) in the worst case if all characters are opening brackets.

Result

Learner understands efficiency and resource use of the solution.

Knowing complexity helps predict performance and optimize code for large inputs.

7

Expert

Extending to Custom Bracket Types and Unicode

🤔Before reading on: do you think the same stack approach works for any bracket types? Commit to your answer.

Concept: Adapt the algorithm to handle new bracket types or Unicode symbols.

To support custom brackets, maintain a map of opening to closing brackets. Check matches using this map instead of fixed conditions. For Unicode or other symbols, ensure character encoding is handled correctly. This generalizes the solution for diverse languages or formats.

Result

Algorithm becomes flexible and extensible for real-world applications.

Understanding how to generalize the approach prepares learners for complex parsing tasks.

Under the Hood

The stack stores opening brackets as they appear. When a closing bracket arrives, the algorithm pops the top of the stack and compares. This ensures the most recent opening bracket is matched first, preserving correct nesting. If mismatches or premature closing brackets occur, the stack state reveals imbalance immediately.

Why designed this way?

Stacks naturally model nested structures because they follow last-in, first-out order, matching how parentheses nest. Alternatives like queues or arrays don't capture this nesting order efficiently. This design simplifies checking without backtracking or complex parsing.

Input string: { [ ( ) ] }

┌─────────────┐
│ Start scan │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ Read char   │
└─────┬───────┘
      │
      ▼
┌─────────────┐       ┌───────────────┐
│ Is opening? │──Yes─▶│ Push to stack │
└─────┬───────┘       └──────┬────────┘
      │No                    │
      ▼                      │
┌─────────────┐              │
│ Is closing? │──Yes─────────┘
└─────┬───────┘
      │
      ▼
┌─────────────┐       ┌───────────────┐
│ Stack empty?│──Yes─▶│ Unbalanced    │
└─────┬───────┘       └───────────────┘
      │No
      ▼
┌─────────────┐       ┌───────────────┐
│ Pop from    │       │ Match check   │
│ stack       │──────▶│               │
└─────┬───────┘       └──────┬────────┘
      │                    │
      ▼                    │
┌─────────────┐            │
│ Matches?    │──No───────▶│ Unbalanced    │
└─────┬───────┘            └───────────────┘
      │Yes
      ▼
┌─────────────┐
│ Continue    │
│ scanning    │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ End of input│
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ Stack empty?│
└─────┬───────┘
      │Yes
      ▼
┌─────────────┐
│ Balanced    │
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think a string with only opening brackets is balanced? Commit yes or no.

Common Belief: If all brackets are opening, the string is balanced because no closing brackets break the order.

Reality: A string with only opening brackets is unbalanced because there are no closing brackets to match them.

Why it matters: Assuming this leads to false positives, causing syntax errors to go unnoticed.

Quick: Do you think the order of different bracket types can be mixed and still be balanced? Commit yes or no.

Common Belief: As long as the total number of opening and closing brackets matches, the string is balanced regardless of order.

Reality: The order and nesting must be correct; mismatched or crossed brackets cause imbalance even if counts match.

Why it matters: Ignoring order causes incorrect parsing and runtime errors in code or expressions.

Quick: Do you think using a queue instead of a stack works for this problem? Commit yes or no.

Common Belief: A queue can track brackets just like a stack, so it should work similarly.

Reality: A queue processes elements in first-in, first-out order, which breaks the nesting logic needed for parentheses matching.

Why it matters: Using a queue leads to wrong results and confusion about bracket structure.

Quick: Do you think ignoring non-bracket characters affects the balance check? Commit yes or no.

Common Belief: All characters must be considered for balance, including letters and symbols.

Reality: Non-bracket characters are ignored; only brackets affect balance checking.

Why it matters: Including irrelevant characters complicates the algorithm and causes unnecessary errors.

Expert Zone

1

Handling early termination: stopping the check as soon as imbalance is detected improves efficiency.

2

Using a map or dictionary for bracket pairs allows easy extension to new bracket types without changing core logic.

3

Stack size can be optimized by ignoring non-bracket characters early, reducing memory usage in large inputs.

When NOT to use

This approach is not suitable for languages or formats where brackets can be escaped or ignored conditionally. In such cases, a full parser or lexer with context awareness is needed.

Production Patterns

Used in compilers and interpreters for syntax validation, in code editors for real-time bracket matching, and in calculators to validate mathematical expressions before evaluation.

Connections

Expression Evaluation

Builds-on

Balanced parentheses checking is a prerequisite for safely evaluating arithmetic or logical expressions, ensuring operators and operands are grouped correctly.

Compiler Syntax Analysis

Same pattern

Compilers use similar stack-based methods to parse nested code blocks and ensure correct syntax structure.

Human Language Parsing

Builds-on

Understanding nested structures in language, like clauses or parentheses in sentences, uses concepts similar to balanced parentheses checking.

Common Pitfalls

#1 Not checking if the stack is empty before popping.

Wrong approach:

if (ch == ')' && stack.top() == '(') { stack.pop(); }

Correct approach:

if (!stack.empty() && ch == ')' && stack.top() == '(') { stack.pop(); } else { return false; }

Root cause:

Assuming the stack always has elements leads to runtime errors when popping from an empty stack.

#2 Matching brackets by counting totals instead of order.

Wrong approach:

int open = count('('); int close = count(')'); if (open == close) return true;

Correct approach:

Use stack to check order and nesting, not just counts.

Root cause:

Ignoring order and nesting breaks the logic of balanced parentheses.

#3 Treating all characters as brackets.

Wrong approach:

for (char ch : expr) { stack.push(ch); }

Correct approach:

for (char ch : expr) { if (isOpeningBracket(ch)) stack.push(ch); else if (isClosingBracket(ch)) { /* check stack */ } }

Root cause:

Not filtering characters causes incorrect stack state and false imbalance.

Key Takeaways

Balanced parentheses ensure every opening bracket has a matching closing bracket in the correct order.

Stacks are the perfect data structure because they follow last-in, first-out order matching nested brackets.

The algorithm scans the string once, pushing openings and popping on closings, checking matches immediately.

Edge cases like empty strings or strings with no brackets are balanced by definition and must be handled.

Extending the approach with maps allows support for custom brackets and complex parsing scenarios.

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