RPN電卓を実装しよう

Rustは実行効率や安全性を重視した人気のプログラミング言語ですが、難しいと言われることもあります。本連載ではいろいろな有名アルゴリズムを解くことでRustに慣れていきます。今回は、RPN電卓を実装してみましょう。またエラー処理についても紹介します。

• 逆ポーランド記法を計算するRPN電卓を実行したところ

RPN電卓とは

RPN電卓とは、逆ポーランド記法を利用して記述した計算式を計算する電卓のことです。逆ポーランド記法(あるいは、後置記法)とは、数字など被演算子の後で演算子を記述する記述方法です。

例えば、「8 + 9」という計算式を逆ポーランド記法で記述すると「8 9 +」となります。このような書き方は、読みづらく感じるかもしれませんが、日本語で計算を言い表すとき、無意識にこの記法を使っています。数字の後に助詞を足して見ると、「8に9を+(足す)」となります。

逆ポーランド記法と日本語の相性の良さは抜群で、「(2 × 3 + 4)÷2」のような長い計算式を表現する場合も、「2に3を×(掛けて)4を+(足して)2で÷(割る)」のように、自然な日本語で表現できます。

逆ポーランド記法はスタックを使うと簡単に計算できる

逆ポーランド記法はコンピューターと相性が良く、スタック構造を使うことで簡単に計算できます。次のような手順で計算できます。

 (1) 文字列を空白でトークンに区切る
 (2) トークンを1つ読む
 (3) 数値なら、スタックに積む
 (4) 演算子なら、スタックから2つ値を取り出して計算してスタックに積む
 (5) トークンが空でなければ(2)に戻る
 (6) スタックに残っている値が答えとなる

例えば、逆ポーランド記法「2 3 * 4 + 2 /」の計算の様子を図で確認してみましょう。特にスタックの様子に注目してみてください。次のようになります。

• 逆ポーランド記法の計算方法

数値ならばそのままスタックへ入れて、演算子ならスタックから取り出して計算して結果をスタックに入れるという単純な仕組みであることが分かるでしょう。

RPN電卓のプログラム

それでは、上記の手順を元にしてプログラムを作成してみましょう。以下のプログラムを「rpn.rs」というファイル名で保存します。

// 逆ポーランド記法を計算する関数 --- (*1)
fn calc_rpn(text: &str) -> f64 {
    // 計算用のスタックを初期化 --- (*2)
    let mut stack: Vec<f64> = vec![];
    // 逆ポーランド記法の式をスペースで区切る --- (*3)
    let tokens = text.split(' ');
    // スペースで区切られたトークンを一つずつ処理 --- (*4)
    for tok in tokens {
        // 空ならば無視する
        let tok = tok.trim();
        if tok.len() == 0 { continue; }
        // 数値変換を試みる --- (*5)
        match tok.parse::<f64>() {
            // 変換成功ならスタックに追加 --- (*6)
            Ok(num) => {
                stack.push(num);
                continue;
            },
            // 失敗なら演算子
            Err(_) => {}
        };
        // 演算子ならスタックから2つ値を得る --- (*7)
        let b = stack.pop().unwrap_or(0.0);
        let a = stack.pop().unwrap_or(0.0);
        // 計算結果をスタックに追加 --- (*8)
        match tok {
            "+" => stack.push(a + b),
            "-" => stack.push(a - b),
            "*" => stack.push(a * b),
            "/" => stack.push(a / b),
            "%" => stack.push(a % b),
            _ => { println!("[ERROR] {}", tok); }
        }
    }
    // 最後にスタックに残っている値が計算結果 --- (*9)
    return stack.pop().unwrap_or(0.0);
}

fn main() {
    // 簡単な問題を解く --- (*10)
    let expr = "8 9 +";
    println!("{} = {}", expr, calc_rpn(expr));
    // 複雑な問題を解く1
    let expr = "2 3 * 4 + 2 /";
    println!("{} = {}", expr, calc_rpn(expr));
    // 複雑な問題を解く2
    let expr = "6 4 + 2 / 3 +";
    println!("{} = {}", expr, calc_rpn(expr));
}

プログラムを実行してみましょう。WindowsならPowerShell、macOSならターミナル.appを起動してコマンドを実行します。(Windowsの場合「/」を「￥」に読み替えてください。)

# コンパイル
$ rustc ./rpn.rs
# 実行
$ ./rpn

すると次のように実行結果が表示されます。「8 9 +」と「2 3 * 4 + 2 /」と「6 4 + 2 / 3 +」の実行結果が正確に表示されました。

• RPN電卓のプログラムを実行したところ

プログラムを確認してみましょう。

(＊1)では逆ポーランド記法を計算する関数calc_rpnを定義します。文字列参照(&str)を受け取り、64ビット浮動小数点(f64)型の値を返す関数です。

(＊2)では計算に使うスタックを初期化します。スタックは計算しやすいよう64ビット浮動小数点のベクタ型とします。ベクタとは動的に複数の値を追加・削除できるデータ型です。

(＊3)では引数として与えられた逆ポーランド記法のテキストをスペースで区切ります。そして、(＊4)以降では区切った1つずつの値(トークンと呼びます)をfor文で1つずつ処理します。

(＊5)では全てのトークンを数値に変換しようと試みます。matchを使うと、parseメソッドが成功した時(Ok)と失敗した時(Err)を分岐させることができます。成功した時には、(＊6)でスタックに数値を追加します。

(＊7)以降は数値以外の時の処理を記述します。ここでは数値以外では演算子しかないので、演算子の時は、スタックから2つ値を取得します。

(＊8)ではmatchを利用して演算子の種類に合わせて計算を行います。そして、結果をスタックに追加します。このように、matchは幅広いパターンマッチングに対応します。

トークンを全て読み終わった後、(＊9)ではスタックから1つ値を取り出して、それを関数の戻り値とします。

最後の(＊10)では、main関数の中で、3回、関数calc_rpnを呼び出して結果を表示します。

Rustのエラー処理について