const INPUT: &str = include_str!("../../data/day18");

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Op {
    Sum,
    Mul,
}

impl Op {
    fn apply<T>(self, a: T, b: T) -> T
    where
        T: std::ops::Add<T, Output=T> + std::ops::Mul<T, Output=T>,
    {
        match self {
            Self::Sum => a + b,
            Self::Mul => a * b,
        }
    }
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Elem<T> {
    ParenLeft,
    Op(Op),
    Item(T),
}

impl<T> Elem<T> {
    fn expect_item(self) -> T {
        if let Elem::Item(item) = self {
            item
        } else {
            panic!("Expected item");
        }
    }

    fn expect_op(self) -> Op {
        if let Elem::Op(op) = self {
            op
        } else {
            panic!("Expected op");
        }
    }

    fn expect_paren_left(self) {
        if let Elem::ParenLeft = self {
            ()
        } else {
            panic!("Expected '('");
        }
    }
}

#[derive(Debug)]
struct Stack<T> {
    elems: Vec<Elem<T>>,
    same_precedence: bool,
}

impl<T> Stack<T>
where
    T: std::ops::Add<T, Output=T> + std::ops::Mul<T, Output=T> + std::fmt::Debug,
{
    fn new(same_precedence: bool) -> Self {
        Self {
            elems: Vec::new(),
            same_precedence,
        }
    }

    fn push_item(&mut self, item: T) {
        self.elems.push(Elem::Item(item))
    }

    fn push_op(&mut self, op: Op) {
        self.elems.push(Elem::Op(op))
    }

    fn push_paren_left(&mut self) {
        self.elems.push(Elem::ParenLeft)
    }

    fn _peek_top(&self) -> &Elem<T> {
        &self.elems[self.elems.len() - 1]
    }

    fn _peek_below_top(&self) -> &Elem<T> {
        &self.elems[self.elems.len() - 2]
    }

    fn pop_item(&mut self) -> T {
        self.elems.pop().expect("expect non empty stack").expect_item()
    }

    fn pop_op(&mut self) -> Op {
        self.elems.pop().expect("expect non empty stack").expect_op()
    }

    fn pop_paren_left(&mut self) {
        self.elems.pop().expect("expect non empty stack").expect_paren_left()
    }

    fn _do_reduce_op(&self, finish: bool) -> bool {
        match self._peek_below_top() {
            Elem::Op(Op::Sum) => true,
            Elem::Op(Op::Mul) => finish || self.same_precedence,
            _ => false,
        }
    }

    fn is_empty(&self) -> bool {
        self.elems.is_empty()
    }

    fn eval_top(&mut self, finish: bool) {
        while self.elems.len() > 2 && matches!(self._peek_top(), Elem::Item(_)) && self._do_reduce_op(finish) {
            let value2 = self.pop_item();
            let op = self.pop_op();
            let value1 = self.pop_item();
            self.push_item(op.apply(value1, value2));
        }
    }
}

fn parse<T>(mut line: &str, same_precedence: bool) -> T
where
    T: std::ops::Add<T, Output=T> + std::ops::Mul<T, Output=T> + std::str::FromStr + std::fmt::Debug,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let mut stack = Stack::new(same_precedence);

    loop {
        line = line.trim();
        if line.is_empty() { 
            break;
        }
        if let Some(rem) = line.strip_prefix('+') {
            stack.push_op(Op::Sum);
            line = rem;
        } else if let Some(rem) = line.strip_prefix('*') {
            stack.push_op(Op::Mul);
            line = rem;
        } else if let Some(rem) = line.strip_prefix('(') {
            stack.push_paren_left();
            line = rem;
        } else if let Some(rem) = line.strip_prefix(')') {
            stack.eval_top(true);
            let item = stack.pop_item();
            stack.pop_paren_left();
            stack.push_item(item);
            line = rem;
        } else {
            let num_end = line.find(|c: char| !c.is_ascii_digit()).unwrap_or(line.len());
            let num = line[..num_end].parse::<T>().unwrap();
            stack.push_item(num);
            line = &line[num_end..];
        }
        stack.eval_top(false);
    }
    stack.eval_top(true);
    let item = stack.pop_item();
    assert!(stack.is_empty());
    item
}

fn main() {
    println!("Sum of evaluated lines (simple   math): {}", INPUT.lines().map(|l| parse::<u64>(l, true)).sum::<u64>());
    println!("Sum of evaluated lines (advanced math): {}", INPUT.lines().map(|l| parse::<u64>(l, false)).sum::<u64>());
}