読者です 読者をやめる 読者になる 読者になる

Panda Noir

JavaScript の限界を究めるブログです。

中置記法の数式を逆ポーランド記法の数式に変換する、操車場アルゴリズム

逆ポーランド記法、便利ですよね。かっこが数式から消えてなくなる辺りがナイスです。

操車場アルゴリズムとは

操車場アルゴリズムとは、中置記法逆ポーランド記法に変換するための直感的なアルゴリズムです。

 

さて、ここで一応、中置記法逆ポーランド記法について軽く触れておきます。

逆ポーランド記法とは別名「後置記法」とも言います。中置記法 と 後置記法 の違いは、演算子を置く位置です。

 

中置記法はその名の通り演算子を真ん中に置きます。例えば1+2のように。それに対し、後置記法は後ろに演算子を置きます。1 2 +.という具合です。

 

後置記法では、計算方法が中置記法とは若干異なります。まず、1 2 + 3 *.という後置記法の数式があったとします。この場合まず、演算子がでるまで要素をスタック(FIFO)にプッシュしながら読んでいきます。

 

この例では、はじめに出てくる演算子は+です。演算子がでたら、スタックから2つポップし、それらに演算子を適応させ、計算結果をスタックにプッシュします。最後に残った要素が計算結果です。

 

中置記法は小学校から習っている通りです。演算子の左右の要素に適応させます(負の数を表すマイナスはまた別ですが)。

 

中置記法、後置記法それぞれメリットデメリットがあります。中置記法のメリットは、「数字、演算子、数字」の順に並ぶので読み間違えることがないです。例えば中置記法なら1+2.は1通りでしか読めません。それに対し後置記法だと12+.などと先ほどの数式からスペースを抜いたりしてしまえば全然違う数式となってしまいます。というか数式として成り立っていません。手書きで後置記法するのはあまり得策ではありません。

 

では中置記法のデメリットは何かというと、かっこがあることです。例えば(1+2)*3.はかっこをなくすと1*3+2*3.となります。数式を計算するプログラムを書こうとしたことがある人はわかると思いますが、分配法則をコンピュータで適応させるのはとても面倒です。考えるのも億劫ですよね。それに対し、後置記法はかっこが必要ありません。(1+2)*3.という中置記法の数式を後置記法に直すと1 2 + 3 *.となります。先頭から順に適応させていくという特殊な計算方法によりかっこが不要となるのです。

 

かっこが消える。これだけでコンピュータでの処理のしやすさが格段に変わってきます。前に書いたとおり、後置記法は前から読んで演算子を適応させるだけなのですから。そして、中置記法を後置記法似直すのが操車場アルゴリズムです。

操車場アルゴリズムの内容

wikiを見ていただければわかると思います。その中でわからないであろう言葉だけピックアップします。

 

まず「左結合性」ですね。左結合性というのは、演算子がどちらから結合するのかということです。A ・ B ・ Cという式(A,B,Cは項、・は演算子)があったとします。そのとき、(A・B)・Cとしても式が変わらないのが左結合、A・(B・C)が右結合です。

 

例えばマイナスは左結合です。(A-B)-CとA-(B-C)は全然意味が違いますよね。別にA+(-B-C)とすれば式を成立させれますが、その場合A・(B・C)の一つ目の・が消えるので右結合ではありません。

 

左結合の演算子には+ - * / %、右結合の演算子には! =などがあります。

操車場アルゴリズムの応用例

操車場アルゴリズムは数式だけでなく命題も扱うことができます。

各命題を項、and、or、not、==を演算子とみたてれば操車場アルゴリズムが使えることからすぐわかります。

andは左結合、orは左結合、notは右結合、==は非結合、優先度はnot == and orの順です(非結合というのはかっこを使うことができない演算子を指す言葉です。(A==B)==Cという命題は解釈の仕様がありませんよね)。

 

これらの知識と後置記法の計算方法を少し改良するだけで簡単に命題の処理をかけることができます。

終わりに

命題、数式と言いましたが、もっと幅広く応用できるアルゴリズムだと思うので頭の片隅に入れておくといいかもしれません。