锈蚀控制台RPN计算器

Question

我一直在努力教自己，锈斯特，我决定，一个简单的控制台计算器将是一个很好的项目学习。

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,
    }
}

还有什么可以改进的吗？特别是

1. 在字符串的第一个字符上是否有更好的模式匹配方法，然后删除它？代码的那一部分感觉很笨重。
2. 是否有更好的方法将运算符的优先级与其定义联系起来？为了获得操作符的优先级，我不得不编写一个优先级函数，这让我很苦恼。

Answer 1

1. 在枚举变体的括号前没有空格
2. derives被合并成一行。
3. 使precedence成为Token上的一种固有方法。
4. 在precedence内部，匹配该值的取消引用。这避免了&的传播。
5. 不需要lazy_static；只需创建一个结构并将正则表达式放入其中，将其重用到循环中即可。
6. 不需要大量的字符串分配。接受一个&str而不是一个String，然后简单地分割它。
7. 与其按运算符字符修剪输入，不如跳过第一个字符的字节数。
8. 不需要指定parse的类型。
9. 代码多次对左代码进行修剪；只需执行一次。
10. 不需要指定queue的类型，因为它是不可推断的。
11. 没有必要使用@模式绑定；可以只使用token。

更大的想法：

1. 在Vec<Token>周围创建一个新类型，以指示数据是按RPN顺序排列的。类型避免了文档的需要。
2. 创建多种类型的枚举；一个有父母，另一个没有。那么就少了一个地方可以拥有unreachable了。如果有子集，可以将子集嵌入到超集中。
3. 对于最终用户来说，错误处理非常粗糙。不匹配的括号杀死程序，而不是解释错误和让用户继续。除了杀死程序或关闭stdin (这会产生另一条错误消息)之外，没有(显而易见的)退出程序的方法。

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]
}

我对代码的解析方面并不满意，但我目前没有看到明显的更好的东西。

作为弗朗西斯·加格内指出的，您可以在取出第一个字符后调用Chars::as_str来获取字符串的其余部分：

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())

当lazy_static!可以做同样的事情时，我不明白只为令牌程序函数创建一个全新的结构的意义

同样，当普通的语言结构可以做同样的事情( lazy_static! )时，我不明白使用^_^的意义。

lazy_static! 当前需要堆分配。和那个内存在程序退出之前是无法回收的。

根据Rust的语义和生命周期，创建一个值并使用它的引用是完全安全的，所以我发现自己使用堆栈分配的频率比使用C这样的语言要高得多。

我一般不喜欢任何类型的单身人士，因为互联网上所支持的理由。在这种情况下，单例是在最后的二进制文件中创建的，这在一定程度上改善了问题。