Balanced Parentheses Problem Using Stack in DSA Java - 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 matching closing characters ')', '}', ']' are checked to ensure they are balanced.

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 closing one.

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 Array

B Queue

C Stack

D Linked List

A stack follows Last-In-First-Out order, which matches how parentheses need to be checked.

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

A Ignore it

B Push it onto the stack

C Pop from the stack

D Replace it with a closing parenthesis

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

If the top of the stack is '(' and the current character is ')', what should you do?

A Pop the '(' from the stack

B Push ')' onto the stack

C Ignore both characters

D Return false immediately

Matching pairs remove each other, so pop the opening parenthesis from the stack.

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

A Parentheses are balanced

B Parentheses are not balanced

C There were no parentheses

D The string is empty

An empty stack means all opening parentheses were matched correctly.

What should happen if a closing parenthesis does not match the top of the stack?

A Ignore the closing parenthesis

B Push the closing parenthesis onto the stack

C Remove all elements from the stack

D Return false (not balanced)

A mismatch means parentheses are not balanced, so return false.

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 pairs don't line up.

Practice

1. What does the Balanced Parentheses problem using a stack check for in a string?

easy

A. Whether every opening bracket has a matching closing bracket in correct order

B. If the string contains only alphabets

C. If the string length is even

D. Whether the string contains any digits

Solution

1. Step 1: Understand the problem goal

   The Balanced Parentheses problem checks if all opening brackets like '(' have a matching closing bracket ')' in the correct order.

2. Step 2: Role of stack in checking

   A stack helps track opening brackets and ensures each is closed properly in sequence.

3. Final Answer:

   Whether every opening bracket has a matching closing bracket in correct order -> Option A

4. Quick Check:

   Balanced parentheses = matching pairs [OK]

Hint: Match each '(' with ')' using stack push/pop [OK]

Common Mistakes:

• Thinking it checks string length
• Ignoring order of brackets
• Checking only for digits or alphabets

2. Which of the following Java code snippets correctly initializes a stack to check balanced parentheses?

easy

A. Stack<Character> stack = new Stack<>();

B. Stack stack = new Stack<Character>();

C. Stack<Character> stack = Stack();

D. Stack<Character> stack = new Stack<Character>;

Solution

1. Step 1: Check correct Stack initialization syntax

   In Java, to create a stack of Characters, use: Stack<Character> stack = new Stack<>(); which uses diamond operator for type inference.

2. Step 2: Identify errors in other options

   Stack stack = new Stack<Character>(); misses generic type on right side; Stack<Character> stack = Stack(); misses 'new' keyword; Stack<Character> stack = new Stack<Character>; misses parentheses after constructor.

3. Final Answer:

   Stack<Character> stack = new Stack<>(); -> Option A

4. Quick Check:

   Correct Java stack init = Stack<Character> stack = new Stack<>(); [OK]

Hint: Use diamond operator <> with new Stack<>() [OK]

Common Mistakes:

• Omitting 'new' keyword
• Missing parentheses after constructor
• Incorrect generic type syntax

3. What will be the output of the following Java code snippet?

String s = "({[]})";
System.out.println(isBalanced(s));

public static boolean isBalanced(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

medium

A. Compilation error

B. false

C. true

D. Runtime exception

Solution

1. Step 1: Trace the input string "({[]})" character by character

   Push '(' '{' '[' onto stack; then pop matching pairs for ']' '}' ')'. Stack ends empty.

2. Step 2: Check final stack state

   Stack is empty after processing all characters, so return true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   All brackets matched = true [OK]

Hint: Stack empty at end means balanced [OK]

Common Mistakes:

• Not checking stack empty at end
• Mismatching brackets order
• Ignoring empty stack before pop

4. Identify the error in this Java method for checking balanced parentheses:

public static boolean checkBalanced(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

medium

A. For loop syntax is incorrect

B. Wrong comparison operators used

C. Stack should store Strings not Characters

D. Missing check if stack is empty before pop

Solution

1. Step 1: Analyze stack pop operation

   Pop is called without checking if stack is empty, which can cause runtime exception if closing bracket appears first.

2. Step 2: Identify missing empty check

   Must check stack.isEmpty() before pop to avoid EmptyStackException.

3. Final Answer:

   Missing check if stack is empty before pop -> Option D

4. Quick Check:

   Always check stack empty before pop [OK]

Hint: Check stack empty before pop to avoid errors [OK]

Common Mistakes:

• Ignoring empty stack before pop
• Assuming input always starts with opening bracket
• Not handling runtime exceptions

5. Given the string "[{()}]({[]})", which of the following modifications to the balanced parentheses algorithm will correctly handle this input and return true?

hard

A. Use two stacks, one for opening and one for closing brackets separately

B. Use a stack and check matching pairs for all bracket types, ensuring stack is empty at end

C. Only check if the string length is even and contains brackets

D. Ignore curly braces '{}' and only check parentheses '()'

Solution

1. Step 1: Understand input complexity

   The string contains multiple types of brackets nested and sequentially combined.

2. Step 2: Apply stack-based matching for all bracket types

   Push opening brackets, pop and match closing brackets; ensure stack empty at end for balanced check.

3. Step 3: Evaluate other options

   Length check or ignoring bracket types will fail; two stacks unnecessary and incorrect.

4. Final Answer:

   Use a stack and check matching pairs for all bracket types, ensuring stack is empty at end -> Option B

5. Quick Check:

   Stack matching all brackets = true [OK]

Hint: Match all bracket types with one stack, check empty at end [OK]

Common Mistakes:

• Ignoring some bracket types
• Relying on string length only
• Using multiple stacks unnecessarily