AOJ 0109: Smart Calculator

問題文

ちまちま読んでいたThe Rust Programming Languageをようやく読み終わった。 Rustで再帰下降構文解析を書きたかったので構文解析のオーソドックスな問題を解くことにした。

いきなりRustで書くのは厳しいためまずはC++で解いた。 構文解析 Howto · GitHubを参考にした。

解析すべき構文は基本的に

<四則演算の式> ::= <乗算除算の式> (+ or -) <乗算除算の式> (+ or -) ...
<乗算除算の式> ::= <括弧か数> (* or /) <括弧か数> (* or /) ...
<括弧か数>     ::= '(' <四則演算の式> ')' or <数>
<数>           ::= ...

である（この問題では式の終わりに=が来ることが指定されているが、数字でも演算子でもカッコでもない文字が来たら終了するコードになっているのであまり考えていない）

これを解くプログラムは以下のようになる。

#include <bits/stdc++.h>

using namespace std;

typedef string::const_iterator State;

int number(State &begin);
int factor(State &begin);
int term(State &begin);
int expression(State &begin);

int expression(State &begin) {
  int ret = term(begin);
  for (;;) {
    if (*begin == '+') {
      begin++;
      ret += term(begin);
    } else if (*begin == '-') {
      begin++;
      ret -= term(begin);
    } else {
      break;
    }
  }
  return ret;
}

int term(State &begin) {
  int ret = factor(begin);
  for (;;) {
    if (*begin == '*') {
      begin++;
      ret *= factor(begin);
    } else if (*begin == '/') {
      begin++;
      ret /= factor(begin);
    } else {
      break;
    }
  }
  return ret;
}

int factor(State &begin) {
  int ret = 0;
  if (*begin == '(') {
    begin++;
    ret = expression(begin);
    begin++;
    return ret;
  } else {
    ret = number(begin);
  }
  return ret;
}

int number(State &begin) {
  int ret = 0;
  while (isdigit(*begin)) {
    ret *= 10;
    ret += *begin - '0';
    begin++;
  }
  return ret;
}

int main() {
  int N;
  cin >> N;
  cin.ignore();
  for (int i = 0; i < N; i++) {
    string s;
    getline(cin, s);
    State begin = s.begin();
    int ans = expression(begin);
    cout << ans << endl;
  }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4049138

このコードを素直にRustにしたらこうなった。 C++のstring::const_iteratorの代わりにstd::iter::Peekable<std::str::Chars>を使っている。

use std::io;

fn parse(input: &String) -> i32 {
    let mut it = input.chars().peekable();
    expression(&mut it)
}

fn expression(it: &mut std::iter::Peekable<std::str::Chars>) -> i32 {
    let mut ret = term(&mut *it);
    loop {
        let c = it.peek().unwrap();
        match c {
            '+' => {
                it.next();
                ret += term(&mut *it);
            }
            '-' => {
                it.next();
                ret -= term(&mut *it);
            }
            ')' | '=' => {
                break;
            }
            _ => {
                panic!("Invalid character: {}", c);
            }
        }
    }
    ret
}

fn term(it: &mut std::iter::Peekable<std::str::Chars>) -> i32 {
    let mut ret = factor(&mut *it);
    loop {
        let c = it.peek().unwrap();
        match c {
            '*' => {
                it.next();
                ret *= factor(&mut *it);
            }
            '/' => {
                it.next();
                ret /= factor(&mut *it);
            }
            _ => {
                break;
            }
        }
    }
    ret
}

fn factor(it: &mut std::iter::Peekable<std::str::Chars>) -> i32 {
    let c = it.peek().unwrap();
    match c {
        '(' => {
            it.next();
            let ret = expression(&mut *it);
            it.next();
            return ret;
        }
        '0'..='9' => {
            return number(&mut *it);
        }
        _ => {
            panic!("Invalid character: {}", c);
        }
    }
}

fn number(it: &mut std::iter::Peekable<std::str::Chars>) -> i32 {
    let mut ret = 0;
    while it.peek().unwrap().is_numeric() {
        ret *= 10;
        ret += it.peek().unwrap().to_digit(10).unwrap() as i32;
        it.next();
    }
    ret
}

fn main() {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    let n: i32 = buf.trim().parse().unwrap();

    for _ in 0..n {
        let mut line = String::new();
        io::stdin().read_line(&mut line).unwrap();
        println!("{}", parse(&line));
    }
}

AOJのRustコンパイラが古いため、このコードはコンパイルが通らなかった。 古いRustの書き方を学ぶことが目的ではないのでテストケースを落としてきて、出力が一致することを確認したのでこれでよしとする。