mul_div.rs

#[derive(Debug, Clone, Copy)]
enum Token {
  Num(i64),
  Add,
  Sub,
  Mul,
  Div,
}

enum AST {
  Num(i64),
  BinOp(Box<AST>, Token, Box<AST>),
}

fn parse(tokens: &[Token]) -> Result<AST, String> {
  parse_add_sub(tokens).map(|e| e.0)
}

fn parse_add_sub(tokens: &[Token]) -> Result<(AST, &[Token]), String> {
  fn internal(lhs: AST, tokens: &[Token]) -> Result<(AST, &[Token]), String> {
    match tokens.split_first() {
      Some((op @ (Token::Add | Token::Sub), tokens)) => {
        let (rhs, tokens) = parse_mul_div(tokens)?;
        internal(AST::BinOp(
          Box::new(lhs),
          *op,
          Box::new(rhs)
        ), tokens)
      },
      _ => Ok((lhs, tokens)),
    }
  }
  let (lhs, tokens) = parse_factor(tokens)?;
  internal(lhs, tokens)
}

fn parse_mul_div(tokens: &[Token]) -> Result<(AST, &[Token]), String> {
  fn internal(lhs: AST, tokens: &[Token]) -> Result<(AST, &[Token]), String> {
    match tokens.split_first() {  
      Some((op @ (Token::Mul | Token::Div), tokens)) => {
        let (rhs, tokens) = parse_factor(tokens)?;
        internal(AST::BinOp(
          Box::new(lhs),
          *op,
          Box::new(rhs)
        ), tokens)
      },
      _ => Ok((lhs, tokens)),
    }
  }
  let (lhs, tokens) = parse_factor(tokens)?;
  internal(lhs, tokens)
}

fn parse_factor(tokens: &[Token]) -> Result<(AST, &[Token]), String> {
  match tokens.split_first() {
    Some((Token::Num(n), rest)) => Ok((AST::Num(*n), rest)),
    _ => Err(format!("syntax error: {:#?}", tokens)),
  }
}

impl AST {
  fn eval(&self) -> i64 {
    match self {
      AST::Num(n) => *n,
      AST::BinOp(l, Token::Add, r) => l.eval() + r.eval(),
      AST::BinOp(l, Token::Sub, r) => l.eval() - r.eval(),
      AST::BinOp(l, Token::Mul, r) => l.eval() * r.eval(),
      AST::BinOp(l, Token::Div, r) => l.eval() / r.eval(),
      AST::BinOp(_l, _, _r) => unreachable!(),
    }
  }
}

fn main() {
  let expr = parse(&[
    Token::Num(1),
    Token::Add,
    Token::Num(2),
    Token::Mul,
    Token::Num(4)
  ]).unwrap();
  println!("{}", expr.eval());
}