โปรแกรมสร้างและประเมินแผนผังนิพจน์โดยใช้ Python

สมมติว่าเราได้รับการส่งผ่านคำสั่งผ่านรายการของแผนผังนิพจน์ เราต้องสร้างแผนผังนิพจน์จากการข้ามผ่านหลังลำดับที่กำหนด จากนั้นจึงประเมินนิพจน์ เราคืนค่ารูทของแผนผังนิพจน์และค่าที่ประเมินของทรี

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น -7

ลำดับ postfix ที่กำหนดเป็นอินพุตของทรีคือ ['1', '2', '+', '3', '4', '+', '*'] นิพจน์หากประเมิน จะกลายเป็น (1 – 2) * (3 + 4); ซึ่งเท่ากับ -7

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• LEFT =0RIGHT =1

• กำหนดฟังก์ชั่นasses() สิ่งนี้จะหยั่งราก

  • ถ้าค่าของรูทเป็นค่าตัวเลขแล้ว

    • คืนค่าการแสดงจำนวนเต็มของค่ารูท

  • left_val :=ประเมิน (ซ้ายของรูท)

  • right_val :=ประเมิน (ทางขวาของรูท)

  • ถ้าค่าของ root ='+' แล้ว

    • กลับ left_val + right_val

  • มิฉะนั้น เมื่อค่าของ root ='-' แล้ว

    • กลับ left_val - right_val

  • มิฉะนั้น เมื่อค่าของ root ='*' แล้ว

    • กลับ left_val * right_val

  • มิฉะนั้น เมื่อค่าของ root ='/' แล้ว

    • ส่งคืนค่าพื้นของ (left_val / right_val)

• กำหนดฟังก์ชัน buildTree() การดำเนินการนี้จะใช้เวลาแก้ไข

  • รูท :=null

  • stack :=รายการใหม่

  • ในขณะที่ postfix ไม่ว่างเปล่าให้ทำ

    • curr :=ลบองค์ประกอบสุดท้ายออกจาก postfix

    • curr_node :=โหนดใหม่ที่มีค่า curr

    • ถ้ารูทว่างก็

      • รูท :=curr_node

    • ถ้าสแต็กไม่ว่างเปล่า

      • parent :=ลบองค์ประกอบสุดท้ายออกจาก stack

      • side :=parent

      • ถ้าด้านเดียวกับ LEFT แล้ว

        • ด้านซ้ายของพาเรนต์ :=curr_node

      • มิฉะนั้น

        • ด้านขวาของพาเรนต์ :=curr_node

    • ถ้าค่าเงินไม่ใช่ค่าตัวเลขแล้ว

      • แทรก tuple (curr_node, LEFT) ที่ส่วนท้ายของ stack

      • แทรก 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