Rust Console RPN Calculator

Question

I've been trying to teach myself Rust, and I decided that a simple console calculator would be a good project to learn from.

use std::io;
extern crate regex;
#[macro_use] extern crate lazy_static;

use regex::Regex;

fn main() {
    loop {
        println!("Enter input:");
        let mut input = String::new();
        io::stdin().read_line(&mut input)
            .expect("Failed to read line");
        let tokens = tokenize(input);
        let stack = shunt(tokens);
        let res = calculate(stack);
        println!("{}", res);
    }
}

#[derive(Debug)]
#[derive(PartialEq)]
enum Token {
    Number (i64),
    Plus,
    Sub,
    Mul,
    Div,
    LeftParen,
    RightParen,
}

/// Tokenizes the input string into a Vec of Tokens.
fn tokenize(mut input: String) -> Vec<Token> {
    lazy_static! {
        static ref NUMBER_RE: Regex = Regex::new(r"^[0-9]+").unwrap();
    }
    let mut res = vec![];
    while !(input.trim_left().is_empty()) {
        input = input.trim_left().to_string();
        input = if let Some((_, end)) = NUMBER_RE.find(&input) {
            let (num, rest) = input.split_at_mut(end);
            res.push(Token::Number(num.parse::<i64>().unwrap()));
            rest.to_string()
        } else {
            res.push(match input.chars().nth(0) {
                Some('+') => Token::Plus,
                Some('-') => Token::Sub,
                Some('*') => Token::Mul,
                Some('/') => Token::Div,
                Some('(') => Token::LeftParen,
                Some(')') => Token::RightParen,
                _ => panic!("Unknown character!")
            });
            input.trim_left_matches(|c| c == '+' ||
                                        c == '-' ||
                                        c == '*' ||
                                        c == '/' ||
                                        c == '(' ||
                                        c == ')').to_string()
        }
    }
    res
}

/// Transforms the tokens created by `tokenize` into RPN using the
/// [Shunting-yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm)
fn shunt(tokens: Vec<Token>) -> Vec<Token> {
    let mut queue: Vec<Token> = vec![];
    let mut stack: Vec<Token> = vec![];
    for token in tokens {
        match token {
            n @ Token::Number(_) => queue.push(n),
            op @ Token::Plus | op @ Token::Sub |
            op @ Token::Mul  | op @ Token::Div => {
                while let Some(o) = stack.pop() {
                    if precedence(&op) <= precedence(&o) {
                        queue.push(o);
                    } else {
                        stack.push(o);
                        break;
                    }
                }
                stack.push(op)
            },
            p @ Token::LeftParen => stack.push(p),
            Token::RightParen => {
                let mut found_paren = false;
                while let Some(op) = stack.pop() {
                    match op {
                        Token::LeftParen => {
                            found_paren = true;
                            break;
                        },
                        _ => queue.push(op)
                    }
                }
                assert!(found_paren)
            }
        }
    }
    while let Some(op) = stack.pop() {
        queue.push(op);
    }
    queue
}

/// Takes a Vec of Tokens converted to RPN by `shunt` and calculates the result
fn calculate(tokens: Vec<Token>) -> i64 {
    let mut stack = vec![];
    for token in tokens {
        match token {
            Token::Number(n) => stack.push(n),
            Token::Plus => {
                let (b, a) = (stack.pop().unwrap(), stack.pop().unwrap());
                stack.push(a + b);
            },
            Token::Sub => {
                let (b, a) = (stack.pop().unwrap(), stack.pop().unwrap());
                stack.push(a - b);
            },
            Token::Mul => {
                let (b, a) = (stack.pop().unwrap(), stack.pop().unwrap());
                stack.push(a * b);
            },
            Token::Div => {
                let (b, a) = (stack.pop().unwrap(), stack.pop().unwrap());
                stack.push(a / b);
            },
            _ => unreachable!() // By the time the token stream gets here, all the LeftParen
                                // and RightParen tokens will have been removed by shunt()
        }
    }
    stack[0]
}

/// Returns the precedence of op
fn precedence(op: &Token) -> usize {
    match op {
        &Token::Plus | &Token::Sub => 1,
        &Token::Mul  | &Token::Div => 2,
        _ => 0,
    }
}

Is there anything that can be improved? In particular

1. Is there any better way to pattern match on the first character of a string and then remove it? That part of the code feels very clunky.
2. Is there a better way to associate the precedence of an operator with its definition? It bugs me to have to write a precedence function in order to get the precedence of an operator.

Answer 1

1. There's no space before the parenthesis on an enum variant

2. derives are combined into one line.

3. Make precedence an inherent method on Token.

4. Inside of precedence, match on the dereference of the value. This avoids the spread of &.

5. There's no need for lazy_static; just create a structure and put the regex in it, the reuse it in the loop.

6. There's no need for the large amount of string allocation. Take in a &str instead of a String and simply slice it up.

7. Instead of trimming the input by the operator characters, skip by the number of bytes the first character was.

8. There's no need to specify the type of parse.

9. The code trims the left multiple times; just do it once.

10. There's no need to specify type of queue as it's inferrable.

11. There's no need to use the @ pattern binding; can just use token.

Larger ideas:

1. Create a newtype around Vec<Token> to indicate that data is in RPN order. Types avoid the need for documentation.

2. Create multiple types of enums; one with parens and one without. Then there's one less place to have an unreachable. If there's subsets, you could embed the subset in the superset.

