Stack - Bash DSA

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.

Basic Implementation

basic.sh

#!/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

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.

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.