Panda Noir

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

操車場アルゴリズム解説

(本記事はリライト記事です。元の記事は削除しました)

逆ポーランド記法は数式からカッコが消せるという魔法のような記法です。今回は中置記法の数式を逆ポーランド記法にする、操車場アルゴリズムについて解説します。

(逆ポーランド記法は「後置記法」とも言います。本記事では以降「後置記法」と呼びます)

中置記法、後置記法とは

中置記法と後置記法は、演算子を「置」く位置が違います中置記法演算子を「真ん中」に置きます。「1+2」は中置記法です。それに対し、後置記法は後ろに演算子を置きます。「1 2 +」という具合です。

中置記法、後置記法のメリット

中置記法のメリットは、数字と数字が演算子で区切れていることです。後置記法の場合、数字同士が連続しているため、「2桁の数字」なのか「1桁の数字が二つ」なのかわかりづらいです。手書きに適しているのは中置記法と言えます。

中置記法のデメリットは、カッコがあることです。数式を計算するプログラムを書こうとしたことがある人はわかると思いますが、カッコがあるだけで構文解析の手間がかなり増えてしまいます。後置記法はカッコが存在しないので、簡単なプログラムで計算ができます

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

前置きが長くなりました。 操車場アルゴリズムの説明に入ります。

アルゴリズムの概要としては

  1. トークンを一つ読み込む
  2. トークンが数値なら出力キューに追加する
  3. トークンが演算子o1のとき、
    1. スタックのトップが演算子トークンではない
    2. スタックのトップの演算子トークンo2があり、
      1. o1の優先度がo2より高い
      2. o1が左結合性でなくo1の優先度がo2以上

    上のどちらかになるまでスタックのトップから演算子トークンを取り出して出力キューに追加し、o1をスタックに入れる。

  4. トークンが左括弧の場合、スタックにプッシュする。
  5. トークンが右括弧の場合
    1. スタックのトップにあるトークンが左括弧になるまで、スタックからポップした演算子を出力キューに追加する動作を繰り返す。
    2. 左括弧をスタックからポップするが、出力には追加せずに捨てる。
  6. 読み込むべきトークンがない場合
    1. スタックが空になるまで演算子をスタックからポップして出力キューに追加する。

wikiには関数がどうとか書いてありますが、今回は中置記法を後置記法にしたいだけなので省略します。

動作例

「1 + 2 * (3 + 4) - 5」という数式を変換してみたいと思います。

番号トークスタック出力キュー動作
11 + 2 * ( 3 + 4 ) - 5トークンに区切る
2+ 2 * ( 3 + 4 ) - 511を出力キューに追加
32 * ( 3 + 4 ) - 5+1+をスタックに追加
4* ( 3 + 4 ) - 5+1 22を出力キューに追加
5( 3 + 4 ) - 5+ *1 2*をスタックに追加
63 + 4 ) - 5+ * (1 2「(」をスタックに追加
7+ 4 ) - 5+ * (1 2 33を出力キューに追加
84 ) - 5+ * ( +1 2 3+をスタックに追加
9) - 5+ * ( +1 2 3 44を出力キューに追加
10- 5+ * ( +1 2 3 4「(」が出るまでスタックをポップする
11- 5+ * (1 2 3 4 ++をポップし出力キューに追加
12- 5+ *1 2 3 4 +「(」をポップし破棄
13- 5+1 2 3 4 + **のほうが-より優先度が高いためポップし出力キューに追加
14- 51 2 3 4 + * ++をポップし出力キューに追加
155-1 2 3 4 + * +-をスタックに追加
16-1 2 3 4 + * + 55を出力キューに追加
171 2 3 4 + * + 5 --をポップし出力キューに追加

このように、演算子が適用する順番(2番目の+ > * > 1番目の+ > -)になるようにアルゴリズムが組まれています。

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

操車場アルゴリズムは、数式だけでなく論理式も扱うことができます。 各命題を項に、「and、or、not、==」を演算子とみたてれば扱えます。 and、orは左結合、notは右結合、==は非結合*1、優先度はnot > == > and > orの順です。

終わりに

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

*1:かっこを使うことができない演算子を指します。例えば(A==B)==Cという式は意味を持ちません