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

図の例では、二項演算子を用いた算術式を二分木で表現している。この式を逆ポーランド記法、中置記法、ポーランド記法で記述すると、それぞれ
出典: フリー百科事典『ウィキペディア(Wikipedia)』
a b + c d – × e f + ÷
(a + b) × (c – d) ÷ (e + f)
÷ × + a b – c d + e f
となり、左優先の帰りがけ順、通りがけ順、行きがけ順に相当する。強調部分は図で点線で囲った部分木である。部分木が二分木であることは、式の項もまた式であることとよく対応する。
中置記法の式が与えられたら、上のような算術式の2分木を生成するアルゴリズムを考えます。
逆ポーランド記法の式を見ると、スタックを用いることで、
式を左側から見ていって…
1.オペランドの場合はスタックに入れる
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分木を得ることができました。