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 `Array` as the open-bracket stack; push by `stack << ch`, pop by `stack.pop`.
matching map A small `match_open(close)` helper returns the expected opener for each closing bracket — three explicit `if`/`elsif` arms keep the lesson compact.

Basic Implementation

basic.rb
Replay: real traced execution (multi-file project)
def match_open(close)
	if close == ')'
		return '('
	elsif close == ']'
		return '['
	elsif close == '}'
		return '{'
	end
	' '
end

text = "({[]})"
stack = []
balanced = true
i = 0
while balanced && i < text.length
	ch = text[i]
	if ch == '(' || ch == '[' || ch == '{'
		stack << ch
	else
		if stack.empty? || stack[-1] != match_open(ch)
			balanced = false
		else
			stack.pop
		end
	end
	i = i + 1
end
if !stack.empty?
	balanced = false
end
if balanced
	puts "True"
else
	puts "False"
end

  1. text ← ({[]})

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

  2. stack ← []

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

  3. balanced ← true

    13stack = []14balanced = true15i = 0
    values this steptruebalanced

  4. stack ← [(]

    16while balanced && i < text.length17	ch = text[i]18	if ch == '(' || ch == '[' || ch == '{'
    values this step[(]stack(ch

  5. stack ← [(, {]

    16while balanced && i < text.length17	ch = text[i]18	if ch == '(' || ch == '[' || ch == '{'
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    16while balanced && i < text.length17	ch = text[i]18	if ch == '(' || ch == '[' || ch == '{'
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    16while balanced && i < text.length17	ch = text[i]18	if ch == '(' || ch == '[' || ch == '{'
    values this step[(, {]stack]ch

  8. stack ← [(]

    16while balanced && i < text.length17	ch = text[i]18	if ch == '(' || ch == '[' || ch == '{'
    values this step[(]stack}ch

  9. stack ← []

    16while balanced && i < text.length17	ch = text[i]18	if ch == '(' || ch == '[' || ch == '{'
    values this step[]stack)ch

  10. balanced ← true, stdout ← True

    32if balanced33	puts "True"34else
    values this steptruebalancedTruestdout[]stack

Complexity

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

Implementation notes

  • Ruby: a plain Array with << / pop / stack[-1] / stack.empty? is the smallest honest stack shape; reaching for a wrapper class would hide the explicit push/pop pattern. A balanced flag plus while balanced && i < text.length loop keeps the early-exit visible without leaning on break.
  • The match_open 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.