3. The error handling is pretty rough for the end user. Mismatched parenthesis kill the program instead of explaining the error and letting the user continue. There's no (obvious) way to exit the program other than by killing it or closing stdin (which produces another error message).

---

use std::io;
extern crate regex; // 0.1.80
#[macro_use]
extern crate lazy_static;

use regex::Regex;

fn main() {
    let tokenizer = Tokenizer::new();

    loop {
        println!("Enter input:");
        let mut input = String::new();
        io::stdin()
            .read_line(&mut input)
            .expect("Failed to read line");
        let tokens = tokenizer.tokenize(&input);
        let stack = shunt(tokens);
        let res = calculate(stack);
        println!("{}", res);
    }
}

#[derive(Debug, PartialEq)]
enum Token {
    Number(i64),
    Plus,
    Sub,
    Mul,
    Div,
    LeftParen,
    RightParen,
}

impl Token {
    /// Returns the precedence of op
    fn precedence(&self) -> usize {
        match *self {
            Token::Plus | Token::Sub => 1,
            Token::Mul | Token::Div => 2,
            _ => 0,
        }
    }
}

struct Tokenizer {
    number: Regex,
}

impl Tokenizer {
    fn new() -> Tokenizer {
        Tokenizer {
            number: Regex::new(r"^[0-9]+").expect("Unable to create the regex"),
        }
    }

    /// Tokenizes the input string into a Vec of Tokens.
    fn tokenize(&self, mut input: &str) -> Vec<Token> {
        let mut res = vec![];

        loop {
            input = input.trim_left();
            if input.is_empty() { break }

            let (token, rest) = match self.number.find(input) {
                Some((_, end)) => {
                    let (num, rest) = input.split_at(end);
                    (Token::Number(num.parse().unwrap()), rest)
                },
                _ => {
                    match input.chars().next() {
                        Some(chr) => {
                            (match chr {
                                '+' => Token::Plus,
                                '-' => Token::Sub,
                                '*' => Token::Mul,
                                '/' => Token::Div,
                                '(' => Token::LeftParen,
                                ')' => Token::RightParen,
                                _ => panic!("Unknown character!"),
                            }, &input[chr.len_utf8()..])
                        }
                        None => panic!("Ran out of input"),
                    }
                }
            };

            res.push(token);
            input = rest;
        }

        res
    }
}

/// Transforms the tokens created by `tokenize` into RPN using the
/// [Shunting-yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm)
fn shunt(tokens: Vec<Token>) -> Vec<Token> {
    let mut queue = vec![];
    let mut stack: Vec<Token> = vec![];
    for token in tokens {
        match token {
            Token::Number(_) => queue.push(token),
            Token::Plus | Token::Sub | Token::Mul | Token::Div => {
                while let Some(o) = stack.pop() {
                    if token.precedence() <= o.precedence() {
                        queue.push(o);
                    } else {
                        stack.push(o);
                        break;
                    }
                }
                stack.push(token)
            },
            Token::LeftParen => stack.push(token),
            Token::RightParen => {
                let mut found_paren = false;
                while let Some(op) = stack.pop() {
                    match op {
                        Token::LeftParen => {
                            found_paren = true;
                            break;
                        },
                        _ => queue.push(op),
                    }
                }
                assert!(found_paren)
            },
        }
    }
    while let Some(op) = stack.pop() {
        queue.push(op);
    }
    queue
}

/// Takes a Vec of Tokens converted to RPN by `shunt` and calculates the result
fn calculate(tokens: Vec<Token>) -> i64 {
    let mut stack = vec![];
    for token in tokens {
        match token {
            Token::Number(n) => stack.push(n),
            Token::Plus => {
                let (b, a) = (stack.pop().unwrap(), stack.pop().unwrap());
                stack.push(a + b);
            },
            Token::Sub => {
                let (b, a) = (stack.pop().unwrap(), stack.pop().unwrap());
                stack.push(a - b);
            },
            Token::Mul => {
                let (b, a) = (stack.pop().unwrap(), stack.pop().unwrap());
                stack.push(a * b);
            },
            Token::Div => {
                let (b, a) = (stack.pop().unwrap(), stack.pop().unwrap());
                stack.push(a / b);
            },
            _ => {
                // By the time the token stream gets here, all the LeftParen
                // and RightParen tokens will have been removed by shunt()
                unreachable!();
            },
        }
    }
    stack[0]
}

---

I'm not really happy with the parsing aspect of the code, but I'm not seeing an obvious better thing at the moment.

---

As pointed out by Francis Gagné, you can call Chars::as_str to get the remainder of the string after pulling off the first character:

let mut chars = input.chars();
match chars.next() {
    Some(chr) => {
        (match chr {
            '+' => Token::Plus,
            '-' => Token::Sub,
            '*' => Token::Mul,
            '/' => Token::Div,
            '(' => Token::LeftParen,
            ')' => Token::RightParen,
            _ => panic!("Unknown character!"),
        }, chars.as_str())

I don't get the point of creating a whole new structure just for the tokenizer function when lazy_static! can do the same thing

Likewise, I don't get the point of using lazy_static! when normal language constructs can do the same thing ^_^.

lazy_static! currently requires heap allocation and that memory can never be reclaimed until the program exits.

Creating a value and using a reference to it is made completely safe by Rust's semantics and lifetimes, so I find myself using stack allocations far more frequently than I would with a language like C.

I generally dislike singletons of any kind, for the reasons espoused throughout the Internet. In this case, the singleton is created in the final binary, which ameliorates the problem somewhat.