Stackを使って、中間置記法から後置記法に変換する。

半年ほど前に神保町の古本市でゲットした、コンパイラの本を読みました。

作者: 中田育男
出版社/メーカー: 産業図書
発売日: 1981/01/01
メディア: 単行本
クリック: 4回
この商品を含むブログ (4件) を見る

自分はもともとコンピュータサイエンスの人間ではなくて、研究で計算機を使っていたのですが、仕事でやってると、もう少し深く原理を知って足腰を鍛えたいなという気持ちが湧いてきたので、ざっと読んでみました。
コンパイラの働きについて基本的なことを俯瞰できたんですが、特に構文解析として中間置記法から後置記法に変換する話がすごく面白いなと思ったので、pythonで簡単な変換器を作ってみました。

機能

ざっくりいうと、式を中間置記法から後置記法に変換します。
例えば、(((3 + 4) * 5) - 6)のような式を与えると、あらかじめ決めておいた演算子の優先順位をもとに3 4 + 5 * 6 -に直してくれます。

中間記法の式を左から読んでいって、
・演算数はそのまま出力
・演算子はスタックに自分より強い演算子が積んであったらその分だけpopしてから積む。
　　　　　　　※上記の書籍のP.13に同様のアルゴリズムが解説されている。

コード

# --- coding: utf-8 ---

class Notation_changer:
    """this class changes notation, infix Notation to Postfix Notation"""

    stack = []
    group1 = ("(", ")")
    group2 = ("+", "-")
    group3 = ("*", "/")

    def _init_(self):
        self.formula =  ""

    def is_not_operator(self, item):
        return item not in ("+", "-", "*", "/", "(", ")")

    def is_weaker_or_equal_operator(self, operator, stacked_operator):
        if self.check_operator_order(operator) < self.check_operator_order(stacked_operator):
            return False
        else:
            return True

    def check_operator_order(self, operator):
        operator_order = 1
        if operator in self.group1:
            operator_order = 1 
        if operator in self.group2:
            operator_order = 2 
        if operator in self.group3:
            operator_order = 3 
        return operator_order

    def setFormula(self, formula):
        self.formula = formula

    def change_notation(self):
        for i in range(len(self.formula)):
            if self.formula[i] == " ":
                continue
        
            if self.is_not_operator(self.formula[i]):
                print(self.formula[i])
                continue 

            if len(self.stack) == 0:
                self.stack.append( self.formula[i] )
                continue            
    
            for j in range(len(self.stack))[::-1]:
                if self.is_weaker_or_equal_operator( self.formula[i] , self.stack[j] ):
                    self.stack.append( self.formula[i] )
                    break
                else:
                    print(self.stack.pop())


if __name__ == "__main__":
    s = "(((3 + 4) * 5) - 6)"

    notation_changer = Notation_changer()

    notation_changer.setFormula(s)
    notation_changer.change_notation()