👻
【Python】逆ポーランド記法
作るもの
逆ポーランド記法(Reverse Polish Notation、RPN)を使用して表現された数式を計算する関数。
中置記法で表現された式「3 + 4」を逆ポーランド記法に変換すると「3 4 +」となる。この式をRPNで解釈すると、最初に「3」と「4」をスタックに積み、次に「+」演算子が来たときにスタックから2つの数値を取り出して演算し、計算結果をスタックに戻すという手順が続く。
実装
rpn.py
def evaluate_rpn(expression):
stack = [] # 演算対象の数値や中間結果を保持するスタック
# RPN式の各トークンを順に処理
for token in expression:
# トークンが数値かどうかをチェック(負数も考慮)
if token.isdigit() or (token[0] == "-" and token[1:].isdigit()):
stack.append(int(token)) # 数値をスタックに追加
else:
b = stack.pop() # スタックから2つの数値を取り出す(後に処理する数値)
a = stack.pop() # スタックから2つの数値を取り出す(先に処理する数値)
# トークンに対応する演算を行い、結果をスタックに追加
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
elif token == "/":
stack.append(int(a / b)) # 除算の結果を整数とする
return stack[0] # スタックの先頭に残るのが最終的な計算結果
# テスト
# RPN式の例:3 4 + 5 *
expression = ["3", "4", "+", "5", "*"]
result = evaluate_rpn(expression)
print("Result:", result) # 出力: 35
参考
Discussion