#![feature(slice_patterns)]

#[derive(Debug, PartialEq)]
pub enum AlgItem {
    R,
    U,
    Pair(Vec<AlgItem>, Vec<AlgItem>),
}

fn parse_one(h: char, t: &[char]) -> Result<(AlgItem, &[char]), &'static str> {
    match h {
        'R' => Ok((AlgItem::R, t)),
        'U' => Ok((AlgItem::U, t)),
        '[' => parse_many(t, Some(';'))
            .and_then(|m1| parse_many(m1.1, Some(']')).map(|m2| (AlgItem::Pair(m1.0, m2.0), m2.1))),
        _ => Err("Expected R, U, or ["),
    }
}

fn parse_many(s: &[char], exp: Option<char>) -> Result<(Vec<AlgItem>, &[char]), &'static str> {
    fn step(
        mut acc: Vec<AlgItem>,
        exp: Option<char>,
        input: &[char],
    ) -> Result<(Vec<AlgItem>, &[char]), &'static str> {
        match input {
            [h, t @ ..] if Some(h) == exp.as_ref() => Ok((acc, t)),
            [h, t @ ..] => parse_one(*h, t).and_then(|a| {
                acc.push(a.0);
                step(acc, exp, a.1)
            }),
            [] => Ok((acc, &[])),
        }
    }
    step(Vec::new(), exp, s)
}

pub fn parse(input: &str) -> Result<Vec<AlgItem>, &'static str> {
    let input: Vec<char> = input.chars().collect();
    parse_many(&input, None).map(|m| m.0)
}

#[test]
fn basic() {
    assert_eq!(Ok(vec![AlgItem::R]), parse("R"));
    assert_eq!(Ok(vec![AlgItem::U]), parse("U"));
    assert_eq!(
        Ok(vec![AlgItem::Pair(vec![AlgItem::R], vec![AlgItem::U])]),
        parse("[R;U]")
    );
    assert_eq!(Err("Expected R, U, or ["), parse("O"));
}