Parsing/RPN calculator algorithm

Question

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<f64> = Vec::new();
    let tokens: Vec<&str> = 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 were sure it wasn't a number.

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

Answer 1

Overall, your code is pretty readable and understandable.

1. There is an unneeded type on tokens; it can just be Vec<_>.
2. 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.
3. 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<f64>);

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

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

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

    fn binary<F>(&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<&error::Error> { 
        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<num::ParseFloatError> for Error {
    fn from(e: num::ParseFloatError) -> Error { Error::InvalidNumber(e) }
}

struct Stack(Vec<f64>);

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

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

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

    fn binary<F>(&mut self, f: F) -> Result<(), Error>
        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<f64, Error> {
    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:

1. There's no need for an explicit type on parse. The fact that it needs to be a f64 can be inferred.
2. Use an if let expression instead of if_ok. This avoids the need to unwrap and better communicates intent.
3. Having a no-op fallthrough case in the match is too loose for my tastes. I'd panic there to indicate that something unexpected happened. That way if I tried to use something like ** for exponentiation it isn't silently ignored.

fn rpn(expression: &str) -> f64 {
    let mut stack: Vec<f64> = Vec::new();
    for token in expression.split_whitespace() {
        if let Ok(value) = token.parse() {
            stack.push(value);
            continue;
        }

        let b = stack.pop().unwrap();
        let a = stack.pop().unwrap();
        match token {
            "+" => stack.push(a + b),
            "-" => stack.push(a - b),
            "*" => stack.push(a * b),
            "/" => stack.push(a / b),
            "^" => stack.push(a.powf(b)),
            other => panic!("Unknown symbol `{}`", other),
        }
    }
    stack.pop().unwrap()
}