(本記事はリライト記事です。元の記事は削除しました)
逆ポーランド記法は数式からカッコが消せるという魔法のような記法です。今回は中置記法の数式を逆ポーランド記法にする、操車場アルゴリズムについて解説します。
(逆ポーランド記法は「後置記法」とも言います。本記事では以降「後置記法」と呼びます)
中置記法、後置記法とは
中置記法と後置記法は、演算子を「置」く位置が違います。中置記法は演算子を「真ん中」に置きます。「1+2」は中置記法です。それに対し、後置記法は後ろに演算子を置きます。「1 2 +」という具合です。
中置記法、後置記法のメリット
中置記法のメリットは、数字と数字が演算子で区切れていることです。後置記法の場合、数字同士が連続しているため、「2桁の数字」なのか「1桁の数字が二つ」なのかわかりづらいです。手書きに適しているのは中置記法と言えます。
中置記法のデメリットは、カッコがあることです。数式を計算するプログラムを書こうとしたことがある人はわかると思いますが、カッコがあるだけで構文解析の手間がかなり増えてしまいます。後置記法はカッコが存在しないので、簡単なプログラムで計算ができます。
操車場アルゴリズムの内容
前置きが長くなりました。 操車場アルゴリズムの説明に入ります。
アルゴリズムの概要としては
- トークンを一つ読み込む
- トークンが数値なら出力キューに追加する
- トークンが演算子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の順です。
終わりに
数式、論理式だけでなく、もっと幅広く応用できるアルゴリズムだと思うので頭の片隅に入れておくといいかもしれません。