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

Basic Implementation

basic.rs
Replay: real traced execution (multi-file project)
fn match_open(close: u8) -> u8 {
	match close {
		b')' => b'(',
		b']' => b'[',
		b'}' => b'{',
		_ => 0,
	}
}

fn main() {
	let text = "({[]})";
	let mut stack: Vec<u8> = Vec::new();
	let mut balanced = true;
	for i in 0..text.len() {
		let ch = text.as_bytes()[i];
		if ch == b'(' || ch == b'[' || ch == b'{' {
			stack.push(ch);
		} else {
			if stack.is_empty() || stack[stack.len()-1] != match_open(ch) {
				balanced = false;
				break;
			}
			stack.pop();
		}
	}
	if !stack.is_empty() {
		balanced = false;
	}
	println!("{}", balanced);
}

  1. text ← ({[]})

    10fn main() {11	let text = "({[]})";12	let mut stack: Vec<u8> = Vec::new();
    values this step({[]})text

  2. stack ← []

    11let text = "({[]})";12let mut stack: Vec<u8> = Vec::new();13let mut balanced = true;
    values this step[]stack

  3. balanced ← true

    12let mut stack: Vec<u8> = Vec::new();13let mut balanced = true;14for i in 0..text.len() {
    values this steptruebalanced

  4. stack ← [(]

    14for i in 0..text.len() {15	let ch = text.as_bytes()[i];16	if ch == b'(' || ch == b'[' || ch == b'{' {
    values this step[(]stack(ch

  5. stack ← [(, {]

    14for i in 0..text.len() {15	let ch = text.as_bytes()[i];16	if ch == b'(' || ch == b'[' || ch == b'{' {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    14for i in 0..text.len() {15	let ch = text.as_bytes()[i];16	if ch == b'(' || ch == b'[' || ch == b'{' {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    14for i in 0..text.len() {15	let ch = text.as_bytes()[i];16	if ch == b'(' || ch == b'[' || ch == b'{' {
    values this step[(, {]stack]ch

  8. stack ← [(]

    14for i in 0..text.len() {15	let ch = text.as_bytes()[i];16	if ch == b'(' || ch == b'[' || ch == b'{' {
    values this step[(]stack}ch

  9. stack ← []

    14for i in 0..text.len() {15	let ch = text.as_bytes()[i];16	if ch == b'(' || ch == b'[' || ch == b'{' {
    values this step[]stack)ch

  10. balanced ← true, stdout ← true

    28	}29	println!("{}", balanced);30}
    values this steptruebalancedtruestdout[]stack

Complexity

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

Implementation notes

  • Rust: a plain Vec<u8> with push / pop 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 match_open 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.