Balanced Parentheses Problem Using Stack in DSA Go

Mental Model

We use a stack to keep track of opening brackets and check if each closing bracket matches the last opened one.

Analogy: Imagine stacking plates: you put plates on top when you see an opening bracket, and you remove the top plate when you see a matching closing bracket. If you try to remove a plate when none is there or the plate doesn't match, something is wrong.

Stack (top at right): []
Expression: ( [ { } ] )

Initial:
Stack: []
Expression pointer ↑ at '('

Dry Run Walkthrough

Input: expression: "({[]})"

Goal: Check if the parentheses in the expression are balanced and correctly nested

Step 1: Read '(' and push it onto the stack

Stack: ['(']
Expression pointer ↑ at '{'

Why: We store opening brackets to match them later with closing ones

Step 2: Read '{' and push it onto the stack

Stack: ['(', '{']
Expression pointer ↑ at '['

Why: Keep track of nested opening brackets

Step 3: Read '[' and push it onto the stack

Stack: ['(', '{', '[']
Expression pointer ↑ at ']'

Why: Add the next opening bracket to stack for matching

Step 4: Read ']' and check top of stack; top is '[' which matches, so pop it

Stack: ['(', '{']
Expression pointer ↑ at '}'

Why: Closing bracket matches last opening, so remove it from stack

Step 5: Read '}' and check top of stack; top is '{' which matches, so pop it

Stack: ['(']
Expression pointer ↑ at ')'

Why: Continue matching closing brackets with last opened

Step 6: Read ')' and check top of stack; top is '(' which matches, so pop it

Stack: []
Expression pointer ↑ at end

Why: All brackets matched and stack is empty

Result:

Stack: []
Expression fully processed
Answer: Balanced

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Stack struct {
	elements []rune
}

func (s *Stack) Push(c rune) {
	s.elements = append(s.elements, c)
}

func (s *Stack) Pop() rune {
	if len(s.elements) == 0 {
		return 0 // empty stack
	}
	last := s.elements[len(s.elements)-1]
	s.elements = s.elements[:len(s.elements)-1]
	return last
}

func (s *Stack) IsEmpty() bool {
	return len(s.elements) == 0
}

func isMatching(open, close rune) bool {
	return (open == '(' && close == ')') ||
		(open == '{' && close == '}') ||
		(open == '[' && close == ']')
}

func isBalanced(expression string) bool {
	stack := Stack{}
	for _, ch := range expression {
		if ch == '(' || ch == '{' || ch == '[' {
			stack.Push(ch) // push opening bracket
		} else if ch == ')' || ch == '}' || ch == ']' {
			if stack.IsEmpty() {
				return false // no matching opening
			}
			last := stack.Pop() // pop last opening
			if !isMatching(last, ch) {
				return false // mismatch
			}
		}
	}
	return stack.IsEmpty() // true if all matched
}

func main() {
	expression := "({[]})"
	if isBalanced(expression) {
		fmt.Println("Balanced")
	} else {
		fmt.Println("Not Balanced")
	}
}

stack.Push(ch) // push opening bracket

add opening bracket to stack to match later

if stack.IsEmpty() { return false }

if closing bracket found but stack empty, no match possible

last := stack.Pop()

remove last opening bracket to check match

if !isMatching(last, ch) { return false }

if popped opening doesn't match closing, fail

return stack.IsEmpty()

if stack empty at end, all brackets matched

Output

Balanced

Complexity Analysis

Time: O(n) because we scan the expression once, pushing and popping at most once per character

Space: O(n) because in worst case all characters are opening brackets stored in stack

vs Alternative: Compared to scanning and counting brackets without stack, this method correctly handles nested and mixed types with linear time and space

Edge Cases

empty string

returns true because no brackets means balanced

DSA Go

return stack.IsEmpty()

string with only opening brackets like "((("

returns false because stack not empty at end

DSA Go

return stack.IsEmpty()

string with closing bracket first like ")("

returns false because stack empty when closing bracket found

DSA Go

if stack.IsEmpty() { return false }

When to Use This Pattern

When you see a problem asking if brackets or symbols are properly opened and closed in order, use a stack to track openings and match closings.

Common Mistakes

Mistake: Not checking if stack is empty before popping on a closing bracket
Fix: Add a check for empty stack before popping to avoid errors and detect unmatched closing brackets

Mistake: Only counting brackets without checking order or type
Fix: Use stack to ensure correct nesting and matching types, not just counts

Summary

Checks if every opening bracket has a matching closing bracket in correct order using a stack

Use when validating expressions with nested brackets or parentheses

The key insight is to push openings and pop them only when a matching closing bracket appears

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