Balanced Parentheses Problem Using Stack in DSA Go - Execution Trace

Concept Flow - Balanced Parentheses Problem Using Stack

Start

↓

Read next char

↓

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

Yes→Push to stack

↓

Is char ')' or '}' or '

↓

Pop from stack

↓

Does popped match char?

No→Unbalanced -> Stop

↓

More chars?

Yes→Repeat

No↓

Stack empty?

Yes→Balanced

No↓

Unbalanced

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

Execution Sample

DSA Go

func isBalanced(s string) bool {
	stack := []rune{}
	for _, ch := range s {
		switch ch {
		case '(', '[', '{':
			stack = append(stack, ch)
		case ')', ']', '}':
			if len(stack) == 0 {
				return false
			}
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if (ch == ')' && top != '(') ||
			   (ch == ']' && top != '[') ||
			   (ch == '}' && top != '{') {
				return false
			}
		}
	}
	return len(stack) == 0
}

Checks if brackets in string s are balanced using a stack.

Execution Table

Step	Operation	Current Char	Stack Before	Stack After	Visual State
1	Read char	(		(	( -> stack: (
2	Read char	(	(	(, (	(( -> stack: ( (
3	Read char	)	(, (	(	(() -> stack: (
4	Read char	)	(		(()) -> stack: empty
5	End of string	-			Stack empty, balanced

💡 End of string reached, stack empty means parentheses are balanced

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
stack		(	(, (	(
current char	-	(	(	)	)	-

Key Moments - 3 Insights

Why do we check if the stack is empty before popping?

Because popping from an empty stack means there is a closing bracket without a matching opening bracket, so the string is unbalanced. See execution_table step 4 where stack is checked before pop.

Why do we compare the popped element with the current closing bracket?

To ensure the types of brackets match (e.g., '(' matches ')'). If they don't match, the string is unbalanced. This is shown in the flow where popped and current char are compared.

What does it mean if the stack is not empty after processing all characters?

It means there are unmatched opening brackets left, so the string is unbalanced. See execution_table final step where stack empty check decides balance.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the stack after processing the current char?

A

B ((

C (

D ()

💡 Hint

Check the 'Stack After' column at Step 3 in execution_table

At which step does the stack become empty again?

A Step 2

B Step 4

C Step 3

D Step 1

💡 Hint

Look at the 'Stack After' column to find when stack is []

If the input string started with a closing bracket ')', what would happen in the execution flow?

A Stack would be empty and unbalanced detected immediately

B Stack would push the closing bracket

C Stack would pop an element

D The program would ignore the closing bracket

💡 Hint

Refer to concept_flow where closing bracket with empty stack leads to unbalanced stop

Concept Snapshot

Balanced Parentheses Using Stack:
- Push opening brackets onto stack
- For closing brackets, pop and check match
- If mismatch or pop from empty stack, unbalanced
- At end, empty stack means balanced
- Common brackets: (), {}, []

Full Transcript

This concept uses a stack to check if parentheses in a string are balanced. We read each character: if it's an opening bracket, we push it onto the stack. If it's a closing bracket, we check if the stack is empty; if yes, it's unbalanced. Otherwise, we pop from the stack and check if the popped bracket matches the closing one. If not, unbalanced. After processing all characters, if the stack is empty, the parentheses are balanced; otherwise, unbalanced. The execution table shows step-by-step stack changes for input like '(())'. Key moments clarify why stack emptiness is checked before popping and why matching brackets matter. The visual quiz tests understanding of stack state at various steps and behavior on invalid input.

Practice

1. What is the main purpose of using a stack in the Balanced Parentheses Problem?

easy

A. To keep track of opening parentheses and match them with closing ones

B. To count the total number of parentheses in the string

C. To reverse the string of parentheses

D. To sort the parentheses in order

Solution

1. Step 1: Understand the role of stack in parentheses matching

   The stack stores opening parentheses as they appear to check if each closing parenthesis matches the last opened one. Counting or reversing parentheses does not help in matching pairs correctly; sorting changes the order and breaks the sequence.

2. Final Answer:

   To keep track of opening parentheses and match them with closing ones -> Option A

3. Quick Check:

   Stack usage = matching parentheses [OK]

Hint: Stack stores last opened parenthesis to match closing one [OK]

Common Mistakes:

• Thinking stack counts parentheses instead of matching
• Assuming stack reverses the string
• Believing sorting helps in matching parentheses

2. Which of the following Go code snippets correctly pushes an opening parenthesis '(' onto a stack represented by a slice of runes named stack?

easy

A. stack = append(stack, '(')

B. stack.push('(')

C. stack.add('(')

D. stack.insert('(')

Solution

1. Step 1: Recall how to add elements to a slice in Go

   In Go, slices use the built-in append function to add elements at the end. Since stack is a slice, stack = append(stack, '(') correctly adds '(' to the top.

2. Final Answer:

   stack = append(stack, '(') -> Option A

3. Quick Check:

   Use append to push in Go slices [OK]

Hint: Use append(slice, value) to push in Go [OK]

Common Mistakes:

• Using non-existent methods like push or add on slices
• Forgetting to assign back after append
• Using incorrect method names

3. What will be the output of the following Go code snippet that checks if the string "([])" has balanced parentheses?

func isBalanced(s string) bool {
    stack := []rune{}
    for _, ch := range s {
        if ch == '(' || ch == '[' {
            stack = append(stack, ch)
        } else if ch == ')' {
            if len(stack) == 0 || stack[len(stack)-1] != '(' {
                return false
            }
            stack = stack[:len(stack)-1]
        } else if ch == ']' {
            if len(stack) == 0 || stack[len(stack)-1] != '[' {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}

fmt.Println(isBalanced("([])"))

medium

A. runtime error

B. false

C. true

D. compilation error

Solution

1. Step 1: Trace the stack operations for "([])"

   Push '(' then push '['; on encountering ']', pop '['; on encountering ')', pop '('; stack ends empty, so function returns true indicating balanced parentheses.

2. Final Answer:

   true -> Option C

3. Quick Check:

   Stack empty after matching = true [OK]

Hint: Empty stack after processing means balanced [OK]

Common Mistakes:

• Not popping matching opening bracket
• Confusing bracket types
• Ignoring empty stack check before pop

4. Identify the bug in the following Go function that checks balanced parentheses:

func isBalanced(s string) bool {
    stack := []rune{}
    for _, ch := range s {
        if ch == '(' {
            stack = append(stack, ch)
        } else if ch == ')' {
            if len(stack) == 0 || stack[len(stack)-1] != ')' {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}

medium

A. Stack is not initialized properly

B. The condition checks for ')' instead of '(' when popping

C. The loop does not iterate over the string

D. The function does not return any value

Solution

1. Step 1: Analyze the popping condition for closing parenthesis

   The code checks if the top of stack is ')', but it should check for '(' to match correctly. Since stack stores '(', checking for ')' fails to match and returns false incorrectly.

2. Final Answer:

   The condition checks for ')' instead of '(' when popping -> Option B

3. Quick Check:

   Match top stack with '(' for ')' closing [OK]

Hint: Match closing bracket with correct opening bracket on stack top [OK]

Common Mistakes:

• Checking wrong character on stack top
• Not handling empty stack before pop
• Ignoring matching pairs logic

5. Given the string "{[()()]()}", which includes curly braces {}, square brackets [], and parentheses (), how should the stack-based algorithm be modified to correctly check for balanced parentheses of all three types?

hard

A. Replace stack with a queue to handle all bracket types

B. Only check for parentheses '()' and ignore other types

C. Use two separate stacks for different bracket types

D. Add conditions to push '{', '[', '(' and pop matching '}', ']', ')' accordingly

Solution

1. Step 1: Extend push logic for all opening brackets

   Push '{', '[', '(' onto the stack when encountered to track all opening brackets. When encountering '}', ']', or ')', check if the top of the stack matches '{', '[', or '(' respectively before popping.

2. Final Answer:

   Add conditions to push '{', '[', '(' and pop matching '}', ']', ')' accordingly -> Option D

3. Quick Check:

   Match all bracket types with stack push/pop [OK]

Hint: Push all openings; pop only if top matches corresponding closing [OK]

Common Mistakes:

• Ignoring curly braces in the algorithm
• Using multiple stacks unnecessarily
• Replacing stack with queue which breaks LIFO logic