Stacks and Queues

Stack

Balanced Parentheses

Use a stack to verify that brackets in a string are properly opened and closed. Push opens, pop on close, and confirm the closer matches the last open.

Algorithm

Canonical input text="({[]})" walks six characters, pushes three, pops three matched, and finishes with an empty stack → True.

push on open A `(`, `[`, or `{` pushes the open bracket onto the stack.
pop on close A `)`, `]`, or `}` pops the stack and checks that the popped value matches the expected open. Mismatch (or empty pop) marks the input unbalanced.

Basic Implementation

basic.sh
Replay: real traced execution (multi-file project)
#!/usr/bin/env bash
set -euo pipefail
match_open() {
	case "$1" in
		")") echo "(" ;;
		"]") echo "[" ;;
		"}") echo "{" ;;
		*) echo " " ;;
	esac
}

text="({[]})"
stack=()
top=-1
balanced=1
i=0
while [ "$balanced" -eq 1 ] && [ "$i" -lt "${#text}" ]; do
	ch=${text:i:1}
	case "$ch" in
		"(" | "[" | "{")
			top=$((top + 1))
			stack[top]=$ch
			;;
		*)
			if [ "$top" -lt 0 ]; then
				balanced=0
			else
				expected=$(match_open "$ch")
				if [ "${stack[top]}" != "$expected" ]; then
					balanced=0
				else
					top=$((top - 1))
				fi
			fi
			;;
	esac
	i=$((i + 1))
done
if [ "$top" -ge 0 ]; then
	balanced=0
fi
if [ "$balanced" -eq 1 ]; then
	echo "True"
else
	echo "False"
fi

  1. text ← ({[]})

    12text="({[]})"13stack=()
    values this step({[]})text

  2. stack ← []

    12text="({[]})"13stack=()14top=-1
    values this step[]stack

  3. top ← -1

    13stack=()14top=-115balanced=1
    values this step-1top

  4. balanced ← true

    14top=-115balanced=116i=0
    values this steptruebalanced

  5. stack ← [(]

    16i=017while [ "$balanced" -eq 1 ] && [ "$i" -lt "${#text}" ]; do18	ch=${text:i:1}
    values this step[(]stack(ch

  6. stack ← [(, {]

    16i=017while [ "$balanced" -eq 1 ] && [ "$i" -lt "${#text}" ]; do18	ch=${text:i:1}
    values this step[(, {]stack{ch

  7. stack ← [(, {, []

    16i=017while [ "$balanced" -eq 1 ] && [ "$i" -lt "${#text}" ]; do18	ch=${text:i:1}
    values this step[(, {, []stack[ch

  8. stack ← [(, {]

    16i=017while [ "$balanced" -eq 1 ] && [ "$i" -lt "${#text}" ]; do18	ch=${text:i:1}
    values this step[(, {]stack]ch

  9. stack ← [(]

    16i=017while [ "$balanced" -eq 1 ] && [ "$i" -lt "${#text}" ]; do18	ch=${text:i:1}
    values this step[(]stack}ch

  10. stack ← []

    16i=017while [ "$balanced" -eq 1 ] && [ "$i" -lt "${#text}" ]; do18	ch=${text:i:1}
    values this step[]stack)ch

  11. balanced ← true, stdout ← True

    42if [ "$balanced" -eq 1 ]; then43	echo "True"44else
    values this steptruebalancedTruestdout[]stack

Complexity

  • Time: O(n)
  • Space: O(n) for the stack

Implementation notes

  • Bash: an indexed stack=() array plus an integer top cursor avoids the unset 'stack[idx]' sparse-array trap that would leave holes after pops. Push is top=$((top + 1)); stack[top]=$ch; pop is top=$((top - 1)).
  • The match_open helper returns the expected open bracket for any closer via a case; it is called via $(...) because it only echoes a value and does not mutate globals.
  • The replay describes each step as push '<ch>' or pop -> '<open>' match with the stack contents after the step so the viewer can follow the LIFO trace.