Python で逆ポーランド記法の計算

逆ポーランド記法 – Wikipedia とは、

たとえば、

1 + 2

（1 に 2 を足す）は

1 2 +

と書く。

この記法を計算機等の入力に採用した場合かっこ操作が必要なくなる。 例えば (1 + 2) × (3 + 4) を計算する場合、数式をそのまま入力する方式の計算機ではこれら全ての記号を入力する必要があるが、逆ポーランド記法を採用した場合は 1 2 + 3 4 + * と入力すればよい

 

仕様

逆ポーランド記法を文字列で入力した場合に計算結果と、中置記法 で表示されるようにしたい。

 

実装

ReversePolishNotation.py

import types, math

# 四則演算子
def add(a,b): return a + b
def sub(a,b): return a - b
def mul(a,b): return a * b
def div(a,b): return a/ float(b)

OPERATORS = {add:'+', sub:'-', mul:'*', div:'/'}
# OPERATORS の逆の対応付け
OPR2FUNCS = dict((v,k) for k,v in OPERATORS.iteritems())

# ---------------------------------------------------------------------------
# 逆ポーランド記法の計算

def calcList(L):
    """ 逆ポーランド記法を表すリストから計算をした結果を返す

    L : 数値と演算子の関数のリスト。
        ex. [3, 8, 2, add, mul, 4, add, 5, sub]
    """
    S = []
    try:
        for e in L:
           if isinstance(e, types.FunctionType):
               # 関数の場合はスタックの末尾から二つ要素を取り出し、
               # 関数を適用。結果をスタックに追加
               S.append(e(S.pop(-2), S.pop(-1)))
           else:
               S.append(e)
               
        # 最終的にスタックに値が一つでなければ不適切な式だったとしてエラーとする
        if not len(S) == 1: raise InvalidExpressionError
        return S[0]
    except:
        raise InvalidExpressionError

class InvalidExpressionError(Exception):
    pass

# ---------------------------------------------------------------------------
# 逆ポーランド記法を中置記法へ変換

def cnvExpList(L):
    """ 逆ポーランド記法を表わしたリストを、二項演算ごとにネストしたリストに変換

    ex. [3, 8, 2, add, mul, 4, add, 5, sub]
        → [[[3, [8, 2, add], mul], 4, add], 5, sub]
    """
    i = 0
    while i < (len(L)-2):
        if type(L[i])   in [int, float, list] and \
           type(L[i+1]) in [int, float, list] and \
           type(L[i+2]) is types.FunctionType:
               L.insert(i, [L.pop(i),L.pop(i),L.pop(i)])
               if len(L) == 1 : break
               else : i = 0; continue
        i += 1
        
    # 式が妥当であればリストの要素は 1 になる。
    if not len(L) == 1 or not isinstance(L[0], list):
        raise InvalidExpressionError
    # 一番外側の括弧をはずす
    return reduce(lambda a,b: a+b, L, [])

def cnvExp(L):
    """ 二項演算ごとにネストしたリストを式の文字列に変換

    ex. [[[3, [8, 2, add], mul], 4, add], 5, sub]
        → (((3*(8+2))+4)-5)
    """
    if isinstance(L, list):
        return '(' + cnvExp(L[0]) + OPERATORS[L[2]] + cnvExp(L[1]) + ')'
    else:
        return str(L)

def delOuterBrackets(L):
    """ 式の一番外側の括弧を削除

    ex. (((3*(8+2))+4)-5) → ((3*(8+2))+4)-5
    """
    import re
    return re.sub(r'^\((.+)\)$', r'\1', L)

# ---------------------------------------------------------------------------
# 逆ポーランド記法の文字列をリストへ変換

def conv2List(rpn):
    """ 逆ポーランド記法で書かれた文字列をリストに変換

    ただし、整数にできるものは整数に変換。演算子は関数に変換。
    ex. "3 8 2 + * 4 + 5 -"
        → [3, 8, 2, add, mul, 4, add, 5, sub]
    """
    return [(int(math.modf(float(x))[1])
                if math.modf(float(x))[0] == 0 else float(x))
            if x not in ['+','-','*','/'] else OPR2FUNCS[x]
            for x in rpn.split()]

# ---------------------------------------------------------------------------

def infixNotation(rpn):
    """ 中置記法に変換 """
    # リストをコピー
    cloneL = reduce(lambda a,b: a+[b], conv2List(rpn), [])
    return delOuterBrackets(cnvExp(cnvExpList(cloneL)))

def calc(s):
    """ 計算した結果を返す """
    return calcList(conv2List(s))
    
if __name__ == "__main__":
    rpn = "30 80 2 + * 4 + 5 -"
    print infixNotation(rpn), '=', calc(rpn)

 

中置記法への変換について

逆ポーランド記法から中置記法に変換するとき、リストを演算ごとにネストすることにより演算のツリーを表現している。

例えば、次のようにリストの先頭から演算部分を探し、リストをネスト化。適正な逆ポーランド記法であれば、要素が一つのリストに変換される。( return するときに一番外側の括弧は外しているけれど。)

 

上記から中置記法に変換するとき、cnvExp で再帰的に関数を適用している。(cf. Python でリストに対する再帰的な関数の適用) cnvExpList では再帰を使っていないが、これを再帰で表現するとしたらどうなるのだろうか ？ (+_+) あ～、よくわらない。

ちなみに、式として適正でないと cnvExp 関数の結果、要素が一つ以上のリストになるので、これをもって逆ポーランド記法の適切さを判別している。