1 + 2 * 3は、7です。小学校の算数で習いましたね。まず先に掛け算、その次に足し算をします。
しかし、プログラム上で1 + 2 * 3を1 + (2 * 3)と解釈するためには、演算子の結合優先度を考慮しないといけません。逆ポーランド記法を用いることで、これを行うことが出来ます。
逆ポーランド記法とは何か
日本語版Wikipediaでは以下のように記述されています。
逆ポーランド記法（ぎゃくポーランドきほう、英語: Reverse Polish Notation, RPN）は、数式やプログラムの記法の一種。演算子を被演算子の後にすることから、後置記法 (Postfix Notation) とも言う。
https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95
演算子は+や*のこと、被演算子は1,2,3のことです。演算子を被演算子の後にする、というのは
1 + 2
を
1 2 +
のように書く、ということです。
ちなみに、1 + 2のような、演算子が被演算子の間に書かれる記法は中置記法と言います。普段使っているのはこちらですね。
逆ポーランド記法の書き方
もう少し複雑な例を見てみましょう。
1 + 2 * 3 – 10 / 5 – 4
かっこをつけると、
((1 + (2 * 3)) – (10 / 5)) – 4
となります。掛け算と割り算を先に行い、その後に足し算と引き算を行います。これを逆ポーランド記法で書くと
1 2 3 * + 10 5 / – 4 –
です。順番に見ていきましょう。
計算する順番で変換していく
一番最初に計算するのは2 * 3の部分です。これを変換すると、2 3 * となります。これをAとおきます。
次に、1 + (2 * 3)を変換します。2 * 3はAとおいていたので、1 + Aを変換し、1 A +となります。これをBとおきます。
次は10 / 5です。これは10 5 /になります。これをCとおきます。
次は(1 + (2 * 3)) – (10 / 5)なので、B – Cです。これを変換すると、B C -です。これをDとおきます。
最後に、D – 4を変換し、D 4 -となります。
文字を式に戻す
結果として、D 4 -が求める逆ポーランド記法です。これを順においた式で戻していけば、文字のない逆ポーランド記法が求まります。
DはB C -でしたので、B C – 4 -になります。
Bは1 A +、Cは10 5 /でしたので、1 A + 10 5 / – 4 -になります。
Aは2 3 *でしたので、1 2 3 * + 10 5 / – 4 -が、求める逆ポーランド記法です。
逆ポーランド記法は一意に決まる？
計算順序が決まっていれば、先程の過程は一意に決まるので、逆ポーランド記法も一意に決まります。しかし、右結合か左結合かによって計算順序が変わるので、逆ポーランド記法も変わります。
例えば、1 + 2 + 3は、右結合の場合は1 + (2 + 3)ですし、左結合の場合は(1 + 2) + 3と解釈されます。それぞれを逆ポーランド記法にすると、右結合の場合は1 2 3 + +、左結合の場合は1 2 + 3 +です。
逆ポーランド記法で書かれた式を計算するプログラムを書いてみよう
逆ポーランド記法で書かれた式を計算するときは、スタックというデータ構造を用います。スタックとは、最後に入れた要素を先に取り出すという決まりがあるデータ構造です。
スタックには、pushとpopという2つの操作があります。pushはデータを入れる操作、popはデータを取り出す操作です。
Pythonではリストをスタックとして扱うことが出来ます。リストのappendメソッドがpush操作、popメソッドがpop操作にあたります。
>>> stack = [1, 2]
>>> stack.append(3)
>>> stack
[1, 2, 3]
>>> stack.pop()
3
>>> stack
[1, 2]
>>> stack.pop()
2
>>> stack
[1]
>>>
これを使って、どうやって計算を行うの？と思うかもしれませんが、以下のような流れで実現できます。
- 式からトークン（演算子、または被演算子）を取り出す
- 取り出したトークンが演算子であれば、スタックから値を2つ取り出し（pop）、計算した値をスタックに入れる（push）
- 取り出したトークンが被演算子であれば、スタックにその値を入れる（push）
- 全てのトークンについて処理し終わった時の、スタックに残った１つの値が計算結果
これをプログラムにします。計算過程が分かるように、スタックの中身も都度表示するようにしてみました。
def calc(exp):
stack = []
tokens = exp.split()
for token in tokens:
print(stack)
# トークンが演算子の場合
# スタックから2回popし、計算した値をpushする
if token == "+":
e1 = stack.pop()
e2 = stack.pop()
stack.append(e2 + e1)
elif token == "-":
e1 = stack.pop()
e2 = stack.pop()
stack.append(e2 - e1)
elif token == "*":
e1 = stack.pop()
e2 = stack.pop()
stack.append(e2 * e1)
elif token == "/":
e1 = stack.pop()
e2 = stack.pop()
stack.append(e2 // e1)
# トークンが被演算子の場合
# スタックにpushする
else:
stack.append(int(token))
# スタックに残っている1つの値が計算結果
return stack[0]
# 計算してみる
exp = "1 2 3 * +"
print(exp, "=", calc(exp))
exp = "1 2 3 * + 10 5 / - 4 -"
print(exp, "=", calc(exp))ラムダ式を使うと、もう少し簡潔になります。
def calc(exp):
stack = []
tokens = exp.split()
for token in tokens:
print(stack)
# トークンが演算子の場合
# スタックから2回popし、計算した値をpushする
operators = {
"+": lambda x, y: x + y,
"-": lambda x, y: x - y,
"*": lambda x, y: x * y,
"/": lambda x, y: x // y
}
if token in operators.keys():
e1 = stack.pop()
e2 = stack.pop()
op = operators(token)
stack.append(op(e2, e1))
# トークンが被演算子の場合
# スタックにpushする
else:
stack.append(int(token))
# スタックに残っている1つの値が計算結果
return stack[0]
# 計算してみる
exp = "1 2 3 * +"
print(exp, "=", calc(exp))
exp = "1 2 3 * + 10 5 / - 4 -"
print(exp, "=", calc(exp))実行結果
[]
[1]
[1, 2]
[1, 2, 3]
[1, 6]
1 2 3 * + = 7
[]
[1]
[1, 2]
[1, 2, 3]
[1, 6]
[7]
[7, 10]
[7, 10, 5]
[7, 2]
[5]
[5, 4]
1 2 3 * + 10 5 / - 4 - = 1まとめ
逆ポーランド記法とは何かについて解説し、その書き方についても言及しました。
また、逆ポーランド記法で書かれた式を計算するプログラムの書き方についても解説しました。
発展課題としては、以下のようなことを考えてみると面白いかもしれません。
- 演算子を増やしてみる
- 中置記法から逆ポーランド記法に変換するプログラムを書いてみる
