parser.rs

extern crate regex;
use regex::Regex;

#[derive(Debug)]
enum ParseResult<T> {
    Success { result: T, next: String },
    Failure
}

impl<T> ParseResult<T> {
    fn flat_map<R, F>(self, f: F) -> ParseResult<R> where F: FnOnce(T, String) -> ParseResult<R> {
        match self {
            ParseResult::Failure => ParseResult::Failure,
            ParseResult::Success { result, next } => f(result, next)
        }
    }
    fn map<R, F>(self, f: F) -> ParseResult<R> where F: FnOnce(T) -> R {
        self.flat_map(|result, next| ParseResult::Success {
            result: f(result),
            next: next
        })
    }
    fn seq<R>(self, that: R) -> ParseResult<R> {
        self.map(|_| that)
    }
    fn or<F>(self, that: F) -> ParseResult<T> where F: FnOnce() -> ParseResult<T> {
        match self {
            ParseResult::Failure => that(),
            ParseResult::Success { result, next } => ParseResult::Success { result: result, next: next }
        }
    }
}

fn rep<R, F>(input: String, f: F) -> ParseResult<Vec<R>> where F: Fn(String) -> ParseResult<R> {
    let mut results = Vec::new();
    let mut next_input = input;
    loop {
        match f(next_input.clone()) {
            ParseResult::Failure => break,
            ParseResult::Success { result, next } => {
                results.push(result);
                next_input = next;
            }
        }
    }
    ParseResult::Success { result: results, next: next_input }
}

fn parse_string(expected: &str, input: String) -> ParseResult<String> {
    if expected.len() <= input.len() {
        let (actual, rest) = input.split_at(expected.len());
        if actual == expected {
            ParseResult::Success {
                result: String::from(actual),
                next: String::from(rest)
            }
        } else {
            ParseResult::Failure
        }
    } else {
        ParseResult::Failure
    }
}

fn parse_regex(regex: Regex, input: String) -> ParseResult<String> {
    match regex.captures(input.as_str()) {
        None => ParseResult::Failure,
        Some(captures) => match captures.at(0) {
            None => ParseResult::Failure,
            Some(capture) => ParseResult::Success {
                result: String::from(capture),
                next: String::from(&input[capture.len()..])
            }
        }
    }
}

#[derive(Debug)]
enum AST {
    Num(i32),
    Exp(Box<AST>, Vec<Op>),
}

impl AST {
    fn app(self, ops: Vec<Op>) -> AST {
        if ops.is_empty() {
            self
        } else {
            AST::Exp(Box::new(self), ops)
        }
    }
    fn eval(self) -> i32 {
        match self {
            AST::Num(value) => value,
            AST::Exp(lhs, ops) => {
                let mut value = lhs.eval();
                for op in ops {
                    value = op.eval(value)
                }
                value
            }
        }
    }
}

#[derive(Debug)]
enum Op {
    Add(Box<AST>),
    Sub(Box<AST>),
    Mul(Box<AST>),
    Div(Box<AST>),
}

impl Op {
    fn eval(self, lhs: i32) -> i32 {
        match self {
            Op::Add(ast) => lhs + ast.eval(),
            Op::Sub(ast) => lhs - ast.eval(),
            Op::Mul(ast) => lhs * ast.eval(),
            Op::Div(ast) => lhs / ast.eval(),
        }
    }
}

fn parse_expr(input: String) -> ParseResult<AST> {
    parse_term(input).flat_map(|result, next| {
        rep(next, |input| {
            parse_add(input.clone()).or(|| parse_sub(input))
        }).map(|ops| result.app(ops))
    })
}

fn parse_add(input: String) -> ParseResult<Op> {
    parse_string("+", input).flat_map(|_, next| {
        parse_term(next).map(|result| Op::Add(Box::new(result)))
    })
}

fn parse_sub(input: String) -> ParseResult<Op> {
    parse_string("-", input).flat_map(|_, next| {
        parse_term(next).map(|result| Op::Sub(Box::new(result)))
    })
}

fn parse_term(input: String) -> ParseResult<AST> {
    parse_factor(input).flat_map(|result, next| {
        rep(next, |input| {
            parse_mul(input.clone()).or(|| parse_div(input))
        }).map(|ops| result.app(ops))
    })
}

fn parse_mul(input: String) -> ParseResult<Op> {
    parse_string("*", input).flat_map(|_, next| {
        parse_factor(next).map(|result| Op::Mul(Box::new(result)))
    })
}

fn parse_div(input: String) -> ParseResult<Op> {
    parse_string("/", input).flat_map(|_, next| {
        parse_factor(next).map(|result| Op::Div(Box::new(result)))
    })
}

fn parse_factor(input: String) -> ParseResult<AST> {
    parse_num(input.clone()).or(|| parse_parentheses(input))
}

fn parse_num(input: String) -> ParseResult<AST> {
    parse_regex(Regex::new(r"^\d+").unwrap(), input).flat_map(|result, next| {
        match result.as_str().parse() {
            Ok(n) => ParseResult::Success { result: AST::Num(n), next: next },
            Err(_) => ParseResult::Failure
        }
    })
}

fn parse_parentheses(input: String) -> ParseResult<AST> {
    parse_string("(", input).flat_map(|_, next| {
        parse_expr(next).flat_map(|result, next| {
            parse_string(")", next).seq(result)
        })
    })
}

fn main() {
    println!("{:?}", parse_expr(String::from("1*2*(3-4)*5+6*7+8*9")).map(|ast| ast.eval())); // => 104
}