逆ポーランド記法
妹ちゃんが宿題をしています。
妹ちゃん「１、１たすは、２。１、２たすは３。」
ワイ「妹ちゃん、やっぱりまだ小学生低学年だな…『１たす１は２』じゃないの？」
妹ちゃん「お兄ちゃん、これは【逆ポーランド記法】なのよ」
ワイ「逆・・・ポーラ・・・なに？( ﾟдﾟ)」
妹ちゃん「逆ポーランド記法。逆ポーランド記法にするとカッコを省略できるのよ。すごくない？」
ワイ「どういうことだってばよ・・・」
中置記法（Infix Notation）
1 + ( 4 - 2 ) x 3
という式があったとします。人間にとってはすごく簡単な計算ですね。
しかし、この書き方では
- ()を先に計算しなければならない（括弧優先のルール）
- ＋－より×÷を先に計算しなければならない（四則演算のルール）
という制約があり、これをプログラムで実現しようとするとそれなりに長い量のコードが必要になってきます。
ちなみに、このような数式の記述方法を中置記法といいます。
前置記法＝ポーランド記法（Polish Notation）
一方、同じ計算式を
- 四則演算子（+-x÷）を始めに書く
- 演算子の対象（左右の数字）を2つ目、3つ目に書く
というルールに従って
+ 1 x - 4 2 3
のように表現することもできます。
このような書き方をポーランド記法といいます。
ポーランド人論理学者、ヤン・ウカシェヴィチが考案したことが名前の由来です。
特徴として、元あった括弧がなくなり、すっきりとしました。
これをプログラムで処理するためには、左端から１文字ずつ読み取り、空白で区切って順番に処理します。
- 演算子の場合、左データと右データの箱（メモリ）を用意する。両方のデータが揃った時点で計算結果をスタックに乗せる。
- 数字の場合、演算子の次であれば左データの箱に、左データの次の位置であれば右データの箱にその値をセットする
- スタックに値がある場合、左データまたは右データの箱が空いている場合はスタックから値を取り出しそこに代入する
- 最後にスタックに残っていた値が計算結果
図１ ポーランド記法による計算手順
後置記法＝逆ポーランド記法（Reverse Polish Notation, RPN）
さらに、これをもっと改善して計算機（CPU）に処理しやすく改善したものが「逆ポーランド記法」です。
その名の通り、ポーランド記法を逆に並べたものが逆ポーランド記法です。
1 4 2 - 3 x +
ポーランド記法では演算子を最初に書きますが、逆ポーランド記法は数値の後に演算子を置きます。
*ポーランド記法**では「演算子の箱」「左データの箱」「右データの箱」「スタック」「計算結果の箱」の５つの要素（メモリ）が必要でしたが、逆ポーランド記法では「スタック」のみで計算できます。
- 数値が来た場合、そのままスタックの上に乗せる
- 演算子が来た場合、スタックから値を２つ取り出し、計算結果をスタックに乗せる
- 最後にスタックに残っていた値が計算結果
図２ 逆ポーランド記法による計算手順
スタックマシンとレジスタマシン
このように、スタックのみで数式を計算する計算機を「スタックマシン」といいます。一方、スタック以外の複数のメモリを使うポーランド記法のような計算機を「レジスタマシン」といいます。
一般にレジスタマシンよりもスタックマシンの方が実装がシンプルになります。
マインド・エンジンも、スタックマシンをベースとしています。
（一部オペコードでレジスタも使用）
マインド・エンジンにおける実装
上記の例では整数のみの計算でしたが、マインド・エンジンでは整数の計算以外に以下の計算もできます。
- 小数（Float）の四則計算
- 変数（Variables）の四則計算
小数の場合は単純にfloatの値をスタックで扱えるように拡張、変数の場合は変数の値をスタックで扱います。
中置記法→逆ポーランド記法への変換
逆ポーランド記法はコンピュータにとって優しい記述であることは事実ですが、一般的に人間にとっては中置記法の方が分かりやすいため、多数のプログラミング言語が中置記法を採用しています。
（ちなみに人工知能分野で使われてきたLISP言語はポーランド記法）
そのため、仮想マシンで／機械語を問わずスタックマシンのコンパイラは中置記法→逆ポーランド記法への変換処理を実装するのが標準的と言えるでしょう。
この処理はスタックマシンで逆ポーランド記法の計算を行うよりは少しだけ複雑ですが、以下のルールをすべて実装すれば実現可能です。
（四則演算＆括弧）
- 入力となる中置記法の数式をトークン化（数値／演算子／括弧に分割）
- 左側のトークンから順番に処理
- トークンが数値だった場合：そのまま出力
- 開き括弧【（】だった場合：スタックへPush
- 閉じ括弧【）】だった場合：開き括弧【（】が出るまでスタックからPopして括弧以外を出力
- 演算子【＋－×÷】の場合：スタックが空であるか、スタックトップの演算子の優先度より高いならそのままスタックへPush、それ以外ならスタックのすべてのデータを順番にPopし、出力
- 入力トークンをすべて処理した後、スタックにデータが残っていればすべてを順番にPopし、出力
各演算子の優先度は以下のようになっています。
| 演算子 | 優先度 |
|---|---|
| × ÷ | 高 |
| + - | ↑↓ |
| ( ) | 低 |
コンパイラによるバイトコードの出力
コンパイラでソースコードの数式からバイトコードを出力する場合、
のような順番で処理します。
例えば、先ほどの
1 4 2 - 3 x +
という逆ポーランド記法の数式があった場合、これをオペランド・オペコードに変換すると
PUSHL 1
PUSHL 4
PUSHL 2
SUB
PUSHL 3
MUL
ADD
のように、左から右に向かって順番にオペランド・オペコードに変換します。簡単ですね。
PUSHLは整数をスタックにPush、SUB、MUL、ADDはそれぞれ四則演算の差、積、和に該当します。
（下記の表参照）
| オペコード | オペランド | 処理 |
|---|---|---|
| PUSHL | 数値１つ | オペランドをスタックにPush |
| SUB | なし | スタックから２つの値をPopし、それらの差をスタックに積む |
| MUL | なし | スタックから２つの値をPopし、それらの積をスタックに積む |
| ADD | なし | スタックから２つの値をPopし、それらの和をスタックに積む |
まとめ
- 中置記法は数学で見るような人間にとって分かりやすい数式の表現
- 前置記法（ポーランド記法）は演算子を最初に、データを後に記述する
- 後置記法（逆ポーランド記法）はデータを最初に、演算子を最後に記述する
- コンピュータにとっては逆ポーランド記法がもっとも簡単に処理できる
- 仮想マシンでは、コンパイラがソースコード（中置記法）から逆ポーランド記法に変換している
最後に
株式会社ロボマインドではこれまでにないAI、『マインド・エンジン』の制作に一緒に携わっていただける開発者の方を募集しています。下記に興味または実績がある方はふるってご応募ください。お待ちしています！
- ディープラーニングの知識または技術をお持ちの方
- ディープラーニングに詳しくなくても、AIの開発に興味のある方
- 自然言語処理の知識または技術をお持ちの方
- AI技術の応用（メタバースやロボット等）に関心のある方
- C#、Java等オブジェクト指向プログラミングの経験のある方
ご応募は会社の採用応募フォームまたは私のTwitterまでDMをお願いします。
次の記事
前の記事