Python3 正規表現で逆ポーランド記法

タイトル通りです。AOJの問題を解く上で、場合分けを減らしたかったので正規表現で書いてみました。¹

python3

import re

def revPolish(f):
    f = re.sub(r'(\-?\d+\.?\d*)\s(\-?\d+\.?\d*)\s([\+\-\*/])(?!\d)',
        lambda m: str(eval(m.group(1) + m.group(3) + m.group(2))),
        f)
    if f[-1] in '+-*/':
        return revPolish(f)
    else:
        return f

if __name__=='__main__':
    print(revPolish(input()))

解説

1. 正規表現部分

(\-?\d+\.?\d*)\s(\-?\d+\.?\d*)\s([\+\-\*/])(?!\d)

簡単に言うと、「数値 数値 演算子」に一致させる表現です。

ただ負数がちょっと厄介でした。例えば以下の式があるとして、

1 2 -3 + +

1 2 -にマッチしてしまうんですよね…

これを回避するために否定先読み(?!...)を使いました。

2. 置換用関数

最初専用の関数を別に書いていたのですが、ここにしか使わないのでlambdaにしちゃいました。

正規表現を使っている段階で可読性もクソもないので、間違ったことはしていないと思います。

lambda m: str(eval(m.group(1) + m.group(3) + m.group(2)))

eval関数便利ですね。こいつがなければ結局場合分け処理になるところでした。

3. 再帰部分

上記正規表現のなすままに、計算可能な部分を計算して数値に置き換えて、それを再帰的に処理しています。

式の文字列fの最後が演算子かどうかで計算終了判定を行なっています。

最初はf内に演算子が残っているかで判断しようと思ったのですが、そうすると結果が負数だと無限ループすることに気づき、

さらに計算が全て終了すると右端の演算子が消えることに気がついた時にはもうこの形に落ち着いていました。

if f[-1] in '+-*/':

---

間違いや改善できそうな点があれば是非コメントください。

参考になれば幸いです。m(_ _)m

---

1. AOJの問題と違い実数除算/も想定していますが、0割等のエラー処理は書いてません。 ↩