seanjensengrey · February 4, 2017 18:19 · Feb 4, 2017
diff --git a/main.rs b/main.rs
@@ -0,0 +1,139 @@
+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),
+    }
+}