Balanced Parentheses Problem Using Stack in DSA Java - Execution Trace

Concept Flow - Balanced Parentheses Problem Using Stack

Start

↓

Read next char

↓

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

Yes→Push to stack

No↓

Is char ')' or '}' or '

↓

Pop from stack

↓

Does popped match char?

No→Unbalanced - Stop

Yes↓

More chars?

Yes→Read next char

No↓

Stack empty?

Yes→Balanced

No↓

Unbalanced

The process reads each character, pushes opening brackets to stack, pops and checks matching for closing brackets, and finally checks if stack is empty to decide balance.

Execution Sample

DSA Java

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

// Helper method
boolean matches(char open, char close) {
  return (open == '(' && close == ')') ||
         (open == '{' && close == '}') ||
         (open == '[' && close == ']');
}

This code checks if the parentheses in the string are balanced using a stack.

Execution Table

Step	Operation	Current Char	Stack Before	Stack After	Action	Visual State
1	Read char	(		(	Push '('	( ) -> null
2	Read char	{	(	(, {	Push '{'	( -> { ) -> null
3	Read char	[	(, {	(, {, [	Push '['	( -> { -> [ ] -> null
4	Read char	]	(, {, [	(, {	Pop '[' matches ']'	( -> { ) -> null
5	Read char	}	(, {	(	Pop '{' matches '}'	( ) -> null
6	Read char	)	(		Pop '(' matches ')'	null
7	End of string	N/A			Stack empty, balanced	null

💡 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	[]	(	(, {	(, {, [	(, {	(

Key Moments - 3 Insights

Why do we push only opening brackets to the stack?

Because opening brackets mark the start of a pair. We push them to remember what type we expect to close later. See execution_table steps 1-3 where '(' '{' '[' are pushed.

What happens if we find a closing bracket but the stack is empty?

It means there's no matching opening bracket, so the string is unbalanced. This is shown in the concept flow where 'Stack empty?' leads to 'Unbalanced - Stop'.

Why do we check if the popped bracket matches the current closing bracket?

Because only matching pairs are balanced. For example, '[' matches ']', but not ')'. This check is done in execution_table steps 4-6.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the stack after popping?

A ({[

B (

C ({

D

💡 Hint

Check the 'Stack After' column at step 4 in execution_table.

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

A Step 3

B Step 6

C Step 7

D Step 5

💡 Hint

Look at the 'Stack After' column to find when it becomes [].

If the input string started with a closing bracket ')', what would happen according to the concept flow?

A Pop from empty stack and stop as unbalanced

B Ignore and continue

C Push ')' to stack

D Return balanced immediately

💡 Hint

Refer to the 'Stack empty?' decision in the concept_flow diagram.

Concept Snapshot

Balanced Parentheses Using Stack:
- Push opening brackets '(' '{' '[' onto stack
- For closing brackets ')' '}' ']', pop and check match
- If mismatch or stack empty on pop, unbalanced
- At end, if stack empty, parentheses are balanced
- Uses LIFO stack to track pairs

Full Transcript

This visualization shows how to check balanced parentheses using a stack. We read each character of the string. If it is an opening bracket like '(' '{' or '[', we push it onto the stack. If it is a closing bracket like ')' '}' or ']', we pop from the stack and check if the popped bracket matches the closing one. If it does not match or the stack is empty when trying to pop, the string is unbalanced. After processing all characters, if the stack is empty, the parentheses are balanced. The execution table shows each step with the stack state and actions. Key moments clarify why we push only opening brackets, what happens if the stack is empty on closing bracket, and why matching is important. The quiz tests understanding of stack states and flow decisions.

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