Shared via Rust Playground

playground.rs

// Basic calculator with algebraic notation. Baby's first parser in Rust.
use std::io;

#[derive(PartialEq,Clone,Copy,Debug)]
enum Parens {
    Begin,
    End
}


#[derive(PartialEq,Clone,Copy,Debug)]
enum Binop {
    Plus,
    Minus,
    Times,
    Divide,
}

fn priority(b : Binop) -> u64 {
    match b {
        Binop::Plus => 10,
        Binop::Minus => 10,
        Binop::Times => 20,
        Binop::Divide => 20,
    }
}

fn add(x :f64 ,y :f64) -> f64 {x + y}
fn sub(x :f64 ,y :f64) -> f64 {x - y}
fn mul(x :f64 ,y :f64) -> f64 {x*y}
fn div(x :f64 ,y :f64) -> f64 {x/y}

fn operator (op: Binop) -> fn(f64,f64) -> f64 {
    match op {
        Binop::Plus    => add,
        Binop::Minus   => sub,
        Binop::Times   => mul,
        Binop::Divide  => div,
    }
}

fn op_print (op: Binop) -> String {
    match op {
        Binop::Plus    => "+".to_string(),
        Binop::Minus   => "-".to_string(),
        Binop::Times   => "*".to_string(),
        Binop::Divide  => "/".to_string(),
    }
}


#[derive(PartialEq,Clone,Copy,Debug)]
enum Number {
    Float(f64),
}

fn to_float(num : Number) -> f64 {
    match num {
        Number::Float(num) => num,
    }
}

#[derive(PartialEq,Clone,Copy,Debug)]
enum Token {
    Number(Number),
    BinaryOperator(Binop),
    Parens(Parens),
}




fn read_token(s : &str) -> Token {
    match s {
        ")" => Token::Parens(Parens::Begin), // Parentheses are effectively 
        "(" => Token::Parens(Parens::End),   // read right to left.
        "+" => Token::BinaryOperator(Binop::Plus),
        "-" => Token::BinaryOperator(Binop::Minus),
        "*" => Token::BinaryOperator(Binop::Times),
        "/" => Token::BinaryOperator(Binop::Divide),
        num => Token::Number(Number::Float(num.parse::<f64>().unwrap())),
    }
}


fn tokenize(s : String) -> Vec<Token> {
    s.split_whitespace().map(read_token).collect()
}




#[derive(PartialEq,Clone,Debug)]
enum Expr {
    BinaryOperator(Binop,Box<Expr>,Box<Expr>),
    Number(Number),

}

#[derive(PartialEq,Clone,Copy,Debug)]
enum StackOp {
    BinaryOperator(Binop),
    OpenParens
}

#[derive(PartialEq,Clone,Copy,Debug)]
enum ParseErr {
    ArityError,
    ParensMatchError,
    ReadError,
    EndExprError
}


// Djkstra's shunting yard algorithm.
fn parse(mut tokens : Vec<Token>) -> Result<Expr,ParseErr> {
    let mut expr_stack : Vec<Expr> = Vec::new();
    let mut op_stack : Vec<StackOp> = Vec::new();

    let apply_binop = |op : Binop, expr_stack : &mut Vec<Expr> | -> Result<(),ParseErr>
    {let fst = try!(expr_stack.pop().ok_or(ParseErr::ArityError));
     let snd = try!(expr_stack.pop().ok_or(ParseErr::ArityError));
     Ok(expr_stack.push(Expr::BinaryOperator(op ,Box::new(fst),Box::new(snd))))};

    while let Some(head) = tokens.pop() {
        match head {
            Token::Number(num) => expr_stack.push(Expr::Number(num)),

            Token::BinaryOperator(bin) => {
                while let Some(sop) = op_stack.pop() {
                    match sop {
                        StackOp::BinaryOperator(bin2) if  priority(bin2) >= priority(bin)
                            => try!(apply_binop(bin2,&mut expr_stack)),
                        x   => {
                            op_stack.push(x);
                            break
                        }
                    }
                }
                op_stack.push(StackOp::BinaryOperator(bin));
                if expr_stack.len() != op_stack.iter().filter(|&&x| if let StackOp::BinaryOperator(_) = x {true} else {false}).count() {
                    return Err(ParseErr::ReadError)
                }
            },

            Token::Parens(Parens::Begin) => op_stack.push(StackOp::OpenParens),
            Token::Parens(Parens::End) => 
                while let Some(sop) = op_stack.pop() {
                    match sop {
                        StackOp::BinaryOperator(op) => try!(apply_binop(op,&mut expr_stack)),
                        StackOp::OpenParens => break,
                    }
                }

        }
    }

    while let Some(sop) = op_stack.pop() {
        match sop {
            StackOp::OpenParens => return Err(ParseErr::ParensMatchError),
            StackOp::BinaryOperator(op) => {
                try!(apply_binop(op,&mut expr_stack))
            },
        }
    }

    if expr_stack.is_empty() || expr_stack.len() > 1 {
        return Err(ParseErr::EndExprError)
    }
    Ok(expr_stack.pop().unwrap())
}


fn eval(ex : &Expr) -> Number {
    match ex {
        &Expr::Number(ref num) => num.clone(),
        &Expr::BinaryOperator(bin, ref ex1, ref ex2) =>
            Number::Float(
                operator(bin)( to_float(eval(ex1)) , to_float(eval(ex2)) )
            )
    }
}


fn parsetree_to_sexp(ex : &Expr) -> String {
    match ex {
        &Expr::Number(Number::Float(ref num)) => num.to_string(),
        &Expr::BinaryOperator(bin, ref ex1, ref ex2) =>
        "(".to_string() + &op_print(bin)+ " " + &parsetree_to_sexp(ex1) + " " + &parsetree_to_sexp(ex2) + ")"
    }
}


fn repl() {
    loop {
        let mut input = String::new();
        io::stdin().read_line(&mut input).expect("read error");

        let parsetree = parse(tokenize(input));

        let output = parsetree.as_ref().map(eval);
        let sexpr = parsetree.as_ref().map(parsetree_to_sexp);

        println!("Result of expr is: {:?}", output);
        println!("The AST of your expression is: {:?}", sexpr );

    }

}



fn main() {
    let input = "2 + 5 * ( 1 + 3 ) / 2".to_string();

    let parsetree = parse(tokenize(input));

    let output = parsetree.as_ref().map(eval);
    let sexpr = parsetree.as_ref().map(parsetree_to_sexp);

    println!("Result of expr is: {:?}", output);
    println!("The AST of your expression is: {:?}", sexpr);
}