December
29

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

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

操車場アルゴリズムとは

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

さて、ここで一応中置記法、逆ポーランド記法について軽く触れておきます(この記事を読んでいる人はきっと中置記法を逆ポーランド記法に変換したくて読んでる人がほとんどだと思うのですが)。

逆ポーランド記法とは別名後置記法とも言います。中置記法と後置記法の違いは、演算子(+とか*とか)を置く位置です。中置記法はその名の通り真ん中に置きます。例えば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は右結合、==は非結合、優先度はnot == and orの順です(非結合というのはかっこを使うことができない演算子を指す言葉です。(A==B)==Cという命題は解釈の仕様がありませんよね)。

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

終わりに

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

Leave a Reply

Name *

Mail

URL

Comment *

※私が承認したコメントのみ表示されます。
トラックバック URL

×

この広告は1年以上新しい記事の投稿がないブログに表示されております。