Photo by Keira Burton from Pexels
逆ポーランド記法はIPAの情処試験の問題などで見たことがあったので、存在は知っていたがよく考えたことがなかった。
$$ 3 4 5 + \times $$
↑こんなやつ
コーディングテストの題材として、中置記法で書かれた数式の文字列を評価して計算結果を返す、というものがあった。
数式の文字列を評価してプログラムで計算する場合、逆ポーランド記法で書かれている方が断然扱いやすい。
なので中置記法で書かれた数式をまず逆ポーランド記法に変換してから、それを計算するという形で実装した。
逆ポーランド記法の計算方法について備忘録
中置記法
我々が普通数学などでつかう式の書き方
例
$ 2+5\times3 $
逆ポーランド記法
例
$ 253\times+ $
解き方
左から順に数字を読んでいき、記号が来たら直前の２つの数字に対して計算を行う
[2]
[2 5]
[2 5 3]
[2 5 3 *] <- 記号があったら直前の２つの数字に対して計算
[2 15]
[2 15 +] <- 2 + 15
[17]
上記の通り計算アルゴリズムがデータ構造のスタックと相性がよく、プログラムで評価しやすい
Pythonで逆ポーランド記法を解く
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
def solveRPN(rpn):
stack = []
for n in rpn:
if isOperator(n):
o1 = stack.pop()
o2 = stack.pop()
stack.append(operate(o2, o1, n))
else:
stack.append(n)
return stack[0]
def isOperator(c):
return c in ["+", "-", "*", "/"]
def operate(o1, o2, operator):
if operator == "+":
return o1 + o2
if operator == "-":
return o1 - o2
if operator == "*":
return o1 * o2
if operator == "/":
return o1 // o2
if __name__ == '__main__':
print(solveRPN([2, 5, 3, '*', '+']))
# Output: 17
|
参考リンク
逆ポーランド記法 - Wikipedia
操車場アルゴリズム - Wikipedia