[Python] 算術式の2分木表現/ Expression Tree

算術式の2分木表現

2分木を用いることで、式を表現することができます。

図の例では、二項演算子を用いた算術式を二分木で表現している。この式を逆ポーランド記法、中置記法、ポーランド記法で記述すると、それぞれ
a b + c d – × e f + ÷
(a + b) × (c – d) ÷ (e + f)
÷ × + a b – c d + e f
となり、左優先の帰りがけ順、通りがけ順、行きがけ順に相当する。強調部分は図で点線で囲った部分木である。部分木が二分木であることは、式の項もまた式であることとよく対応する。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

中置記法の式が与えられたら、上のような算術式の2分木を生成するアルゴリズムを考えます。

逆ポーランド記法の式を見ると、スタックを用いることで、

式を左側から見ていって…

１．オペランドの場合はスタックに入れる

２．演算子の場合は、スタックから2つオペランドを取り出して、部分木を作り、スタックに入れる

というアルゴリズムで、自然に2分木が生成できそうです。

中置記法から逆ポーランド記法への変換は、下記で記載したアルゴリズムを用います。

Pythonで上のアルゴリズムをコードにします。

operator_precedence = {
    '(' : 0,
    ')' : 0,
    '+' : 1,
    '-' : 1,
    '*' : 2,
    '/' : 2
}
 
def infix_to_postfix(infix):
    stack = []
    postfix = [] 
         
    for char in infix.split():
        if char not in operator_precedence:
            postfix.append(char)
        else:
            if len(stack) == 0:
                stack.append(char)
            else:
                if char == "(":
                    stack.append(char)
                elif char == ")":
                    while stack[len(stack) - 1] != "(":
                        postfix.append(stack.pop())
                    stack.pop()
                elif operator_precedence[char] > operator_precedence[stack[len(stack) - 1]]:
                    stack.append(char)
                else:
                    while len(stack) != 0:
                        if stack[len(stack) - 1] == '(':
                            break
                        postfix.append(stack.pop())
                    stack.append(char)
     
    while len(stack) != 0:
        postfix.append(stack.pop())
 
    return postfix


class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
 
class ExressionTree(object):
    def __init__(self, root=None):
        self.root = root
     
    def postorder(self):
        self._postorder(self.root)
         
    def _postorder(self, node):
        if node:
            self._postorder(node.left)
            self._postorder(node.right)
            print(node.value)
 
def build_expression_tree(infix):
    postfix = infix_to_postfix(infix)
 
    stack = []
 
    for char in postfix:
        if char not in operator_precedence:
            node = Node(char)   
            stack.append(node)
        else:
            node = Node(char)
            right = stack.pop()
            left = stack.pop()
            node.right = right
            node.left = left
            stack.append(node)
     
    return ExressionTree(stack.pop())

infix = '( A + B ) * ( C - D ) / ( E + F )'
# ['A', 'B', '+', 'C', 'D', '-', '*', 'E', 'F', '+', '/']
print(infix_to_postfix(infix))
build_expression_tree('( A + B ) * ( C - D ) / ( E + F )').postorder()
# A
# B
# +
# C
# D
# -
# *
# E
# F
# +
# /

想定通りの2分木を得ることができました。