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 an `[Character]` array as the open-bracket stack; push by `stack.append(ch)`, pop by `stack.removeLast()`.
matching map A small `matchOpen(close)` helper returns the expected opener for each closing bracket — three explicit `switch` arms keep the lesson compact.

Basic Implementation

basic.swift
Replay: real traced execution (multi-file project)
func matchOpen(_ close: Character) -> Character {
	switch close {
	case ")": return "("
	case "]": return "["
	case "}": return "{"
	default:  return " "
	}
}

let text = "({[]})"
var stack: [Character] = []
var balanced = true
for ch in text {
	if ch == "(" || ch == "[" || ch == "{" {
		stack.append(ch)
	} else {
		if stack.isEmpty || stack.last! != matchOpen(ch) {
			balanced = false
			break
		}
		stack.removeLast()
	}
}
if !stack.isEmpty {
	balanced = false
}
print(balanced ? "True" : "False")

  1. text ← ({[]})

    10let text = "({[]})"11var stack: [Character] = []
    values this step({[]})text

  2. stack ← []

    10let text = "({[]})"11var stack: [Character] = []12var balanced = true
    values this step[]stack

  3. balanced ← true

    11var stack: [Character] = []12var balanced = true13for ch in text {
    values this steptruebalanced

  4. stack ← [(]

    12var balanced = true13for ch in text {14	if ch == "(" || ch == "[" || ch == "{" {
    values this step[(]stack(ch

  5. stack ← [(, {]

    12var balanced = true13for ch in text {14	if ch == "(" || ch == "[" || ch == "{" {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    12var balanced = true13for ch in text {14	if ch == "(" || ch == "[" || ch == "{" {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    12var balanced = true13for ch in text {14	if ch == "(" || ch == "[" || ch == "{" {
    values this step[(, {]stack]ch

  8. stack ← [(]

    12var balanced = true13for ch in text {14	if ch == "(" || ch == "[" || ch == "{" {
    values this step[(]stack}ch

  9. stack ← []

    12var balanced = true13for ch in text {14	if ch == "(" || ch == "[" || ch == "{" {
    values this step[]stack)ch

  10. balanced ← true, stdout ← True

    26}27print(balanced ? "True" : "False")
    values this steptruebalancedTruestdout[]stack

Complexity

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

Implementation notes

  • Swift: var stack: [Character] with append / removeLast / last is the smallest honest stack shape; the stdlib Array already exposes a proper LIFO API so the lesson can stay on the explicit push/pop pattern instead of importing Foundation.
  • The matchOpen helper documents the closing -> opening map without leaking runtime references into the replay.
  • The replay highlights the current character, shows the stack updating each frame, and surfaces the final balanced/unbalanced verdict.