Pythonで式ツリー（式木）を構築する方法：後置記法の式から式木を作るプログラム

式ツリー（Expression Tree）とは、二分木の一種で、葉ノードには演算の対象となる値（オペランド）が格納され、内部ノードには演算子が格納されるデータ構造です。

例：「4 + ((7 + 9) * 2)」という式は、次のような式ツリーで表現できます。

問題を解くためのアプローチ

与えられた式から式ツリーを構築する際には、一般的にスタックというデータ構造を使用します。まず、与えられた後置記法（ポストフィックス記法）の式を走査しながら、以下の手順を実行していきます。

• 式の中にオペランドが現れた場合は、それをノードとして作成し、スタックにプッシュします。
• 演算子が現れた場合は、その演算子をノードとして作成し、スタック上の既存ノードの子として接続します。さらに、その演算子ノード自身もスタックにプッシュします。
• 式全体の処理が完了するまで、手順1と手順2を繰り返します。

本記事の実装では、後置記法の式を右から左へ走査している点がポイントです。後置記法の最後の文字は必ず演算子になるため、それをルートノードとし、残りの文字を逆順に処理しながら「右の子 → 左の子」の順でノードを割り当てていきます。

コード例

class stack:
   def __init__(self):
      self.arr = []
   def push(self, data):
      self.arr.append(data)
   def pop(self):
      try:
         return self.arr.pop(-1)
      except:
         pass
   def top(self):
      try:
         return self.arr[-1]
      except:
         pass
   def size(self):
      return len(self.arr)
# 式ツリー用のノードクラス
class node:
   def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
# 式ツリークラス
class exp_tree:
   def __init__(self, postfix_exp):
      self.exp = postfix_exp
      self.root = None
      self.createTree(self.exp)
   def isOperator(self, char):
      optr = [" ", "-", "*", "/", "^"]
      if char in optr: # 演算子の場合
         return True # True を返す
      return False # それ以外は False を返す
   def createTree(self, exp):
      s = stack()
      # 子ノードが未設定の演算子ノードを管理するためのスタック
      self.root = node(exp[-1])
      # 後置記法の最後の文字は必ず演算子
      s.push(self.root)
      # 残りの後置記法の式を走査
      for i in "".join(reversed(exp[:-1])):
         curr_node = s.top()
         if not curr_node.right:
            # 現在のノードの右の子が未設定の場合
            temp = node(i)
            curr_node.right = temp
            if self.isOperator(i):
               s.push(temp)
         else: # 左の子が未設定の場合
            temp = node(i)
            curr_node.left = temp
            # 現在のノードの子がすべて埋まったのでスタックから取り除く
            s.pop()
            if self.isOperator(i):
               s.push(temp)
   def inorder(self, head):
      # 式ツリーの中順走査
      # 中順走査 => 左、ルート、右
      if head.left:
         self.inorder(head.left)
      print(head.data, end=" ")
      if head.right:
         self.inorder(head.right)
   def infixExp(self):
      # 中順走査の結果として中置記法の式が出力される
      self.inorder(self.root)
      print()
if __name__ == "__main__":
   postfixExp = "ab ef*g*"
   et = exp_tree(postfixExp)
   et.infixExp()

上記のコードを実行すると、次の出力が得られます。

出力

(a + b - e * f * g)

解説：

与えられた後置記法の式からツリーを構築すると、演算子が内部ノード（ルート）となり、オペランドが葉ノードとして配置された式ツリーが完成します。このツリーに対して中順走査（Inorder Traversal）——「左の子 → ルート → 右の子」の順でノードを訪問する手法——を適用することで、元の中置記法の式である「(a + b - e * f * g)」が復元されます。このように、スタックと木構造を組み合わせることで、数式の解析や評価を効率的に行うことができます。