Chương trình xây dựng và đánh giá một cây biểu thức bằng Python

Giả sử, chúng ta được cung cấp dịch chuyển thứ tự bài đăng của một cây biểu thức. Chúng ta phải xây dựng một cây biểu thức từ duyệt theo thứ tự sau đã cho, và sau đó đánh giá biểu thức. Chúng tôi trả về gốc của cây biểu thức và giá trị được đánh giá của cây.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là -7.

Thứ tự hậu tố được đưa ra làm đầu vào của cây là ['1', '2', '+', '3', '4', '+', '*']. Biểu thức nếu được đánh giá sẽ trở thành (1 - 2) * (3 + 4); bằng -7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• LEFT =0RIGHT =1

• Định nghĩa một hàm eval (). Điều này sẽ bắt nguồn từ gốc

  • nếu giá trị của gốc là giá trị số, thì

    • trả về biểu diễn số nguyên của giá trị gốc

  • left_val:=eval (left of root)

  • right_val:=eval (quyền của thư mục gốc)

  • nếu giá trị của root ='+' thì

    • trả về left_val + right_val

  • ngược lại khi giá trị của root ='-' thì

    • trả về left_val - right_val

  • ngược lại khi giá trị của root ='*' thì

    • trả về left_val * right_val

  • ngược lại khi giá trị của root ='/' thì

    • trả về giá trị sàn của (left_val / right_val)

• Định nghĩa một hàm buildTree (). Điều này sẽ có hậu tố

  • root:=null

  • stack:=một danh sách mới

  • trong khi postfix không trống, hãy thực hiện

    • curr:=xóa phần tử cuối cùng khỏi postfix

    • curr_node:=một nút mới chứa giá trị curr

    • nếu gốc trống, thì

      • root:=curr_node

    • nếu ngăn xếp không trống, thì

      • cha:=xóa phần tử cuối cùng khỏi ngăn xếp

      • bên:=cha mẹ

      • nếu bên giống với bên trái thì

        • bên trái của cha mẹ:=curr_node

      • nếu không,

        • quyền của cha mẹ:=curr_node

    • nếu curr không phải là một giá trị số thì

      • chèn tuple (curr_node, LEFT) vào cuối ngăn xếp

      • chèn tuple (curr_node, RIGHT) vào cuối ngăn xếp

• trả về thư mục gốc

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

-7