Pythonを使用して式ツリーを構築および評価するプログラム

式ツリーのポストオーダートラバーサルが与えられたとします。与えられたポストオーダートラバーサルから式ツリーを構築してから、式を評価する必要があります。式ツリーのルートとツリーの評価値を返します。

したがって、入力が次のような場合

その場合、出力は-7になります。

ツリーの入力として指定された接尾辞の順序は、['1'、 '2'、'+'、 '3'、 '4'、'+'、'*']です。評価すると、式は（1 – 2）*（3 + 4）;になります。これは-7に相当します。

これを解決するには、次の手順に従います-

• 左=0右=1

• 関数evaluate（）を定義します。これが定着します

  • ルートの値が数値の場合、

    • ルートの値の整数表現を返す

  • left_val：=評価（ルートの左側）

  • right_val：=評価（ルートの権利）

  • ルートの値='+'の場合、

    • left_val + right_val

      を返します

  • それ以外の場合、ルートの値='-'の場合、

    • left_val --right_val

      を返します

  • それ以外の場合、ルートの値='*'の場合、

    • left_val * right_val

      を返します

  • それ以外の場合、ルートの値='/'の場合、

    • （left_val / right_val）のフロア値を返す

• 関数buildTree（）を定義します。これには後置が必要です

  • ルート：=null

  • スタック：=新しいリスト

  • 接尾辞が空ではない場合は、実行してください

    • curr：=接尾辞から最後の要素を削除する

    • curr_node：=値currを含む新しいノード

    • ルートが空の場合、

      • ルート：=curr_node

    • スタックが空でない場合は、

      • 親：=スタックから最後の要素を削除

      • サイド：=親

      • サイドがLEFTと同じ場合、

        • 親の左側：=curr_node

      • それ以外の場合

        • 親の権利：=curr_node

    • currが数値でない場合は、

      • スタックの最後にタプル（curr_node、LEFT）を挿入します

      • スタックの最後にtuple（curr_node、RIGHT）を挿入します

• ルートを返す

理解を深めるために、次の実装を見てみましょう-

例

LEFT = 0
RIGHT = 1
class Node():
def __init__(root, val, left = None, right = None):
   root.val = val
   root.left = left
   root.right = right
def evaluate(root):
   if(root.val.isnumeric()):
      return int(root.val)
      left_val = evaluate(root.left)
      right_val = evaluate(root.right)
      return (
         ( root.val == '+' and left_val + right_val ) or
         ( root.val == '-' and left_val - right_val ) or
         ( root.val == '*' and left_val * right_val ) or
         ( root.val == '/' and left_val // right_val )
      )
def buildTree(postfix):
   root = None
   stack = []
   while(postfix):
      curr = postfix.pop()
      curr_node = Node(curr)
      if(not root):
         root = curr_node
      if(stack):
         parent, side = stack.pop()
      if(side == LEFT):
         parent.left = curr_node
      else:
         parent.right = curr_node
      if(not curr.isnumeric()):
         stack.append((curr_node, LEFT))
         stack.append((curr_node, RIGHT))
   return root
root = buildTree(['1', '2', '+', '3', '4', '+', '*'])
print(evaluate(root))

入力

['1', '2', '+', '3', '4', '+', '*']

出力

-7