Skip to content

Mitaka Club

四則演算を逆ポーランド記法で解く(Rust)

中置記法で書かれた四則演算を操車場アルゴリズムで逆ポーランド記法にしてから計算する。

Russ Cox の Regular Expression Matching Can Be Simple And Fast を読んでいて正規表現を postfix notation で書き換えるというところがあったがよくわかってなかったので、練習のため四則演算で試しに書いてみた。次の演算子とスタックのトップの演算子を比較して、優先順位が同じかスタックの方が高かったらスタックをポップしてキューに突っ込むところがなるほどとなった。

fn main() {
    println!("Hello, world!");
}

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
}

fn to_postfix(tokens: Vec<String>) -> Vec<String> {
    fn order(s: &str) -> usize {
        match s {
            "*" | "/" => 3,
            "+" | "-" => 2,
            "(" | ")" => 1,
            _ => panic!(),
        }
    }

    let mut out: Vec<String> = vec![];
    let mut stack: Vec<String> = vec![];

    for s in tokens.into_iter() {
        match s.as_str() {
            "+" | "-" | "*" | "/" => {
                while let Some(last) = stack.last() {
                    if order(last) >= order(&s) {
                        let op = stack.pop().unwrap();
                        out.push(op);
                    } else {
                        break;
                    }
                }

                stack.push(s);
            }
            "(" => {
                stack.push(s);
            }
            ")" => loop {
                if !stack.is_empty() {
                    let op = stack.pop().unwrap();
                    if op == "(" {
                        break;
                    } else {
                        out.push(op);
                    }
                } else {
                    break;
                }
            },
            _ => out.push(s),
        }
    }

    while !stack.is_empty() {
        let op = stack.pop().unwrap();
        out.push(op);
    }

    out
}

fn eval(postfix: Vec<String>) -> i32 {
    let mut stack: Vec<i32> = vec![];

    for s in postfix.into_iter() {
        match s.as_str() {
            "+" | "-" | "*" | "/" => {
                let right = stack.pop().unwrap();
                let left = stack.pop().unwrap();
                match s.as_str() {
                    "+" => stack.push(left + right),
                    "-" => stack.push(left - right),
                    "*" => stack.push(left * right),
                    "/" => stack.push(left / right),
                    _ => panic!(),
                }
            }
            _ => {
                stack.push(s.parse::<i32>().unwrap());
            }
        }
    }

    stack.pop().unwrap()
}

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 to_postfix_test() {
        assert_eq!(
            to_postfix(lexer("12 + 4".to_string())),
            vec!["12", "4", "+"]
        );
        assert_eq!(
            to_postfix(lexer("12 - 4".to_string())),
            vec!["12", "4", "-"]
        );
        assert_eq!(
            to_postfix(lexer("(11 + 1) * 2".to_string())),
            vec!["11", "1", "+", "2", "*"]
        );
        assert_eq!(
            to_postfix(lexer("3 + 4 * 2 / (1 - 5)".to_string())),
            vec!["3", "4", "2", "*", "1", "5", "-", "/", "+"]
        );
    }

    #[test]
    fn eval_test() {
        assert_eq!(eval(to_postfix(lexer("12 + 4".to_string()))), 16);
        assert_eq!(eval(to_postfix(lexer("12 - 4".to_string()))), 8);
        assert_eq!(eval(to_postfix(lexer("12 * 4".to_string()))), 48);
        assert_eq!(eval(to_postfix(lexer("12 / 4".to_string()))), 3);
        assert_eq!(eval(to_postfix(lexer("(11 + 1) * 2".to_string()))), 24);
        assert_eq!(
            eval(to_postfix(lexer("3 + 4 * 2 / (1 - 5)".to_string()))),
            1
        );
    }
}

参考