Balanced Parentheses Problem Using Stack in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced Parentheses Check

What is the output of the following Go code that checks if the parentheses in the string are balanced?

DSA Go

package main
import "fmt"
func isBalanced(s string) bool {
    stack := []rune{}
    pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
    for _, char := range s {
        switch char {
        case '(', '[', '{':
            stack = append(stack, char)
        case ')', ']', '}':
            if len(stack) == 0 || stack[len(stack)-1] != pairs[char] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}
func main() {
    fmt.Println(isBalanced("{[()()]()}"))
}

A SyntaxError

B false

C true

D panic: runtime error

💡 Hint

Think about how the stack is used to match opening and closing brackets.

The code uses a stack to push opening brackets and pop them when a matching closing bracket is found. The input string is balanced, so the function returns true.

❓ Predict Output

intermediate

Output for Unbalanced Parentheses

What will the output be when running this Go code with the input string "{[(])}"?

DSA Go

package main
import "fmt"
func isBalanced(s string) bool {
    stack := []rune{}
    pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
    for _, char := range s {
        switch char {
        case '(', '[', '{':
            stack = append(stack, char)
        case ')', ']', '}':
            if len(stack) == 0 || stack[len(stack)-1] != pairs[char] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}
func main() {
    fmt.Println(isBalanced("{[(])}"))
}

A true

B false

C panic: runtime error

D SyntaxError

💡 Hint

Check if the closing brackets match the last opening bracket in the stack.

The string is not balanced because the closing bracket ')' does not match the last opening bracket '[' in the stack, so the function returns false.

🔧 Debug

advanced

Identify the Error in Parentheses Checking Code

What error will this Go code produce when checking parentheses balance?

DSA Go

package main
import "fmt"
func isBalanced(s string) bool {
    stack := []rune{}
    pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
    for _, char := range s {
        if char == '(' || char == '[' || char == '{' {
            stack = append(stack, char)
        } else if char == ')' || char == ']' || char == '}' {
            if len(stack) == 0 || stack[len(stack)] != pairs[char] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}
func main() {
    fmt.Println(isBalanced("()"))
}

A SyntaxError

B false

C true

D panic: runtime error: index out of range

💡 Hint

Check how the stack is accessed when popping elements.

The code tries to access stack[len(stack)] which is out of range because valid indices go from 0 to len(stack)-1.

🧠 Conceptual

advanced

Stack Usage in Balanced Parentheses Problem

Why is a stack the best data structure to check for balanced parentheses?

A Because it allows checking the last opened bracket first, matching the last-in, first-out order needed.

B Because it automatically removes duplicates from the input string.

C Because it uses less memory than arrays for this problem.

D Because it stores all brackets in sorted order for quick lookup.

💡 Hint

Think about how brackets must be closed in reverse order of opening.

A stack follows last-in, first-out order, which matches how brackets must be closed in reverse order of opening, making it ideal for this problem.

🚀 Application

expert

Resulting Stack State After Processing Input

Given the input string "[{()}({})]({})", what is the state of the stack after processing all characters using the balanced parentheses stack algorithm?

A Empty stack (all parentheses matched)

B Stack contains one ']'

C Stack contains two '{' and one '['

D Stack contains one '('

💡 Hint

Visualize pushing opening brackets and popping when matching closing brackets appear.

All brackets in the input string are properly matched and closed, so the stack is empty at the end.

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