(本記事はリライト記事です。元の記事は削除しました)
逆ポーランド記法(後置記法)はカッコが存在しない魔法のような記法です。今回は中置記法の数式を逆ポーランド記法にする、操車場アルゴリズムについて解説します。
(逆ポーランド記法は「後置記法」とも呼びます。本記事では以降「後置記法」と呼びます。)
中置記法、後置記法とは
まず、そもそも中置記法と後置記法とは何かについて説明します。これらは演算子を「置」く位置による式の分類です。
中置記法は演算子を「真ん中」に置きます。例えば「1+2」は中置記法です。それに対し、後置記法は後ろに演算子を置きます。「1 2 +」という具合です。
中置記法、後置記法のメリット
中置記法のメリットは、数字と数字が演算子で区切れていることです。後置記法の場合、「1 2 +」のように数字が連続するため、「2桁の数字」なのか「1桁の数字が二つ」なのかわかりづらいです。そのため、中置記法のほうが手書きに適しています。
中置記法のデメリットは、カッコがあることです。数式を計算するプログラムを書いたことがあればわかると思いますが、カッコがあるだけで構文解析の手間がかなり増えます。後置記法はカッコが存在しないので、簡単なプログラムで式を計算できます。
操車場アルゴリズムの内容
では操車場アルゴリズムの説明に入ります。操車場アルゴリズムは中置記法の式を後置記法へ変換するアルゴリズムです。
アルゴリズムの概要はこちらです。
- トークンを一つ読み込む
- トークンが数値なら出力キューに追加する
- トークンが演算子o1のとき、
- スタックのトップが演算子トークンではない
- スタックのトップの演算子トークンo2があり、
- o1の優先度がo2より高い
- o1が左結合性でなくo1の優先度がo2以上
上のどちらかになるまでスタックのトップから演算子トークンを取り出して出力キューに追加し、o1をスタックに入れる。
- トークンが左括弧の場合、スタックにプッシュする。
- トークンが右括弧の場合
- スタックのトップにあるトークンが左括弧になるまで、スタックからポップした演算子を出力キューに追加する動作を繰り返す。
- 左括弧をスタックからポップするが、出力には追加せずに捨てる。
- 読み込むべきトークンがない場合
- スタックが空になるまで演算子をスタックからポップして出力キューに追加する。
(wikiには関数についても書かれていますが、今回は中置記法を後置記法にしたいだけなので省略します。)
動作例
「1 + 2 * (3 + 4) - 5」という数式を変換してみたいと思います。
| 番号 | トークン | スタック | 出力キュー | 動作 |
|---|---|---|---|---|
| 1 | 1 + 2 * ( 3 + 4 ) - 5 | トークンに区切る | ||
| 2 | + 2 * ( 3 + 4 ) - 5 | 1 | 1を出力キューに追加 | |
| 3 | 2 * ( 3 + 4 ) - 5 | + | 1 | +をスタックに追加 |
| 4 | * ( 3 + 4 ) - 5 | + | 1 2 | 2を出力キューに追加 |
| 5 | ( 3 + 4 ) - 5 | + * | 1 2 | *をスタックに追加 |
| 6 | 3 + 4 ) - 5 | + * ( | 1 2 | 「(」をスタックに追加 |
| 7 | + 4 ) - 5 | + * ( | 1 2 3 | 3を出力キューに追加 |
| 8 | 4 ) - 5 | + * ( + | 1 2 3 | +をスタックに追加 |
| 9 | ) - 5 | + * ( + | 1 2 3 4 | 4を出力キューに追加 |
| 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 | - 5 | 1 2 3 4 + * + | +をポップし出力キューに追加 | |
| 15 | 5 | - | 1 2 3 4 + * + | -をスタックに追加 |
| 16 | - | 1 2 3 4 + * + 5 | 5を出力キューに追加 | |
| 17 | 1 2 3 4 + * + 5 - | -をポップし出力キューに追加 |
このように、演算子が適用する順番(2番目の+ > * > 1番目の+ > -)になるようにアルゴリズムが組まれています。
操車場アルゴリズムの応用例
操車場アルゴリズムは、数式だけでなく論理式も扱うことができます。 各命題を項に、「and、or、not、==」を演算子とみたてれば扱えます。 and、orは左結合、notは右結合、==は非結合*1、優先度はnot > == > and > orの順です。
終わりに
操車場アルゴリズムは数式、論理式だけでなく、もっと幅広く応用できます。頭の片隅に入れておくといいかもしれません。
*1:かっこを使うことができない演算子を指します。例えば(A==B)==Cという式は意味を持ちません