পাইথন ব্যবহার করে একটি এক্সপ্রেশন ট্রি তৈরি এবং মূল্যায়ন করার জন্য প্রোগ্রাম

ধরুন, আমাদেরকে একটি এক্সপ্রেশন ট্রির পোস্ট অর্ডার ট্রাভার্সাল দেওয়া হয়েছে। আমাদের প্রদত্ত পোস্ট-অর্ডার ট্রাভার্সাল থেকে একটি অভিব্যক্তি গাছ তৈরি করতে হবে এবং তারপর অভিব্যক্তিটির মূল্যায়ন করতে হবে। আমরা এক্সপ্রেশন ট্রির মূল এবং গাছের মূল্যায়ন করা মান ফিরিয়ে দিই।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে -7।

গাছের ইনপুট হিসাবে দেওয়া পোস্টফিক্স অর্ডার হল ['1', '2', '+', '3', '4', '+', '*']। অভিব্যক্তিটি যদি মূল্যায়ন করা হয়, তাহলে হয়ে যায় (1 – 2) * (3 + 4); যার সমান -7।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• বাম =0 ডান =1

• একটি ফাংশন evaluate() সংজ্ঞায়িত করুন। এটি রুট নেবে

  • যদি রুটের মান একটি সাংখ্যিক মান হয়, তাহলে

    • রুটের মানের পূর্ণসংখ্যা উপস্থাপনা

  • left_val :=মূল্যায়ন (মূলের বাম)

  • right_val :=মূল্যায়ন (মূলের ডান)

  • যদি root-এর মান ='+', তাহলে

    • বাম_ভাল + ডান_ভাল

      ফেরত দিন

  • অন্যথায় যখন root এর মান ='-', তারপর

    • বাম_ভাল - ডান_ভাল

      ফেরত দিন

  • অন্যথায় যখন root-এর মান ='*', তাহলে

    • বাম_ভাল * ডান_ভাল

      ফেরত দিন

  • অন্যথায় যখন root ='/' এর মান, তারপর

    • (left_val / right_val)

      এর রিটার্ন ফ্লোর মান

• একটি ফাংশন buildTree() সংজ্ঞায়িত করুন। এটি পোস্টফিক্স গ্রহণ করবে

  • root :=null

  • স্ট্যাক :=একটি নতুন তালিকা

  • পোস্টফিক্স খালি না থাকার সময়, করুন

    • curr :=পোস্টফিক্স থেকে শেষ উপাদান মুছুন

    • curr_node :=curr মান ধারণকারী একটি নতুন নোড

    • যদি রুট খালি থাকে, তাহলে

      • root :=curr_node

    • যদি স্ট্যাক খালি না হয়, তাহলে

      • অভিভাবক :=স্ট্যাক থেকে শেষ উপাদান মুছুন

      • পক্ষ :=পিতামাতা

      • যদি পাশ LEFT এর মত হয়, তাহলে

        • পিতামাতার বাম :=curr_node

      • অন্যথায়,

        • পিতামাতার অধিকার :=curr_node

    • যদি curr একটি সংখ্যাসূচক মান না হয়, তাহলে

      • স্ট্যাকের শেষে tuple (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