Skip to content

Mitaka Club

四則演算を再帰下降で書く(Rust)

覚えてるかなと思ってサッと書いてみた。テスト通ってるし多分動くと思う。テスト含めて200行くらいなので勉強したい言語で書いてみるのもいいかもしれない、TypeScriptとか。

fn main() {
    let s = "1 + 1".to_string();
    let tokens = lexer(s);
    let mut parser = Parser { tokens, idx: 0 };
    let ret = parser.expr();
    println!("{}", ret);
}

fn lexer(s: String) -> Vec<String> {
    let mut ret = Vec::new();
    let mut num = Vec::new();

    let chars: Vec<char> = s.chars().collect();
    for i in 0..chars.len() {
        match chars[i] {
            '(' | ')' | '+' | '-' | '*' | '/' => ret.push(String::from(chars[i])),
            n if n.is_numeric() => {
                num.push(n);
            }
            ' ' => {}
            _ => panic!(),
        }

        if !num.is_empty() && i < chars.len() - 1 && !chars[i + 1].is_numeric() {
            let n: String = num.iter().collect();
            ret.push(n);
            num = Vec::new();
        }
    }

    if !num.is_empty() {
        let n: String = num.iter().collect();
        ret.push(n);
    }

    ret
}

struct Parser {
    tokens: Vec<String>,
    idx: usize,
}

impl Parser {
    pub fn expr(&mut self) -> i32 {
        let mut left = self.term();

        loop {
            if self.idx >= self.tokens.len() {
                break;
            }

            let op = match self.tokens[self.idx].as_str() {
                "+" => "+",
                "-" => "-",
                _ => break,
            };
            self.consume();

            let right = self.term();
            left = match op {
                "+" => left + right,
                "-" => left - right,
                _ => unreachable!(),
            }
        }

        left
    }

    fn term(&mut self) -> i32 {
        let mut left = self.factor();

        loop {
            if self.idx >= self.tokens.len() {
                break;
            }

            let op = match self.tokens[self.idx].as_str() {
                "*" => "*",
                "/" => "/",
                _ => break,
            };
            self.consume();

            let right = self.factor();
            left = match op {
                "*" => left * right,
                "/" => left / right,
                _ => unreachable!(),
            }
        }

        left
    }

    fn factor(&mut self) -> i32 {
        match self.tokens[self.idx].as_str() {
            "(" => {
                self.consume();
                let ret = self.expr();

                match self.tokens[self.idx].as_str() {
                    ")" => {
                        self.consume();
                        return ret;
                    }
                    _ => panic!(),
                }
            }
            _ => return self.number(),
        }
    }

    fn number(&mut self) -> i32 {
        let ret = self.tokens[self.idx].parse::<i32>().unwrap();
        self.consume();
        ret
    }

    fn consume(&mut self) {
        self.idx += 1;
    }
}

mod test {
    use super::*;

    #[test]
    fn lexer_test() {
        assert_eq!(lexer("12 + 4".to_string()), vec!["12", "+", "4"]);
        assert_eq!(lexer("12 - 4".to_string()), vec!["12", "-", "4"]);
        assert_eq!(lexer("12 * 4".to_string()), vec!["12", "*", "4"]);
        assert_eq!(lexer("12 / 4".to_string()), vec!["12", "/", "4"]);

        assert_eq!(
            lexer("(11 + 1) * 2".to_string()),
            vec!["(", "11", "+", "1", ")", "*", "2"]
        );
    }

    #[test]
    fn parser_test() {
        let mut parser = Parser {
            tokens: vec!["12".to_string(), "+".to_string(), "4".to_string()],
            idx: 0,
        };
        assert_eq!(parser.expr(), 16);

        let mut parser = Parser {
            tokens: vec!["12".to_string(), "-".to_string(), "4".to_string()],
            idx: 0,
        };
        assert_eq!(parser.expr(), 8);

        let mut parser = Parser {
            tokens: vec!["12".to_string(), "*".to_string(), "4".to_string()],
            idx: 0,
        };
        assert_eq!(parser.expr(), 48);

        let mut parser = Parser {
            tokens: vec!["12".to_string(), "/".to_string(), "4".to_string()],
            idx: 0,
        };
        assert_eq!(parser.expr(), 3);

        let mut parser = Parser {
            tokens: vec!["12".to_string(), "/".to_string(), "4".to_string()],
            idx: 0,
        };
        assert_eq!(parser.expr(), 3);

        let mut parser = Parser {
            tokens: vec![
                "12".to_string(),
                "+".to_string(),
                "4".to_string(),
                "*".to_string(),
                "3".to_string(),
            ],
            idx: 0,
        };
        assert_eq!(parser.expr(), 24);

        let mut parser = Parser {
            tokens: vec![
                "12".to_string(),
                "-".to_string(),
                "4".to_string(),
                "-".to_string(),
                "3".to_string(),
            ],
            idx: 0,
        };
        assert_eq!(parser.expr(), 5);

        let mut parser = Parser {
            tokens: vec![
                "(".to_string(),
                "12".to_string(),
                "+".to_string(),
                "4".to_string(),
                ")".to_string(),
                "*".to_string(),
                "3".to_string(),
            ],
            idx: 0,
        };
        assert_eq!(parser.expr(), 48);
    }
}