#[derive(Clone, Debug)]
enum Lex {
    LeftParen,
    Symbol(String),
    RightParen,
}

#[derive(Debug)]

enum Ast {
    Leaf(String),
    List(Vec<Ast>),
}

use Lex::*;
fn parse(lexemes: Box<Iterator<Item = Lex>>) -> (Option<(Ast, Box<Iterator<Item = Lex>>)>) {
    println!("parse");
    let mut result = Vec::new();
    let mut lexemes = lexemes;
    while let Some(l) = lexemes.next() {
        println!("l = {:?}", l);
        match l {
            LeftParen => {
                let rest = parse(lexemes).unwrap();
                result.push(rest.0);
                lexemes = rest.1
            }
            Symbol(x) => {
                result.push(Ast::Leaf(x));
            }
            RightParen => {
                return Some((Ast::List(result), lexemes));
            }
        }
    }
    if result.len() == 1 {
        Some((result.pop().unwrap(), lexemes))
    } else {
        None
    }
}
use std::mem::replace;
fn parse2(lexemes: Box<Iterator<Item = Lex>>) -> Ast {
    let mut stack = Vec::new();

    let mut result = Vec::new();
    let mut lexemes = lexemes;
    while let Some(l) = lexemes.next() {
        println!("l = {:?}", l);
        match l {
            LeftParen => {
                stack.push(replace(&mut result, Vec::new()));
            }
            Symbol(x) => {
                result.push(Ast::Leaf(x));
            }
            RightParen => {
                let old_result = stack.pop().unwrap();
                let last_paren = replace(&mut result, old_result);
                result.push(Ast::List(last_paren ))
            }
        }
    }
    result.pop().unwrap()
}


fn main() {
    //(sresh 1 (+ 1 2) 3 7)
    let x = vec![
        LeftParen,
        Symbol("sresh".to_string()),
        LeftParen,
        Symbol("+".to_string()),
        Symbol("1".to_string()),
        Symbol("2".to_string()),
        RightParen,
        Symbol("3".to_string()),
        Symbol("7".to_string()),
        RightParen,
    ];
    println!("new: {:?}", parse(Box::new(x.clone().into_iter())).unwrap().0);

    println!("new: {:?}", parse2(Box::new(x.into_iter())))
}