Parsing/RPN calculator algorithm

I decided to try and complete the Parsing/RPN calculator algorithm from Rosetta Code in Rust. I'm still learning Rust and would appreciate feedback on my code.

use std::str::FromStr;

fn rpn(expression: &str) -> f64 {
    let mut stack: Vec = Vec::new();
    let tokens: Vec = expression.split_whitespace().collect();
    for token in tokens {
        match token {
            "+" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                stack.push(a + b);
            },
            "-" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                stack.push(a - b);
            },
            "*" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                stack.push(a * b);
            },
            "/" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                stack.push(a / b);
            },
            "^" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                stack.push(a.powf(b));
            },
            _ => {
                stack.push(f64::from_str(token).unwrap());
            }
        }
    }
    stack.pop().unwrap()
}

fn main() {
    let expression = "3 4 2 * 1 5 - 2 3 ^ ^ / +";
    println!("{}", rpn(expression));
}

I had attempted to write the commutative operations without assigning the operands to variables (i.e. a and b) like this:

stack.push(stack.pop().unwrap() + stack.pop().unwrap());

However, I received:

error: cannot borrow `stack` as mutable more than once at a time [E0499]

Another Approach

One approach I noticed some of the other languages' implementations using was to first check if a token is a number and push it onto the stack before checking for the operations. This allowed them to pop the two operands for the operations after they we

Overall, your code is pretty readable and understandable.

• There is an unneeded type on tokens; it can just be Vec.

• There's no need to collect to a vector at all! The current code takes an iterator, stores it in a vector, then converts it back into an iterator. Instead, just use the first iterator.

• It's unusual to use from_str directly. Usually, you call parse on the string.

That's the basic style stuff, looking up a level...

There's a lot of repeated code for the 5 binary operators. I'd suggest refactoring these out:

struct Stack(Vec);

impl Stack {
    fn new() -> Stack { Stack(Vec::new()) }

    fn pop(&mut self) -> Option {
        self.0.pop()
    }

    fn parse(&mut self, token: &str) {
        self.0.push(token.parse().unwrap());
    }

    fn binary(&mut self, f: F)
        where F: Fn(f64, f64) -> f64
    {
        let b = self.0.pop().unwrap();
        let a = self.0.pop().unwrap();
        self.0.push(f(a, b));
    }
}

fn rpn(expression: &str) -> f64 {
    let mut stack = Stack::new();

    for token in expression.split_whitespace() {
        match token {
            "+" => stack.binary(|a, b| a + b),
            "-" => stack.binary(|a, b| a - b),
            "*" => stack.binary(|a, b| a * b),
            "/" => stack.binary(|a, b| a / b),
            "^" => stack.binary(|a, b| a.powf(b)),
            _ => stack.parse(token),
        }
    }

    stack.pop().unwrap()
}

fn main() {
    let expression = "3 4 2 * 1 5 - 2 3 ^ ^ / +";
    println!("{}", rpn(expression));
}

There's also a lot of unwrap calls. This is fine for quick code that you don't expect to have non-programmers using, but often it's a good idea to try and see how error reporting can work:

use std::{error, fmt, num};

#[derive(Debug)]
enum Error {
    InvalidNumber(num::ParseFloatError),
    EmptyStack,
}

impl error::Error for Error {
    fn description(&self) -> &str {
        match *self {
            Error::InvalidNumber(..) => "Not a valid number",
            Error::EmptyStack => "No numbers on the stack",
        }
    }

    fn cause(&self) -> Option { 
        match *self {
            Error::InvalidNumber(ref e) => Some(e),
            Error::EmptyStack => None,
        }
    }
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", error::Error::description(self))
    }
}

impl From for Error {
    fn from(e: num::ParseFloatError) -> Error { Error::InvalidNumber(e) }
}

struct Stack(Vec);

impl Stack {
    fn new() -> Stack { Stack(Vec::new()) }

    fn pop(&mut self) -> Option {
        self.0.pop()
    }

    fn parse(&mut self, token: &str) -> Result {
        self.0.push(try!(token.parse()));
        Ok(())
    }

    fn binary(&mut self, f: F) -> Result
        where F: Fn(f64, f64) -> f64
    {
        let b = try!(self.0.pop().ok_or(Error::EmptyStack));
        let a = try!(self.0.pop().ok_or(Error::EmptyStack));
        self.0.push(f(a, b));
        Ok(())
    }
}

fn rpn(expression: &str) -> Result {
    let mut stack = Stack::new();

    for token in expression.split_whitespace() {
        let r = match token {
            "+" => stack.binary(|a, b| a + b),
            "-" => stack.binary(|a, b| a - b),
            "*" => stack.binary(|a, b| a * b),
            "/" => stack.binary(|a, b| a / b),
            "^" => stack.binary(|a, b| a.powf(b)),
            _ => stack.parse(token),
        };
        try!(r);
    }

    stack.pop().ok_or(Error::EmptyStack)
}

fn main() {
    let expression = "3 4 2 * 1 5 - 2 3 ^ ^ / +";
    println!("{:?}", rpn(expression));
}

Rust has a built-in testing framework, so I'd encourage you to use it. It's easy enough to throw in some tests instead of visually comparing the output of main. I've wrapped the tests in a bit of ceremony here to ensure they aren't compiled during a production build:

// Add `PartialEq` to the `derive` on `Error` to allow comparison

#[cfg(test)]
mod test {
    use super::rpn;

    #[test]
    fn golden_master() {
        assert_eq!(Ok(3.0001220703125), rpn("3 4 2 * 1 5 - 2 3 ^ ^ / +"));
    }
}

I had attempted to write the commutative operations without assigning the operands to variables

Yes, this is a current limitation of the borrow checker. The entire expression is borrow checked at once, and it sees that stack.push requires a mutable borrow and stack.pop requires an immutable borrow. Since you can't have any other borrows during a mutable borrow, you get the error. It isn't currently smart enough to understand that the immutable borrow ends before the mutable borrow begins.

There is work in progress to loosen up these checks, but separate variables is the current solution.

For the alternate code:

• There's no need for an explicit type on parse. The fact that it needs to be a f64 can be inferred.

• Use an if let expression instead of if_ok. This avoids the need to unwrap and better communicates intent.

• Having a

StackExchange Code Review Q#122566, answer score: 5