はじめに
AOJをちまちまと解いていて久しぶりに「逆ポーランド記法」に触れました。
0087:Strange Mathematical Expression
ということで復習がてらPythonで逆ポーランド記法(RPN:Reverse Polish Notation)を書いてみました。
そもそも逆ポーランド記法とは
大学の授業で習ったときは「へぇ～、いちいち括弧を書かなくて済むし慣れたら使いやすそうな書き方だなぁ～」程度にしか思っていませんでした。
難しく考えなくても計算したい数字や演算子の入力をすべて待たなくても済むというだけでコンピュータとの相性は良さそうです。
また、日本人との相性も良さそうです。
たとえば
「(1 + 3) * (9 - 2)」
という普段慣れ親しんだ数式表現（これを中置記法と呼びます。）を逆ポーランド記法で記述すると
「1 3 + 9 2 - *」
のように書き換えられます。
これはつまり、
「１と３を足して、９から２を引き、それらを掛ける」
というなんとも日本語的な翻訳がなされているわけです。
Stackを使えば、記述も簡単です。
・入力が数値であればStackにPush
・入力が演算子であればStackから引数分の数値をPopして演算し、戻り値をまたPush
これを繰り返すだけです。
ちなみに、これは余談ですがなぜ「（逆）ポーランド記法」と呼ばれているのかご存知でしょうか？
僕はてっきりポーランドではこのような記述方法が一般的なのかと勘違いしていました（え？）がそうではありません。
もともとこの記述方法を考案した論理学者ヤン・ウカシェヴィチがポーランド人であったから呼ばれているそうです。
だとすれば「ウカシェヴィチ記法」などと呼ばれそうなものですが、Jan Łukasiewiczという彼の名前は当時の英国人には発音が難しかったため「ポーランド記法」とざっくりとした名称で呼ばれるようになったそうです。
優先順位を表す括弧の表記を無くすことを目的として考案されたポーランド記法が括弧の多さに定評のあるLispに採用されているのは何とも皮肉なものです。
実際にPythonで書いてみる
def RPN(states):
'''
逆ポーランド記法を計算する関数
'''
operator = {
'+': (lambda x, y: x + y),
'-': (lambda x, y: x - y),
'*': (lambda x, y: x * y),
'/': (lambda x, y: float(x) / y)
}
stack = []
print('RPN: %s' % states)
for index, z in enumerate(states):
if index > 0:
print(stack)
if z not in operator.keys():
stack.append(int(z))
continue
y = stack.pop()
x = stack.pop()
stack.append(operator[z](x, y))
print('%s %s %s =' % (x, z, y))
print(stack[0])
return stack[0]
def test():
print("OK" if RPN("37+621-*+") == 16 else "NG")
if __name__ == '__main__':
import sys
RPN(sys.argv[1])
test()
$ python rpn.py 37+621-*+
RPN: 37+621-*+
[3]
[3, 7]
3 + 7 =
[10]
[10, 6]
[10, 6, 2]
[10, 6, 2, 1]
2 - 1 =
[10, 6, 1]
6 * 1 =
[10, 6]
10 + 6 =
[16]
OK
おわりに
復習がてらいくつかサイトを見ていたら実装にenumerate関数を使っている人が多かったので真似をしました。
>>> a = ['a','b','c']
>>> for x in a:
... print(x)
...
a
b
c
のようなlistに対して
>>> a = ['a','b','c']
>>> for i,x in enumerate(a):
... print('%d : %d' % (i,x))
...
0 : a
1 : b
2 : c
のような処理ができます。
お恥ずかしい話、今日まで使ったことがなかったのですがindexと要素を同時に取り出したい場合（こんかいのような場合）には非常に便利だということがわかりました。
※@shiracamusからご指摘いただき、enumerateを使わなくても実装ができました。一応残しておきますが、参考までに。
最後に全然関係ないですが、PRN計算が可能な電卓がAmazonリストにまとめられていました。
欲し...くはないかな？