main.rs

use std::collections::VecDeque;
use std::str::FromStr;

#[derive(Debug, Clone)]
enum OperatorToken {
    Plus,
    Minus,
    Multiply,
    Divide,
}

impl OperatorToken {
    pub fn precedence(&self) -> u8 {
        match *self {
            OperatorToken::Multiply | OperatorToken::Divide => 10,
            OperatorToken::Plus | OperatorToken::Minus => 8,
        }
    }

    pub fn operation(&self, operand1: i32, operand2: i32) -> i32 {
        match *self {
            OperatorToken::Plus => operand1 + operand2,
            OperatorToken::Minus => operand1 - operand2,
            OperatorToken::Multiply => operand1 * operand2,
            OperatorToken::Divide => operand1 / operand2,
        }
    }
}

#[derive(Debug, Clone)]
struct Number(i32);

#[derive(Debug, Clone)]
enum Token {
    Value(Number),

    Operator(OperatorToken),
}

/// Tokenize an Expression
/// An expression consists of integers and +-/*,
/// separated by spaces for simplicity
fn tokenize_expr(expr: &str) -> Result<Vec<Token>, String> {
    let mut word_iter = expr.split_whitespace();
    let mut tokens: Vec<Token> = Vec::new();

    loop {
        match word_iter.next() {
            Some("+") => tokens.push(Token::Operator(OperatorToken::Plus)),
            Some("-") => tokens.push(Token::Operator(OperatorToken::Minus)),
            Some("*") => tokens.push(Token::Operator(OperatorToken::Multiply)),
            Some("/") => tokens.push(Token::Operator(OperatorToken::Divide)),
            Some(word) => {
                if i32::from_str(word).is_ok() {
                    tokens.push(Token::Value(Number(i32::from_str(word).unwrap())))
                } else {
                    return Err(format!("{} is not +-*/ or a number.", word));
                }
            }

            None => break,
        }
    }

    Ok(tokens)
}

fn parse_expression(tokens: Vec<Token>) -> Result<VecDeque<Token>, String> {
    let mut token_iter = tokens.iter();

    let mut output_queue: VecDeque<Token> = VecDeque::new();
    let mut operator_stack: Vec<OperatorToken> = Vec::new();

    loop {
        let token = token_iter.next();
        match token {
            Some(number @ &Token::Value(_)) => output_queue.push_back((*number).clone()),
            Some(&Token::Operator(ref operator)) => {
                if !operator_stack.is_empty() {
                    let top_op = operator_stack.last().unwrap().clone();
                    if operator.precedence() <= top_op.precedence() {
                        let top_op = operator_stack.pop().unwrap();
                        output_queue.push_back(Token::Operator(top_op))
                    }
                }
                operator_stack.push(operator.clone());
            }
            None => break,
        }
    }

    while !operator_stack.is_empty() {
        output_queue.push_back(Token::Operator(operator_stack.pop().unwrap()));
    }

    Ok(output_queue)
}

fn eval(queue: &mut VecDeque<Token>) -> Result<i32, String> {
    let mut stack: Vec<i32> = Vec::new();

    while !queue.is_empty() {
        match queue.pop_front() {
            Some(Token::Value(Number(number))) => stack.push(number),
            Some(Token::Operator(op)) => {
                if stack.len() >= 2 {
                    let operand2 = stack.pop().unwrap();
                    let operand1 = stack.pop().unwrap();

                    stack.push(op.operation(operand1, operand2))
                } else {
                    return Err(format!("Operator {:?} requires two operands!", op));
                }
            }
            None => break,
        }
    }

    // If expression is well formed, there will only be the result on the stack
    assert!(stack.len() == 1);
    Ok(stack[0])
}

fn main() {
    match tokenize_expr("3 + 4 * 5 / 2") {
        Ok(tokens) => {
            match parse_expression(tokens) {
                Ok(ref mut queue) => {
                    match eval(queue) {
                        Ok(result) => println!("Result is: {}", result),
                        Err(e) => println!("Error in evaluation: {:?}", e),
                    }
                }
                Err(e) => println!("Error in parsing expression: {:?}", e),
            }
        }
        Err(e) => println!("Error tokenizing expression: {:?}", e),
    }
}