2
\$\begingroup\$

To learn some rust I decided to write a simple calculator. This calculator can take a string in the form of 1+2*3/4-5, and calculate the result. It does so while keeping the order of operations in mind (*/ before +-).

I came up with the following:

/// Token containing either a number or an operation. Never both.
#[derive(Debug, PartialEq)]
enum Token {
    NUMBER(i64),
    /// Operation being one of +/*-
    OPERATION(char),
}

impl Token {
    pub fn from_string(string: &str) -> Result<Self, &str> {
        let number = string.parse::<i64>().ok();
        if number.is_some() {
            Ok(Token::NUMBER(number.unwrap()))
        } else {
            match string.chars().nth(0) {
                Some(c) => Ok(Token::OPERATION(c)),
                None => Err("Can't parse token from empty string."),
            }
        }
    }
}

/// Tokenizes the given string. Splits numbers from non-numbers. Returns a vector of tokens.
fn tokenize(sum: &str) -> Vec<Token> {
    let mut parts: Vec<String> = Vec::new();
    let mut prev_is_number = false;
    for c in sum.chars() {
        if c.is_numeric() != prev_is_number {
            prev_is_number = c.is_numeric();
            parts.push(String::new());
        }
        parts.last_mut().unwrap().push(c);
    }
    let mut tokens: Vec<Token> = Vec::new();
    for token in parts {
        tokens.push(Token::from_string(&token).expect(&format!("Failed to parse {}", token)));
    }
    prev_is_number = false;
    for token in &tokens {
        let is_number = match token {
            Token::NUMBER(..) => true,
            _ => false
        };
        assert_ne!(prev_is_number,
                is_number
        ); // Assert numbers always followed by tokens and otherwise.
        prev_is_number = is_number;
    }

    return tokens;
}

/// Solves the multiplications and divisions in the given token vector. Returns a vector of tokens that were not solved, with the solved parts in-place.
/// e.g. 1+2*3 returns 1+6.
fn solve_multiply_divide(tokens: &Vec<Token>) -> Vec<Token> {
    let mut prev_number: Option<i64> = None;
    let mut prev_operation: Option<char> = None;

    let mut result: Vec<Token> = Vec::new();

    for token in tokens {
        match token {
            Token::NUMBER(number) => {
                match prev_number {
                    None => {
                        prev_number = Some(*number);
                    },
                    Some(unwrapped_prev_number) => {
                        match prev_operation {
                            Some('*') => {
                                prev_number = Some(unwrapped_prev_number * number);
                            },
                            Some('/') => {
                                prev_number = Some(unwrapped_prev_number / number);
                            },
                            _ => {panic!("Found two numbers after each other without operator in between. Incorrect token sequence supplied.")}
                        }
                        prev_operation = None;
                    }
                }
            }
            Token::OPERATION(operation) => {
                if *operation == '*' || *operation == '/' {
                    prev_operation = Some(*operation);
                } else {
                    if prev_number.is_some() {
                        result.push(Token::NUMBER(prev_number.unwrap()));
                    }
                    result.push(Token::OPERATION(*operation));
                    prev_number = None;
                    prev_operation = None;
                }

            }
        }
    }

    if prev_number.is_some() {
        result.push(Token::NUMBER(prev_number.unwrap()));
    }

    return result;
}

/// Solves the plus and minus in the given token vector. Returns a vector of tokens that were not solved, with the solved parts in-place.
/// e.g. 1+2*3 returns 3*3
fn solve_plus_minus(tokens: &Vec<Token>) -> Vec<Token> {
    let mut prev_number: Option<i64> = None;
    let mut prev_operation: Option<char> = None;

    let mut result: Vec<Token> = Vec::new();

    for token in tokens {
        match token {
            Token::NUMBER(number) => {
                match prev_number {
                    None => {
                        prev_number = Some(*number);
                    },
                    Some(unwrapped_prev_number) => {
                        match prev_operation {
                            Some('+') => {
                                prev_number = Some(unwrapped_prev_number + number);
                            },
                            Some('-') => {
                                prev_number = Some(unwrapped_prev_number - number);
                            },
                            _ => {panic!("Found two numbers after each other without operator in between. Incorrect token sequence supplied.")}
                        }
                        prev_operation = None;
                    }
                }
            }
            Token::OPERATION(operation) => {
                if *operation == '+' || *operation == '-' {
                    prev_operation = Some(*operation);
                } else {
                    if prev_number.is_some() {
                        result.push(Token::NUMBER(prev_number.unwrap()));
                    }
                    result.push(Token::OPERATION(*operation));
                    prev_number = None;
                    prev_operation = None;
                }

            }
        }
    }

    if prev_number.is_some() {
        result.push(Token::NUMBER(prev_number.unwrap()));
    }

    return result;
}

