main5.rs

extern crate nom;

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::char,
    character::complete::{digit1, multispace0},
    combinator::{cut, map, opt},
    error::ParseError,
    multi::{fold_many0, many0, separated_list},
    sequence::{delimited, preceded, tuple},
    IResult,
};

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Op {
    Eq,
    Neq,
    Add,
    Sub,
    Mul,
    Div,
    Pow,
    Minus,
    Not,
    Par
}

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    Atom(Atom),
    BinOp(Op, Box<Expr>, Box<Expr>),
    Unary(Op, Box<Expr>),
}

#[derive(Debug, Clone, PartialEq)]
pub enum Atom {
    Num(i32),
    // Identifier
    // Function application
}


pub fn parse_i32(i: &str) -> IResult<&str, Expr> {
    map(digit1, |digit_str: &str| {
        Expr::Atom(Atom::Num(digit_str.parse::<i32>().unwrap()))
    })(i)
}

fn parse_uop(i: &str) -> IResult<&str, Op> {
    preceded(
        multispace0,
        alt((map(tag("-"), |_| Op::Minus), map(tag("!"), |_| Op::Not))),
    )(i)
}

fn parse_mulop(i: &str) -> IResult<&str, Op> {
    preceded(
        multispace0,
        alt((map(tag("*"), |_| Op::Mul), map(tag("/"), |_| Op::Div))),
    )(i)
}

fn parse_addop(i: &str) -> IResult<&str, Op> {
    preceded(
        multispace0,
        alt((map(tag("+"), |_| Op::Add), map(tag("-"), |_| Op::Sub))),
    )(i)
}

//   expr       ::= eq-expr
//   eq-expr    ::= add-expr ( ( '==' | '!=' ) add-expr ) *
//   add-expr   ::= mul-expr ( ( '+' | '-' ) mul-expression ) *
//   mul-expr   ::= primary ( ( '*' | '/' ) terminal ) *
//   terminal   ::= '(' expr ')' | NUMBER | VARIABLE | '-' primary

fn parse_expr(i: &str) -> IResult<&str, Expr> {
    parse_additative(i)
}

fn parse_additative(i: &str) -> IResult<&str, Expr> {
    //map(tuple((parse_terminal, opt(parse_rhs)), |((_,t), _)| t))(i)
    map(
        tuple((
            parse_multiplicative,
            many0(tuple((parse_addop, parse_multiplicative))),
        )),
        |(t, m)| {
            m.iter()
                .fold(t, |l, (op, r)| climb(l, op.clone(), r.clone()))
        },
    )(i)
}

fn binop(op: Op, l: Expr, r: Expr) -> Expr {
    Expr::BinOp(op, Box::new(l), Box::new(r))
}

fn climb(l: Expr, op: Op, r: Expr) -> Expr {
    match r.clone() {
        Expr::BinOp(r_op, r_l, r_r) => {
            let (prec, ass) = climb_op(&op);
            let (r_prec, _) = climb_op(&r_op);
            if r_prec
                < prec
                    + match ass {
                        Ass::Left => 1,
                        _ => 0,
                    }
            {
                binop(r_op, binop(op, l, *r_l), *r_r)
            } else {
                binop(op, l, r)
            }
        }
        _ => binop(op, l, r),
    }
}

fn parse_multiplicative(i: &str) -> IResult<&str, Expr> {
    map(
        tuple((
            parse_terminal,
            many0(tuple((parse_mulop, parse_multiplicative))),
        )),
        |(t, m)| {
            m.iter()
                .fold(t, |l, (op, r)| climb(l, op.clone(), r.clone()))
        },
    )(i)
}

fn parse_terminal(i: &str) -> IResult<&str, Expr> {
    preceded(
        multispace0,
        alt((
            parse_i32,
            map(tuple((parse_uop, parse_terminal)), |(uop, e)| {
                Expr::Unary(uop, Box::new(e))
            }),
            map(parse_parenthesis(parse_expr), |e| Expr::Unary(Op::Par, Box::new(e)))
        )),
    )(i)
}

// helpers
fn parse_parenthesis<'a, O, F, E>(inner: F) -> impl Fn(&'a str) -> IResult<&'a str, O, E>
where
    F: Fn(&'a str) -> IResult<&'a str, O, E>,
    E: ParseError<&'a str>,
{
    // delimited allows us to split up the input
    // cut allwos us to consume the input (and prevent backtracking)
    delimited(char('('), preceded(multispace0, inner), cut(char(')')))
}

fn main() {
    let p = parse_additative("1-(1+1)-1)").unwrap().1;
    println!("{:?} {} {}", p, math_eval(&p), 1-(1+1)-1);

    // let p = parse_additative("5*(20+2)/4").unwrap().1;
    // println!("{:?} {} {}", p, math_eval(&p), 5 * (20 + 2) / 4);
}

fn math_expr(e: &Expr) -> String {
    match e {
        Expr::Atom(Atom::Num(i)) => format!("{}", i),
        Expr::BinOp(op, l, r) => format!("({:?}, {}, {})", op, math_expr(l), math_expr(r)),
        Expr::Unary(op, e) => format!("({:?}, {})", op, math_expr(e)),
    }
}

fn math_eval(e: &Expr) -> i32 {
    match e {
        Expr::Atom(Atom::Num(i)) => *i,
        Expr::BinOp(op, l, r) => {
            let lv = math_eval(l);
            let rv = math_eval(r);
            match op {
                Op::Add => lv + rv,
                Op::Sub => lv - rv,
                Op::Mul => lv * rv,
                Op::Div => lv / rv,
                Op::Pow => lv.pow(rv as u32),
                _ => unimplemented!(),
            }
        },
        Expr::Unary(op, e) => {
            let e = math_eval(e);
            match op {
                Op::Par => e,
                Op::Mul => -e,
                _ => unimplemented!(),
            }
        }
        
        _ => unimplemented!(),
    }
}

#[derive(Debug, Copy, Clone, PartialEq)]
enum Ass {
    Left,
    Right,
}

fn climb_op(op: &Op) -> (u8, Ass) {
    match op {
        Op::Add => (1, Ass::Left),
        Op::Sub => (1, Ass::Left),
        Op::Mul => (2, Ass::Left),
        Op::Div => (2, Ass::Left),
        Op::Pow => (3, Ass::Right),
        _ => unimplemented!(),
    }
}