ポーランド記法について
概要
- 数学でよく使う中置記法にくらべてコンピュータなどでパースしやすくした記法がポーランド記法
op num1 num2みたいな記法になる- この記法にすると二分木の記法にもすることができる
- 逆ポーランド記法とよばれるポーランド記法を逆にしたものを用いると、リストの操作のみで計算することができる
逆ポーランド記法のパースと計算
def remove_and_insert(i, y, tokens):
tokens.pop(i)
tokens.pop(i)
tokens.pop(i)
tokens.insert(i, y)
def solve(tokens):
i = 2
while 1:
if len(tokens) == 1:
break
match tokens[i]:
case "+":
y = int(tokens[i-2]) + int(tokens[i-1])
remove_and_insert(i-2, y, tokens)
i = 2
continue
case "-":
y = int(tokens[i-2]) - int(tokens[i-1])
remove_and_insert(i-2, y, tokens)
i = 2
continue
case "*":
y = int(tokens[i-2]) * int(tokens[i-1])
remove_and_insert(i-2, y, tokens)
i = 2
continue
case "/":
y = int(tokens[i-2]) / int(tokens[i-1])
remove_and_insert(i-2, y, tokens)
i = 2
continue
i += 1
return int(tokens.pop())
assert solve(["2","1","+","3","*"]) == 9 # ((2 + 1) * 3) = 9
assert solve(["4","13","5","/","+"]) == 6 # (4 + (13 / 5)) = 6
assert solve(["10","6","9","3","+","-11","*","/","*","17","+","5","+"]) == 22 # ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22