/// Solves a given equation.
pub fn solve(sum: &str) -> Result<i64, &str> {
    let tokens = tokenize(sum);
    let tokens_multiplied_divided = solve_multiply_divide(&tokens);
    let tokens_plus_minus = solve_plus_minus(&tokens_multiplied_divided);
    assert_eq!(tokens_plus_minus.len(), 1);
    match tokens_plus_minus.first().unwrap() {
        Token::NUMBER(result) => Ok(*result),
        _ => Err("Could not solve. Invalid equation?")
    }
}

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

    /// Returns the vector of tokens for 1+2*3/4-5
    fn get_test_tokens() -> Vec<Token> {
        return vec![
            Token::NUMBER(1),
            Token::OPERATION('+'),
            Token::NUMBER(2),
            Token::OPERATION('*'),
            Token::NUMBER(3),
            Token::OPERATION('/'),
            Token::NUMBER(4),
            Token::OPERATION('-'),
            Token::NUMBER(5),
        ];
    }
    #[test]
    fn test_tokenize() {
        assert_eq!(tokenize("1+2*3/4-5"), get_test_tokens());
    }
    #[test]
    fn test_multiply_divide() {
        assert_eq!(
            solve_multiply_divide(&get_test_tokens()),
            [
                Token::NUMBER(1),
                Token::OPERATION('+'),
                Token::NUMBER(2 * 3 / 4),
                Token::OPERATION('-'),
                Token::NUMBER(5),
            ]
        )
    }

    #[test]
    fn test_solve() {
        match solve("1+2*3/4-5") {
            Ok(-3) => assert!(true),
            Ok(number) => assert!(false, "wrong answer: {}", number),
            Err(error) => assert!(false, "got an error: {}", error)
        }
    }
}

One problem that I do have with this code is the overlap between solve_multiply_divide and solve_plus_minus, I feel like these could be merged somehow but I haven't figured out how yet.

I'm coming from a C++ background, which could shine through in this code. How could I improve my code and make it adhere more to a rust way of thinking, instead of c++?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The classic way to parse a string of binary operations with precedence is the Shunting-Yard algorithm. This would allow nesting. \$\endgroup\$
    – Davislor
    Jan 5 at 17:05

1 Answer 1

2
\$\begingroup\$

One problem that I do have with this code is the overlap between solve_multiply_divide and solve_plus_minus, I feel like these could be merged somehow but I haven't figured out how yet.

This can be done by introducing a more general function solve_bin_ops. You will then run into some limitations of match which you can solve by using if instead. Like this:

/// Solves the multiplications and divisions in the given token vector. Returns a vector of tokens that were not solved, with the solved parts in-place.
/// e.g. 1+2*3 returns 1+6.
fn solve_multiply_divide(tokens: &Vec<Token>) -> Vec<Token> {
    solve_bin_ops(tokens, ('*', i64::wrapping_mul), ('/', i64::wrapping_div))
}

/// Solves the plus and minus in the given token vector. Returns a vector of tokens that were not solved, with the solved parts in-place.
/// e.g. 1+2*3 returns 3*3
fn solve_plus_minus(tokens: &Vec<Token>) -> Vec<Token> {
    solve_bin_ops(tokens, ('+', i64::wrapping_add), ('-', i64::wrapping_sub))
}

fn solve_bin_ops(
    tokens: &Vec<Token>,
    op1: (char, fn(i64, i64) -> i64),
    op2: (char, fn(i64, i64) -> i64),
) -> Vec<Token> {
    let mut prev_number: Option<i64> = None;
    let mut prev_operation: Option<char> = None;

    let mut result: Vec<Token> = Vec::new();

    for token in tokens {
        match token {
            Token::NUMBER(number) => match prev_number {
                None => {
                    prev_number = Some(*number);
                }
                Some(unwrapped_prev_number) => {
                    if prev_operation == Some(op1.0) {
                        prev_number = Some(op1.1(unwrapped_prev_number, *number));
                    } else if prev_operation == Some(op2.0) {
                        prev_number = Some(op2.1(unwrapped_prev_number, *number));
                    } else {
                        panic!("Found two numbers after each other without operator in between. Incorrect token sequence supplied.")
                    }
                    prev_operation = None;
                }
            },
            Token::OPERATION(operation) => {
                if *operation == op1.0 || *operation == op2.0 {
                    prev_operation = Some(*operation);
                } else {
                    if prev_number.is_some() {
                        result.push(Token::NUMBER(prev_number.unwrap()));
                    }
                    result.push(Token::OPERATION(*operation));
                    prev_number = None;
                    prev_operation = None;
                }
            }
        }
    }

    if prev_number.is_some() {
        result.push(Token::NUMBER(prev_number.unwrap()));
    }

    result
}

I've slightly changed the binary operators here, by specifying what should happen in the case of overflow. To recover the behavior of your original code, which will panic on overflow in debug mode (since you haven't specified what you want to happen in that case), but wrap in release mode, do this:

/// Solves the multiplications and divisions in the given token vector. Returns a vector of tokens that were not solved, with the solved parts in-place.
/// e.g. 1+2*3 returns 1+6.
fn solve_multiply_divide(tokens: &Vec<Token>) -> Vec<Token> {
    solve_bin_ops(tokens, ('*', <i64 as std::ops::Mul>::mul), ('/', <i64 as std::ops::Div>::div))
}

/// Solves the plus and minus in the given token vector. Returns a vector of tokens that were not solved, with the solved parts in-place.
/// e.g. 1+2*3 returns 3*3
fn solve_plus_minus(tokens: &Vec<Token>) -> Vec<Token> {
    solve_bin_ops(tokens, ('+', <i64 as std::ops::Add>::add), ('-', <i64 as std::ops::Sub>::sub))
}

Introducing explicit grouping (using parentheses is customary) into the language you accept (for example (3+4)*2) will probably change your design quite a bit...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.