Stacks and Queues

Balanced Parentheses

Walk a string of bracket characters. Push every opening bracket. On a closing bracket, pop and verify it matches; mismatch or empty-stack pop means unbalanced. At end of string, stack must be empty.

Algorithm

Canonical input "({[]})" (balanced) finishes with the stack empty and the result true.

stack push/pop Use a plain `[]byte` slice as the stack; push by `append(stack, ch)`, pop by `stack = stack[:len(stack)-1]`.
matching map A small `matchOpen(close)` helper returns the expected opener for each closing bracket — three explicit cases keep the lesson compact.

Basic Implementation

basic.go
Replay: real traced execution (multi-file project)
package main

import "fmt"

func matchOpen(close byte) byte {
	switch close {
	case ')':
		return '('
	case ']':
		return '['
	case '}':
		return '{'
	}
	return 0
}

func main() {
	text := "({[]})"
	stack := make([]byte, 0, 64)
	balanced := true
	for i := 0; i < len(text); i++ {
		ch := text[i]
		if ch == '(' || ch == '[' || ch == '{' {
			stack = append(stack, ch)
		} else {
			if len(stack) == 0 || stack[len(stack)-1] != matchOpen(ch) {
				balanced = false
				break
			}
			stack = stack[:len(stack)-1]
		}
	}
	if len(stack) != 0 {
		balanced = false
	}
	fmt.Println(balanced)
}

  1. text ← ({[]})

    17func main() {18	text := "({[]})"19	stack := make([]byte, 0, 64)
    values this step({[]})text

  2. stack ← []

    18text := "({[]})"19stack := make([]byte, 0, 64)20balanced := true
    values this step[]stack

  3. balanced ← true

    19stack := make([]byte, 0, 64)20balanced := true21for i := 0; i < len(text); i++ {
    values this steptruebalanced

  4. stack ← [(]

    21for i := 0; i < len(text); i++ {22	ch := text[i]23	if ch == '(' || ch == '[' || ch == '{' {
    values this step[(]stack(ch

  5. stack ← [(, {]

    21for i := 0; i < len(text); i++ {22	ch := text[i]23	if ch == '(' || ch == '[' || ch == '{' {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    21for i := 0; i < len(text); i++ {22	ch := text[i]23	if ch == '(' || ch == '[' || ch == '{' {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    21for i := 0; i < len(text); i++ {22	ch := text[i]23	if ch == '(' || ch == '[' || ch == '{' {
    values this step[(, {]stack]ch

  8. stack ← [(]

    21for i := 0; i < len(text); i++ {22	ch := text[i]23	if ch == '(' || ch == '[' || ch == '{' {
    values this step[(]stack}ch

  9. stack ← []

    21for i := 0; i < len(text); i++ {22	ch := text[i]23	if ch == '(' || ch == '[' || ch == '{' {
    values this step[]stack)ch

  10. balanced ← true, stdout ← true

    36	fmt.Println(balanced)37}
    values this steptruebalancedtruestdout[]stack

Complexity

  • Time: O(n)
  • Space: O(n) worst case

Implementation notes

  • Go: a plain []byte slice with append / re-slice is the smallest honest stack shape; the standard library has no dedicated stack type, which keeps the lesson on the explicit push/pop pattern.
  • The matchOpen helper documents the closing -> opening map without leaking object identity into the replay.
  • The replay highlights the current character, shows the stack updating each frame, and surfaces the final balanced/unbalanced verdict.