Balanced Parentheses Problem Using Stack in DSA C++ - Build from Scratch

Balanced Parentheses Problem Using Stack

📋 What You'll Learn

💡 Why This Matters

🌍 Real World

Checking balanced parentheses is important in code editors, compilers, and calculators to ensure expressions are correct.

💼 Career

Understanding stacks and balanced parentheses is a common interview question and fundamental for software development roles.

1

Create the parentheses string

Create a std::string variable called expression and set it to the value "{[()()]}.

DSA C++

#include 
#include 
#include 

int main() {

    // Create the expression string
    // Your code here

    return 0;
}

Hint

Use std::string expression = "{[()()]} to store the parentheses.

2

Create a stack to hold opening brackets

Create a std::stack<char> variable called stack to hold characters.

DSA C++

#include 
#include 
#include 

int main() {
    std::string expression = "{[()()]}";

    // Create the stack
    // Your code here

    return 0;
}

Hint

Use std::stack<char> stack; to create the stack.

3

Implement the logic to check balanced parentheses

Use a for loop with variable ch to iterate over each character in expression. Inside the loop, push opening brackets '(', '{', '[' onto stack. For closing brackets, check if the top of stack matches the corresponding opening bracket and pop it. If not matched or stack is empty, set a boolean variable isBalanced to false and break the loop. Initialize isBalanced as true before the loop. After the loop, if stack is not empty, set isBalanced to false.

DSA C++

#include 
#include 
#include 

int main() {
    std::string expression = "{[()()]}";
    std::stack stack;

    // Check balanced parentheses
    // Your code here

    return 0;
}

Hint

Use a loop to check each character and update isBalanced accordingly.

4

Print the result

Print "Balanced" if isBalanced is true, otherwise print "Not Balanced".

DSA C++

#include 
#include 
#include 

int main() {
    std::string expression = "{[()()]}";
    std::stack stack;
    bool isBalanced = true;

    for (char ch : expression) {
        if (ch == '(' || ch == '{' || ch == '[') {
            stack.push(ch);
        } else {
            if (stack.empty()) {
                isBalanced = false;
                break;
            }
            char top = stack.top();
            if ((ch == ')' && top == '(') ||
                (ch == '}' && top == '{') ||
                (ch == ']' && top == '[')) {
                stack.pop();
            } else {
                isBalanced = false;
                break;
            }
        }
    }

    if (!stack.empty()) {
        isBalanced = false;
    }

    // Print the result
    // Your code here

    return 0;
}

Hint

Use std::cout to print the result based on isBalanced.

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