Zenn
👻

【Python】逆ポーランド記法

2023/08/11に公開
Python
アルゴリズム
逆ポーランド記法
tech

作るもの

逆ポーランド記法（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

参考

https://www.algoexpert.io

Discussion