基本情報技術者試験では、「次の式を後置表記法で表現したものはどれか。」みたいな問題が出たりします。
逆ポーランド記法？ YAB-= とか YAB＋CDE÷－×＝ とか、なにそれ？？
となったので、
逆ポーランド記法についてと、中置記法→逆ポーランド記法の置換方法についてまとめます。
「数字 数字 演算子」が後置記法（逆ポーランド記法）
計算式を 「数字 数字 演算子」の順番で書くのが逆ポーランド記法です。
演算子は「＋」とか「−」とか「✕」ですね。
1 + 2 なら 2 1 +
4 / 2 なら 4 2 /
となります。
普段使っている計算式は「数字 演算子 数字」で「中置記法（ちゅうちきほう）」
逆ポーランド記法は「数字 数字 演算子」で「後置記法（後置記法）」ともいう
「前置記法」なんて書き方もある
普段使っている計算式から後置記法に直す
「1 + 1」の式を「1 1 +」に直すようなときです。
普段使っている計算式（中置記法）から逆ポーランド記法に直す際にはルールがあります。
「数字 演算子 数字」を「数字 数字 演算子」に直す
1 + 2 なら 2 1 +
4 / 2 なら 4 2 /
にする
置換するところがいくつもあるときは、優先順位の順で計算する
数学や算数で「計算するときは()の中身を先に計算する」と習いましたよね。
あのルールに沿って、順番に置換していきます。
例えば
8 = 2 * ( 1 + 5)
という式があったとすると、最初に置換するのは (1 + 5) の部分です。
8 = 2 1 5 +
置換するところがいくつもあるときは、置換した部分を変数にしておくと便利
先ほど「8 = 2 * ( 1 + 5)」を「8 = 2 1 5 +」に置換しましたが、これだと次はどこを置換すればいいのかわかりづらいですよね。
なので、すでに置換してしまった部分は変数にしてしまうとわかりやすいです。
変数といってしまうと難しい感じがしますが、要は 数字のかわりにアルファベットなどで置き換えて見た目をわかりやすくする イメージです
例えば、先程の「1 5 +」 は今後アルファベットの「x」で表すことにしましょう。
8 = 2 * x
となりました。
上記のルールにのっとって置換を続けていくと
8 = 2 * x ←（’2 x * ‘ を変数 y とする）
8 = y
8 y =
となります。
式全体を変換したら、置き換えた部分を元に戻す
あとは変数にした部分を数字に戻せば、後置記法の式の完成です。
たとえば先程、「8 = 2 * ( 1 + 5)」を変換した結果
y = 2 x *
x = 1 5 +
8 y =
という式になりましたね。
この「8 y =」を、数字を使った式に戻していきます。
y = 2 * xなので、「8 y =」は
8 2 x * =
x = 1 5 +なので、「8 2 x *」は
8 2 1 5 + * =
これで、「8 = 2 * ( 1 + 5)」を後置記法の式に書き直すことができました！
※変数がいくつもあるときは、後ろの変数から先に戻していくとやりやすいです。
練習問題
10 + 20 を後置記法に置換する
10 + 20
10 20 + ※「数値 数値 演算子」の形にする
答え.10 20 +
1 + 2 * (3 – 4) を後置記法に置換する
1 + 2 * (3 – 4)
1 + 2 * 3 4 - ※まず最初に (3 – 4)を「数値 数値 演算子」の形にする
1 + 2 * A ※「(3 4 -)」を変数Aに置換
1 + 2 A * ※2 * Aを「数値 数値 演算子」の形にする
1 + B ※「2 A *」を変数Aに置換
1 B + ※「数値 数値 演算子」の形にする
ここで全てが「数値 数値 演算子」の形になったので、変数を元に戻していきます。
A = 3 4 - ※()は「先に計算する」という目印なので省略
B = 2 A *
1 B +
1 2 A *
1 2 3 4 – *
答え. 1 2 3 4 – *
Y = (A + B) * (C – (D / E)) を後置記法に置換する
Y = (A + B) * (C – (D / E))
Y = A B + * (C – (D / E)) ※(A + B)を「数値 数値 演算子」の形にする
Y = J * (C – (D / E)) ※「A B +」を変数Jに置換
Y = J * (C – D E /) ※ (D / E)を「数値 数値 演算子」の形にする
Y = J * (C – K) ※「D E /」を変数Kに置換
Y = J * C K - ※(C – K)を「数値 数値 演算子」の形にする
Y = J * L ※「C K -」を変数Lに置換
Y = J L * ※J * L を「数値 数値 演算子」の形にする
Y = M ※「J L *」を変数Mに置換
Y M =
ここで全てが「数値 数値 演算子」の形になったので、変数を元に戻していきます。
J = A B +
K = D E /
L = C K –
M = J L *
Y M =
Y J L * =
Y J C K – * = ※JとLどちらを先に戻すか迷いますが、後ろから戻していきます。Lを戻します
Y J C D E / – * ※Kを戻します
Y A B + C D E / – * = ※Jを戻します
答え. Y A B + C D E / – * =
戻すときは後ろから、というルールは無いのかもしれませんが
どこから変換していく、というのが決まっていると計算する際に迷いにくかったです。
参考
逆ポーランド記法の説明について、こちらの動画にお世話になりました。
逆ポーランド記法の説明だけでなく、他のシリーズの説明もめちゃくちゃわかりやすいです。
