プログラマのみなさんなら、きっと算数が苦手でしょう。というのも電卓という便利な道具があるのですから計算は全部そいつに任せてしまうため、どんどん算数ができなくなっていくに違いないからです。

それに専用の電卓がなくとも、たとえばWindowsならば、「電卓」というアプリケーションがあります。

Windowsの電卓はごく普通の電卓なのですが、電卓というのは、「＋」や「÷」というボタンを押すと即座に計算してしまうため、たとえば次のような数式は

１ ＋ ２ × ３ ＝ ９

となります。でも小学校の算数で習ったとおり、積や商は、和や差より先に計算しなければいけません。なので本当は

１ ＋ ２ × ３ ＝ ７

となるはずです。実はWindowsの電卓には関数電卓モードというのがあり、このモードでは演算子の優先順位の処理はもちろん、カッコによる順序の変更も可能になっています。

というわけで苦手な算数については、このような電卓アプリを使えばいいのですが、プログラマとしてはこれを作ってみたくなるワケです。

逆ポーランド記法とは

数式を正しく解釈する計算機をいきなり作るのはちょっと難しい部分もあります。演算子の優先順位の処理もそうですが、カッコも使いたいと思うと、いっそう処理は複雑になります。そこでまず先に、逆ポーランド記法というものを紹介して、その計算機を作ってみます。

通常の数式の特徴のひとつに、演算子は対象の数の中間におかれるというものがあります。これを特に中置記法ということがあります。

４　＋　５

これに対し、対象の数の後ろに演算子を置くスタイルがあります。これを逆ポーランド記法といいます。

４　５　＋

初めて見る方には奇妙に見えるかもしれません。「＋」という演算子は、その前にある２項に対して働くため、４と５が足しあわされるという意味になります。

もっと長い数式も、逆ポーランド記法で書くことができます。

１　＋　２　×　３　＋　４

１　２　３　×　４　＋　＋

長い式を手動で計算するときは、演算子がどの項に作用するのかが分かりづらく、慣れるのに非常に時間がかかります。コツは数値2項の直後に演算子がある部分をどんどん計算して置き換えていくことです。

逆ポーランド記法の利点は、演算子の優先順位はすべて等しいということです。演算は先に現れたものから順に行えばよいのです。この性質を利用すると、たとえばカッコを使って順序を変更したとしても、記述順が変わるだけで数式が書けます。

（１　＋　２）　×　（３　＋　４）

１　２　＋　３　４　＋　×

このような逆ポーランド記法を解釈する電卓を作ってみましょう。

逆ポーランド計算機

逆ポーランド記法で書かれた数式の計算は、スタックを使うだけで非常に簡単に実装できます。ルールは3つだけです。

1. 数式を左から順に読んでいく
2. 数字が現れたらスタックに積む
3. 演算子が現れたらスタックから2項取り出し、計算してスタックに返す

スタックとはデータ構造の一種です。データを積み上げるように保管するために「スタック」と呼ばれます。データを保存するときはpushといい、スタックの一番上にデータを置くような動作になります。データを取り出すときはpopといいますが、スタックのトップにあるデータしか読みだせません。途中のデータを中抜きすることができない、非常に原始的なデータ構造です。このアルゴリズムを図にするとこうなります。

これをPerlで書いてみましょう。Perlには、配列をスタックのように扱うpushとpop関数がすでにあります。数値をストアするスタックを@sとして、以下のように書くことができます。

#!/usr/bin/perl
use strict;
my @s;
while (<>) {
    chomp;
    foreach my $t (split(/\s+/)) {
        if ($t =~ /^\d+$/) {
            # 数字ならスタックへ
            push(@s, $t);
        } elsif ($t =~ /^[\+\-\*\/]$/) {
            # 演算子なら2項を取り出し計算
            my $b = pop(@s);
            my $a = pop(@s);
            push(@s, eval("$a $t $b"));
        } else {
            print STDERR "$t: unknown op\n";
        }
    }
}
print pop(@s), "\n";
exit 0;

このコードでは暗黙のルールがいくつかあります。まず数値と演算子はすべてスペースで区切る必要があります。逆ポーランド記法では項や演算子を区切る記号が必要なのですが、パーザで手抜きをしているという面もあります。また、エラーチェックをほとんどしていませんので、スタックがアンダーフローしないように注意が必要です。またスタックに積み残しがあっても最後にはトップしか表示しません。

肝心の計算部分でevalを使うインチキをしていますが、そこはご愛嬌ということで勘弁ください。真面目に書くなら演算子ごとにelsif節を増やすことになります。

    } elsif ($t eq "+") {
        my $b = pop(@s);
        my $a = pop(@s);
        push(@s, $a + $b);
    } elsif ($t eq "-") {
        my $b = pop(@s);
        my $a = pop(@s);
        push(@s, $a - $b);
    }
    :
    :

適当な名前、たとえばrpncという名前でプログラムを保存し、実行フラグを立てて動かしてみるとこんな感じになります。

% ./rpnc
1 2 + 3 4 + *
^D
21

普通の数式を逆ポーランド記法に変換する

さて本題です。逆ポーランド記法であれば計算できるようになったので、今度は普通の数式（中置記法）を逆ポーランド記法に変換することを考えてみます。この変換も、スタックを使うことで行うことができます。

1. 数式を左から順に読んでいく
2. 数値だったら出力
3. 演算子だったらスタックに積む
   • スタックトップの演算子の優先順位が高ければそれを出力する
4. 数式を読み終わったらスタック上の演算子を最後まで順に出力する

手順3は、演算子の優先順位を正しく処理するために必要です。どのように違うかを比較してみましょう。

もし、「＋」を読んだときにスタックをチェックせずに積むと、出力結果は「１　２　３　＋　×」になり、２＋３が先に計算されてしまいます。

さてカッコの処理ですが、先ほどのルールにちょっと変更を加えるだけで実現できます。

1. 数式を左から順に読んでいく
2. 数値だったら出力
3. 「（」だったらスタックに積む
4. 「）」だったらスタック上の演算子を「（」が出てくるまで出力する。「（」と「）」は捨てる
5. 演算子だったらスタックに積む
   • スタックトップの演算子の優先順位が高ければそれを出力する
6. 数式を読み終わったらスタック上の演算子を最後まで順に出力する

これも同じく、Perlで書いてみましょう。@rが出力結果となる逆ポーランド記法の式、@opが演算子を保管するスタックです。

#!/usr/bin/perl
use strict;
my @r;
my @op;
my $p;
while (<>) {
    chomp;
    foreach my $t (split(/\s+/)) {
        if ($t =~ /^\d+$/) {
            # 数字ならば出力
            push(@r, $t);
        } elsif ($t eq "(") {
            push(@op, $t);
        } elsif ($t eq ")") {
            while ($#op >= 0 && ($p = pop(@op)) ne "(") {
                push(@r, $p);
            }
        } else {
            # 演算子の処理
            # スタックをチェック
            while ($#op >= 0) {
                $p = $op[$#op];
                if (op_compare($p, $t) <= 0) {
                    # トークンの方が優先順位が高い
                    last;
                }
                # スタックトップの方が優先順位が高いなら出力
                push(@r, pop(@op));
            }
            # トークンをスタックへ
            push(@op, $t);
        }
    }
    # スタックに残ったトークンを出力
    while ($#op >= 0) {
        push(@r, pop(@op));
    }
}
print join(" ", @r), "\n";
exit 0;
sub op_priority
{
    my $op = shift;
    if ($op eq "*" || $op eq "/") {
        return 1;
    } elsif ($op eq "+" || $op eq "-") {
        return 2;
    } elsif ($op eq "(" || $op eq ")") {
        return 99;
    }
    print STDERR "$op: unknown op\n";
    exit 1;
}
sub op_compare
{
    my $o1 = shift;
    my $o2 = shift;
    return op_priority($o2) - op_priority($o1);
}

このプログラムを、例えばconv2rpnのような名前で保存すれば、こんな風に使うことができます。

% ./conv2rpn | ./rpnc
1 / ( ( 2 + 3 ) * 4 ) )
^D
0.05

終わりに

高級な言語ではコンパイルといえばもう少し複雑な手法と手順で構文解析を行います。書籍やWeb上の情報をあたっていただければ、それらの言語がどのように処理しているのかを調べることができるでしょう。しかしスタックを使うだけでも、今回示した通り簡単に数式の処理と計算ができますし、IF文やFOR、WHILEのような構造制御の解析と実行も実装できます。Forthという言語がまさにそのように作られているのですが、これについては別の機会にお話ししてみたいと思います。