逆ポーランド記法(RPN)計算機を作ってみよう

前回、なでしこで自作電卓を作る方法を紹介しました。自分専用電卓を作るのはとても愉しいものです。さて、今回は一部のマニアの間で今も重宝されている「逆ポーランド記法(RPN)」で記述する電卓を作ってみましょう。

• 逆ポーランド記法で計算できる電卓を作ってみよう

逆ポーランド記法(RPN)とは？

最初に「逆ポーランド記法(RPN/Reverse Polish Notation)」について紹介します。逆ポーランド記法というのは、数式の記法の一種で、演算子を数値(被演算子)の後ろに記述するものです。

例えば、私たちが日常的に使う足し算の計算式であれば「5 + 8」のように、記述しますが、逆ポーランド記法では「5 8 +」と書きます。演算子を後ろに書くので「後置記法」とも呼ばれます。そして、後置記法に対して、私たちが日常的に使う計算式を「中置記法」と呼びます。

• 逆ポーランド記法は日本語で計算式を読み上げるのと同じ

ちなみに、筆者は「逆ポーランド記法」が日本語との親和性が高いと思っています。と言うのも、逆ポーランド記法は、日本語で計算式を読み上げる順番と同じなのです。例えば、「5 + 8」を日本語で読み上げると「5に8を足す」と言います。これを記号に置き換えると「5(に) 8(を) +(足す)」となり、容易に逆ポーランド記法にすることができます。

もう少し、複雑な逆ポーランド記法で考えた場合も、同じ要領で言い換えができます。中置記法の「3 × 5 + 4」を逆ポーランド記法に変換してみましょう。計算式を日本語読みするだけです。「3に5を掛けて4を足す」つまる「3(に) 5(を) ×(掛けて) 4(を) +(足す)」、カッコを取り外せば「3 5 × 4 +」となり、正しい逆ポーランド記法にすることができました。

逆ポーランド記法はコンピューター処理に適した記法

逆ポーランド記法は「スタック」と呼ばれるデータ構造を使うことで、手軽に計算できます。中置記法よりもずっと簡単に計算できるため、初期のプログラミング言語のForthやPostScriptでは、プログラムや計算式の記述を、この逆ポーランド記法で記述することになっています。

加えて、日本語と相性が良いということは、日本語プログラミング言語とも相性が良いということです。実際、日本語のように記述できるForthの実装もあります。「Mind」という日本語プログラミング言語がありますが、Forthの考え方を取り入れています。また、本連載で扱っている「なでしこ」もMindと同じように、Forthの影響を受けています。

スタック構造について

逆ポーランド記法の計算機を作るのにあたって、「スタック(stack)」構造を学ぶ必要があります。スタックとは、コンピューターでよく使われるデータ構造であり、最初に追加したデータは最後に取り出し、最後に追加したデータは最初に取り出すというルールで管理するものです。

• スタック構造について

これは、机の上にたくさんの積み木を重ねて載せていくのに似ています。既にいくつかの積み木を積んである場合、下にある積み木を無理に取ろうとすると崩れてしまいます。そこで、積み木の上から順番に(つまり最後に載せた積み木から)取っていくと、崩すことなく積み木を取ることができます。

逆ポーランド記法を計算するプログラムを作ろう

具体的に、逆ポーランド記法を計算するには、このスタックを使って、次の手順で計算を行います。

- (1) 式からトークンを1つ取り出してtとする
- (2) もし、tが数値であれば、スタックに積む
- (3) もし、tが演算子であれば、スタックから2つ値を下ろし、計算を行って、スタックに載せる
- (4) 式が空になるまで上記手順を繰り返す
- (5) スタックから値を1つ下ろし、それを式の答えとする

この手順をプログラムにすると、次のようになります。下記のプログラムを、なでしこ3貯蔵庫に貼り付けて実行してみてください。コメントを含めて、わずか38行のプログラムですが、しっかり逆ポーランド記法で四則演算が可能です。なお、今回のプログラムはこちらにもアップしています。

# 入力画面を作る --- (*1)
式エディタ＝「3 5 × 4 +」のエディタ作成。
計算ボタン＝「計算」のボタン作成
結果エディタ＝「」のエディタ作成。
計算ボタンをクリックした時には
　　S=(式エディタからテキスト取得)
　　Sを逆ポーランド計算して答えに代入。
　　結果エディタに答えをテキスト設定。
ここまで。

●（Sを）逆ポーランド計算とは # --- (*2)
    スタックは[]
    Sを「 」で区切って反復 # --- (*3)
        C=対象
        「+-*×/÷%」でCが何文字目 # 演算子か？ ---- (*4)
        もし、そうならば
            # 値を2つ取り出す --- (*5)
            B=スタックから配列ポップ。
            A=スタックから配列ポップ。
            # 計算をしてスタックに積む --- (*6)
            もし、C=「+」ならば
                スタックに(A+B)を配列追加。。。
            もし、C=「-」ならば
                スタックに(A-B)を配列追加。。。
            もし、(C=「*」)または(C=「×」)ならば
                スタックに(A*B)を配列追加。。。
            もし、(C=「/」)または(C=「÷」)ならば
                スタックに(A/B)を配列追加。。。
            もし、C=「%」ならば
                スタックに(A%B)を配列追加。。。
        違えば
            C=INT(C) # 数値ならスタックに積む --- (*7)
            スタックにCを配列追加。
        ここまで。
        # スタックをJSONエンコードして表示。
    ここまで。
    スタックから配列ポップ。# 答えを取り出す --- (*8)
ここまで。

プログラムを実行すると、下記のような画面が表示されます。左側のテキストボックスに式を入力し「計算（＝）」ボタンを押すと、逆ポーランド記法の式を計算して、右側のテキストボックスに結果を表示します。

• 逆ポーランド記法のプログラムを実行したところ