parse_parens.rs

use std::{cmp};

type ParseResult<T> = Result<T, String>;

// Parse a string containing any number of balanced parentheses 
// groups. For example these are valid:
//
//   () => 1 group, max depth 1
//   (())() => 2 groups, max depth 2
//   (()()()(())()) => 1 group, max depth 3
//  
// While these are considered invalid
//
//   ()(
//   )
//   ((())()
//   (a)
//
// Returns the number of parentheses groups found, and the max 
// depth (in the sense of viewing the parens groups as a tree).
fn parse_parens(chars: &mut str::Chars) -> ParseResult<(u32, u32)> {
    let mut depth: u32 = 0;
    let mut max_depth = 0;
    let mut num_groups = 0;
    loop {
        match chars.next() {
            Some('(') => {
                depth += 1;
                max_depth = cmp::max(max_depth, depth);
            },
            Some(')') if depth > 0 => {
                depth -= 1;
                if depth == 0 {num_groups += 1}
            },
            Some(')') => return Err("Unbalanced parens".to_string()),
            Some(c) =>
                return Err(format!("Unexpected character '{}'", c)),
            None if depth == 0 => return Ok((max_depth, num_groups)),
            None => return Err("Not enough closing parens".to_string()),
        }
    }
}

// Same as parse_parens, but recursive.
fn parse_parens_rec(chars: &mut str::Chars, depth: u32, max: u32, num: u32)
                    -> ParseResult<(u32, u32)> {
    match chars.next() {
        Some('(') =>
            parse_parens_rec(chars, depth + 1, cmp::max(depth + 1, max), num),
        Some(')') if depth == 1 =>
            parse_parens_rec(chars, depth - 1, max, num + 1),
        Some(')') if depth > 0 =>
            parse_parens_rec(chars, depth - 1, max, num),
        Some(')') => Err("Closing parens at depth 0".to_string()),
        Some(c) => Err(format!("Unexpected character '{}'", c)),
        None if depth == 0 => Ok((max, num)),
        None => Err("Not enough closing parens".to_string()),
    }
}


fn main() {
    let parens_groups = ["", "()(())", "((()))", "(", "())", "(x)"];
    for s in parens_groups.iter() {
        println!("Input: {:?}", s);
        match parse_parens(&mut s.chars()) {
            Ok((depth, groups)) =>
                println!("{} groups, max depth of {}", groups, depth),
            Err(err) => println!("Parse error: {}", err),
        }
        // Try the same thing with the recursive version
        match parse_parens_rec(&mut s.chars(), 0, 0, 0) {
            Ok((depth, groups)) =>
                println!("{} groups, max depth of {}", groups, depth),
            Err(err) => println!("Parse error: {}", err),
        }
    }
}