064 Intermediate

064 — Balanced Parentheses

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "064 — Balanced Parentheses" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Checking whether brackets are balanced is the classic stack application problem. Key difference from OCaml: 1. **Exception vs early return**: OCaml uses exceptions (`raise Exit`) for early exit from iteration. Rust uses `return false` inside a `for` loop — more explicit.

Tutorial

The Problem

Checking whether brackets are balanced is the classic stack application problem. Every (, [, or { must have a matching closing bracket in the correct order. The algorithm is: push opening brackets; on closing brackets, pop and verify the match; at end, the stack must be empty.

This problem appears in: compilers (syntax checking), text editors (bracket highlighting), math expression parsing, HTML/XML validation, and shell scripts (unmatched quotes). It is also the typical introductory interview problem for stacks.

🎯 Learning Outcomes

• Use Vec<char> as a stack for bracket matching

• Push opening brackets, verify and pop on closing brackets

• Return false immediately on mismatch (early exit)

• Return false at end if the stack is non-empty (unclosed brackets)

• Implement a recursive version using immutable slice-as-stack (functional style)

• Use a counter: increment on (, decrement on ), return counter == 0 && never_negative at the end

• Extend to multiple bracket types using a Vec stack: push opening brackets, verify matching on closing brackets

Code Example

#![allow(clippy::all)]
/// # Balanced Parentheses
///
/// Stack-based bracket matching using Vec as a stack.
/// Supports (), [], {}.

/// Idiomatic Rust with a Vec as stack.
pub fn is_balanced(s: &str) -> bool {
    let mut stack: Vec<char> = Vec::new();
    for c in s.chars() {
        match c {
            '(' | '[' | '{' => stack.push(c),
            ')' => {
                if stack.pop() != Some('(') {
                    return false;
                }
            }
            ']' => {
                if stack.pop() != Some('[') {
                    return false;
                }
            }
            '}' => {
                if stack.pop() != Some('{') {
                    return false;
                }
            }
            _ => {} // ignore other characters
        }
    }
    stack.is_empty()
}

/// Recursive approach using a slice as an immutable stack (functional style).
pub fn is_balanced_recursive(s: &str) -> bool {
    fn matching(c: char) -> char {
        match c {
            ')' => '(',
            ']' => '[',
            '}' => '{',
            _ => ' ',
        }
    }

    fn check(chars: &[char], stack: &[char]) -> bool {
        match chars.first() {
            None => stack.is_empty(),
            Some(&c) => match c {
                '(' | '[' | '{' => {
                    let mut new_stack = stack.to_vec();
                    new_stack.push(c);
                    check(&chars[1..], &new_stack)
                }
                ')' | ']' | '}' => match stack.last() {
                    Some(&top) if top == matching(c) => {
                        let new_stack = &stack[..stack.len() - 1];
                        check(&chars[1..], new_stack)
                    }
                    _ => false,
                },
                _ => check(&chars[1..], stack),
            },
        }
    }

    let chars: Vec<char> = s.chars().collect();
    check(&chars, &[])
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_balanced() {
        assert!(is_balanced("([]{})"));
        assert!(is_balanced("((()))"));
        assert!(is_balanced("[{()}]"));
        assert!(is_balanced(""));
    }

    #[test]
    fn test_unbalanced() {
        assert!(!is_balanced("([)]"));
        assert!(!is_balanced("("));
        assert!(!is_balanced(")"));
        assert!(!is_balanced("((())"));
    }

    #[test]
    fn test_with_other_chars() {
        assert!(is_balanced("a(b[c]d)e"));
    }

    #[test]
    fn test_recursive() {
        assert!(is_balanced_recursive("([]{})"));
        assert!(!is_balanced_recursive("([)]"));
        assert!(is_balanced_recursive(""));
    }
}

(* Balanced Parentheses — Stack-based bracket matching *)

let is_balanced s =
  let matching = function ')' -> '(' | ']' -> '[' | '}' -> '{' | _ -> ' ' in
  let rec check stack i =
    if i = String.length s then stack = []
    else match s.[i] with
    | '(' | '[' | '{' as c -> check (c :: stack) (i + 1)
    | ')' | ']' | '}' as c ->
      (match stack with
       | top :: rest when top = matching c -> check rest (i + 1)
       | _ -> false)
    | _ -> check stack (i + 1)
  in
  check [] 0

let () =
  assert (is_balanced "([]{})" = true);
  assert (is_balanced "([)]" = false);
  assert (is_balanced "((()))" = true);
  assert (is_balanced "[{()}]" = true);
  assert (is_balanced "(" = false);
  assert (is_balanced "" = true);
  Printf.printf "All balanced parentheses tests passed!\n"

Key Differences

Exception vs early return: OCaml uses exceptions (raise Exit) for early exit from iteration. Rust uses return false inside a for loop — more explicit.

**Stack module vs Vec**: OCaml's Stack module is a mutable stack. Rust uses Vec<char> as a stack — push appends, pop removes from end.

**String.iter vs chars()**: OCaml's String.iter f s calls f on each byte. Rust's s.chars() iterates Unicode scalar values. For ASCII input (brackets), both are equivalent.

Functional recursive: The recursive approach treats the remaining input and current stack as function arguments, enabling pure functional style without mutation.

Stack-based algorithm: The canonical algorithm uses a counter (for single bracket type) or a stack (for multiple bracket types). Increment on (, decrement on ), return true iff counter is 0 at the end and never went negative.

Early termination: A counter going negative means there's a ) with no matching ( — immediately return false. Rust's fold with early termination: use try_fold or all() with a mutable counter.

Multiple bracket types: Extending to (), [], {} requires a Vec stack. Push opening brackets, pop and check matching on closing brackets.

Real-world use: Compiler lexers, JSON parsers, and HTML validators all use balanced bracket checking. The same algorithm underlies XML tag matching and indentation validation.

OCaml Approach

OCaml's version: let is_balanced s = let stack = Stack.create () in try String.iter (fun c -> match c with | '(' | '[' | '{' -> Stack.push c stack | ')' -> if Stack.pop stack <> '(' then raise Exit | ']' -> if Stack.pop stack <> '[' then raise Exit | '}' -> if Stack.pop stack <> '{' then raise Exit | _ -> ()) s; Stack.is_empty stack with Exit -> false | Stack.Empty -> false. The try/with handles both the mismatch and the empty-stack cases.

Full Source

#![allow(clippy::all)]
/// # Balanced Parentheses
///
/// Stack-based bracket matching using Vec as a stack.
/// Supports (), [], {}.

/// Idiomatic Rust with a Vec as stack.
pub fn is_balanced(s: &str) -> bool {
    let mut stack: Vec<char> = Vec::new();
    for c in s.chars() {
        match c {
            '(' | '[' | '{' => stack.push(c),
            ')' => {
                if stack.pop() != Some('(') {
                    return false;
                }
            }
            ']' => {
                if stack.pop() != Some('[') {
                    return false;
                }
            }
            '}' => {
                if stack.pop() != Some('{') {
                    return false;
                }
            }
            _ => {} // ignore other characters
        }
    }
    stack.is_empty()
}

/// Recursive approach using a slice as an immutable stack (functional style).
pub fn is_balanced_recursive(s: &str) -> bool {
    fn matching(c: char) -> char {
        match c {
            ')' => '(',
            ']' => '[',
            '}' => '{',
            _ => ' ',
        }
    }

    fn check(chars: &[char], stack: &[char]) -> bool {
        match chars.first() {
            None => stack.is_empty(),
            Some(&c) => match c {
                '(' | '[' | '{' => {
                    let mut new_stack = stack.to_vec();
                    new_stack.push(c);
                    check(&chars[1..], &new_stack)
                }
                ')' | ']' | '}' => match stack.last() {
                    Some(&top) if top == matching(c) => {
                        let new_stack = &stack[..stack.len() - 1];
                        check(&chars[1..], new_stack)
                    }
                    _ => false,
                },
                _ => check(&chars[1..], stack),
            },
        }
    }

    let chars: Vec<char> = s.chars().collect();
    check(&chars, &[])
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_balanced() {
        assert!(is_balanced("([]{})"));
        assert!(is_balanced("((()))"));
        assert!(is_balanced("[{()}]"));
        assert!(is_balanced(""));
    }

    #[test]
    fn test_unbalanced() {
        assert!(!is_balanced("([)]"));
        assert!(!is_balanced("("));
        assert!(!is_balanced(")"));
        assert!(!is_balanced("((())"));
    }

    #[test]
    fn test_with_other_chars() {
        assert!(is_balanced("a(b[c]d)e"));
    }

    #[test]
    fn test_recursive() {
        assert!(is_balanced_recursive("([]{})"));
        assert!(!is_balanced_recursive("([)]"));
        assert!(is_balanced_recursive(""));
    }
}

(* Balanced Parentheses — Stack-based bracket matching *)

let is_balanced s =
  let matching = function ')' -> '(' | ']' -> '[' | '}' -> '{' | _ -> ' ' in
  let rec check stack i =
    if i = String.length s then stack = []
    else match s.[i] with
    | '(' | '[' | '{' as c -> check (c :: stack) (i + 1)
    | ')' | ']' | '}' as c ->
      (match stack with
       | top :: rest when top = matching c -> check rest (i + 1)
       | _ -> false)
    | _ -> check stack (i + 1)
  in
  check [] 0

let () =
  assert (is_balanced "([]{})" = true);
  assert (is_balanced "([)]" = false);
  assert (is_balanced "((()))" = true);
  assert (is_balanced "[{()}]" = true);
  assert (is_balanced "(" = false);
  assert (is_balanced "" = true);
  Printf.printf "All balanced parentheses tests passed!\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_balanced() {
        assert!(is_balanced("([]{})"));
        assert!(is_balanced("((()))"));
        assert!(is_balanced("[{()}]"));
        assert!(is_balanced(""));
    }

    #[test]
    fn test_unbalanced() {
        assert!(!is_balanced("([)]"));
        assert!(!is_balanced("("));
        assert!(!is_balanced(")"));
        assert!(!is_balanced("((())"));
    }

    #[test]
    fn test_with_other_chars() {
        assert!(is_balanced("a(b[c]d)e"));
    }

    #[test]
    fn test_recursive() {
        assert!(is_balanced_recursive("([]{})"));
        assert!(!is_balanced_recursive("([)]"));
        assert!(is_balanced_recursive(""));
    }
}

Deep Comparison

Balanced Parentheses — OCaml vs Rust Comparison

Core Insight

The stack data structure is central to bracket matching. OCaml models the stack as an immutable list (push = cons, pop = pattern match on head). Rust uses Vec<char> with push()/pop(). The Option return from pop() naturally handles the empty-stack case.

OCaml Approach

A recursive function carries the stack as a list parameter. Pattern matching destructures both the current character and the stack top simultaneously. The functional style means no mutation — each recursive call gets a new stack state.

Rust Approach

Iterative with Vec::push() and Vec::pop(). pop() returns Option<char>, so comparing with Some('(') handles both the empty-stack and wrong-bracket cases in one expression. The imperative style with early return false is idiomatic.

Comparison Table

Aspect	OCaml	Rust
Memory	List stack (cons cells)	Vec stack (contiguous memory)
Null safety	Pattern match on list	`Option<char>` from `pop()`
Errors	Returns false	Returns false
Iteration	Recursive with index	`for c in s.chars()`
Stack op	`c :: stack` / `h :: t`	`push(c)` / `pop()`

Things Rust Learners Should Notice

**Vec::pop() returns Option<T>** — no panics on empty, unlike some languages

**Pattern matching on Option** — if stack.pop() != Some('(') is concise and safe

**Vec is a great stack** — O(1) amortized push/pop, cache-friendly, unlike linked list

Early return — return false inside a for loop is idiomatic Rust for short-circuiting

Exercises

Return mismatch position: Return Result<(), (usize, char)> where the error contains the position and character where balancing failed. Use enumerate() on the char iterator.

Nesting depth: Write max_nesting_depth(s: &str) -> usize that returns the maximum nesting depth of parentheses without checking for balance.

Generate balanced: Write generate_balanced(n: usize) -> Vec<String> that generates all balanced parenthesis strings of exactly n pairs. This is the Catalan number problem (C(n) = (2n choose n) / (n+1)).

Generate all balanced strings: Implement generate_balanced(n: usize) -> Vec<String> that generates all balanced parenthesis strings of length 2n using backtracking (Catalan number C(n) results).

Score of parentheses: Implement score(s: &str) -> Result<u32, String> computing the "score" where () = 1, AB = score(A) + score(B), and (A) = 2 * score(A).

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust

Tutorial Video

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Balanced Parentheses — OCaml vs Rust Comparison

Core Insight

OCaml Approach

Rust Approach

Comparison Table

Things Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos