特定の式の式ツリーを構築するPythonプログラム

式ツリーは、リーフノードが操作される値を持ち、内部ノードがリーフノードが実行される演算子を含むツリーです。

例：4 +（（7 + 9）* 2） -

この問題を解決するためのアプローチ

特定の式の式ツリーを構築するために、通常、スタックデータ構造を使用します。最初に、指定された接尾辞式を繰り返し処理し、以下の手順に従います-

• 指定された式でオペランドを取得した場合は、それをスタックにプッシュします。これは、式ツリーのルートになります。
• 演算子が式で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)
# node class for expression tree
class node:
   def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
# expression tree class
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: # if given char is operator
         return True # then return true
      return False # else return false
   def createTree(self, exp):
      s = stack()
      # store those operator node whose any child node is NULL
      self.root = node(exp[-1])
      # last character of postfix expression is always an operator
      s.push(self.root)
      # travel on rest of the postfix expression
      for i in "".join(reversed(exp[:-1])):
         curr_node = s.top()
         if not curr_node.right:
            # if right node of current node is NULL
            temp = node(i)
            curr_node.right = temp
            if self.isOperator(i):
               s.push(temp)
         else: # if left node of current node is NULL
            temp = node(i)
            curr_node.left = temp
            # if no child node of current node is NULL
            s.pop() # pop current from stack
            if self.isOperator(i):
               s.push(temp)
   def inorder(self, head):
      # inorder traversal of expression tree
      # inorder traversal = > left, root, right
      if head.left:
         self.inorder(head.left)
      print(head.data, end=" ")
      if head.right:
         self.inorder(head.right)
   def infixExp(self):
      # inorder traversal of expression tree give infix expression
      self.inorder(self.root)
      print()
if __name__ == "__main__":
   postfixExp = "ab ef*g*-"
   et = exp_tree(postfixExp)
   et.infixExp()

上記のコードを実行すると、次のように出力が生成されます

出力

(a + b - e * f * g)

説明：

指定された式からツリーを構築すると、オペランドがノードのルートになり、残りの数値が式ツリーの子ノードになるように出力が生成されます。