064: Balanced Parentheses

Difficulty: ⭐ Level: Foundations Check whether every opening bracket has a matching closing bracket in the right order — the classic stack algorithm.

The Problem This Solves

You're writing a linter, a simple expression parser, or checking whether a JSON/HTML template has unclosed tags. The problem always reduces to the same question: are the brackets balanced? The naive approach — counting opens vs closes — fails for `"([)]"`: same count, wrong order. You need a stack. The algorithm is simple: push opening brackets, pop on closing ones, and check the popped value matches. At the end, the stack must be empty. This is one of the most common interview problems precisely because it's clean and teaches an important concept: some problems need memory of the past, and the right data structure (a stack) makes the solution obvious.

The Intuition

Think of it like checking parentheses in a math textbook. When you see `(`, you mentally "open a tab." When you see `)`, you close the most recent open tab. If the tab you're closing doesn't match what you opened, something is wrong. If you reach the end with open tabs remaining, also wrong. In Python you'd use a list as a stack (`stack.append()` / `stack.pop()`). In JavaScript, same thing with an array. Rust uses `Vec<char>` with `.push()` and `.pop()`. The Rust version shines in the pattern match — each closing bracket is handled in its own branch, and `pop()` returns `Option<char>`, forcing you to handle the "nothing on the stack" case explicitly.

How It Works in Rust

pub fn is_balanced(s: &str) -> bool {
 let mut stack: Vec<char> = Vec::new();

 for c in s.chars() {
     match c {
         '(' | '[' | '{' => stack.push(c),  // push opening brackets
         ')' => {
             if stack.pop() != Some('(') { return false; }
         }
         ']' => {
             if stack.pop() != Some('[') { return false; }
         }
         '}' => {
             if stack.pop() != Some('{') { return false; }
         }
         _ => {}  // ignore letters, spaces, etc.
     }
 }
 stack.is_empty()  // unmatched opens would remain
}

`pop()` returns `Option<char>` — `None` if the stack is empty (unmatched close bracket), `Some(c)` otherwise. Comparing directly to `Some('(')` handles both the empty-stack case and the wrong-bracket case in one check.

What This Unlocks

Parsing — any recursive/nested structure (HTML, JSON, code) can be validated with a stack
Expression evaluation — extend this to evaluate arithmetic with operator precedence using two stacks
State machines — the "push on open, pop on close" pattern generalizes to any context where you need to match paired events

Key Differences

Concept	OCaml	Rust
Stack data structure	`list` (immutable, cons/hd)	`Vec<char>` with `.push()` / `.pop()`
Pop result	Pattern match on list head	`pop()` returns `Option<char>`
Empty stack check	`= []`	`.is_empty()`
Match on char	`match c with \	'(' -> ...`	`match c { '(' \	'[' \	'{' => ... }`

/// # 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(""));
    }
}

fn main() {
    println!("{:?}", is_balanced("([]{})"));
    println!("{:?}", is_balanced("((()))"));
    println!("{:?}", is_balanced("[{()}]"));
}

(* 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"

📊 Detailed 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

1. `Vec::pop()` returns `Option<T>` — no panics on empty, unlike some languages 2. Pattern matching on `Option` — `if stack.pop() != Some('(')` is concise and safe 3. `Vec` is a great stack — O(1) amortized push/pop, cache-friendly, unlike linked list 4. Early return — `return false` inside a `for` loop is idiomatic Rust for short-circuiting