Zenn
🍩

入力した数式をPythonで逆ポーランド記法にして解く

に公開
Python
tech

サマリ

数式を入力して逆ポーランド記法にする過程をpythonで実装して、見える様にします。

マシンスペック

MacBook Air M2 arm64

逆ポーランド記法

プログラムで演算する際の記法の一種です。演算子を数字（非演算子）の列の後に記載する方法です。
今回はこれをpythonで可視化して実際に演算まで行います。
例えば1+1という演算は11+という記法に変わります。
これは人間にとってものすごく解りづらいのですが、コンピュータにとっては都合の良い記法になります。
コンピュータは、スタックを利用したアルゴリズムを採用しており、前から順番にスタックに積んでいき、数字の場合は連続して積み上げ、演算子の場合は必要な数字をスタックから取り出し演算、その後スタックに積み演算子がなくなるまで行います。
1*2+3*4の逆ポーランド記法は1 2 * 3 4 * +となります。
これをスタック[]に積んで擬似的に人間である私が演算をすると

手順 スタックの中身 未処理トークン列 操作・説明
1 [] 1 2 * 3 4 * + 初期状態
2 [1] 2 * 3 4 * + 1 を push
3 [1 2] * 3 4 * + 2 を push
4 [2] 3 4 * + * の演算子 → 1 × 2 を計算し 2 を push
5 [2 3] 4 * + 3 を push
6 [2 3 4] * + 4 を push
7 [2 12] + * の演算子 → 3 × 4 = 12 を push
8 [14] （空） + の演算子 → 2 ＋ 12 = 14 を push
9 14 （終了） 最後に残った値の 14 を pop

結果は14となります。

このアルゴリズムをPythonで動かしてみます。

サンプルコード

import operator, re

OPS = {
    '+': (1, operator.add),
    '-': (1, operator.sub),
    '*': (2, operator.mul),
    '/': (2, operator.truediv),
}

token_pat = re.compile(r'\d+|[+\-*/()]')

def infix_to_rpn(expr: str) -> str:
    out, op_stack = [], []
    for tok in token_pat.findall(expr.replace(' ', '')):
        if tok.isdigit():
            out.append(tok)
        elif tok in OPS:
            prec, _ = OPS[tok]
            while op_stack and op_stack[-1] in OPS and OPS[op_stack[-1]][0] >= prec:
                out.append(op_stack.pop())
            op_stack.append(tok)
        elif tok == '(':
            op_stack.append(tok)
        elif tok == ')':
            while op_stack and op_stack[-1] != '(':
                out.append(op_stack.pop())
            if not op_stack or op_stack.pop() != '(':
                raise ValueError("mismatched parentheses")
    out.extend(reversed(op_stack))
    return ' '.join(out)

def eval_rpn(rpn: str) -> float:
    stack = []
    for tok in rpn.split():
        if tok in OPS:
            if len(stack) < 2:
                raise ValueError("underflow")
            b, a = stack.pop(), stack.pop()
            stack.append(OPS[tok][1](a, b))
        else:
            stack.append(float(tok))
    if len(stack) != 1:
        raise ValueError("ill-formed RPN")
    return stack[0]

if __name__ == "__main__":
    print("数式を入力してください：")
    expr = input()
    rpn  = infix_to_rpn(expr)
    val  = eval_rpn(rpn)
    print(f"数式: {expr}\n  逆ポーランド記法: {rpn}\n  = {val}")

こちらを実行すると、下記のように任意の数式を入力してEnterを押して逆ポーランド記法、演算を行います。

数式を入力してください：
1*2+3*4
数式: 1*2+3*4
  逆ポーランド記法: 1 2 * 3 4 * +
  = 14.0

期待した結果が出せました。

まとめ

逆ポーランド記法を紐解いて、コンピュータ側の計算アルゴリズムに寄り添いました。

Discussion