पायथन का उपयोग करके एक अभिव्यक्ति वृक्ष बनाने और उसका मूल्यांकन करने का कार्यक्रम

मान लीजिए, हमें एक व्यंजक ट्री का पोस्ट ऑर्डर ट्रैवर्सल दिया गया है। हमें दिए गए पोस्ट-ऑर्डर ट्रैवर्सल से एक एक्सप्रेशन ट्री बनाना है, और फिर एक्सप्रेशन का मूल्यांकन करना है। हम एक्सप्रेशन ट्री की जड़ और ट्री का मूल्यांकित मान लौटाते हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट -7 होगा।

पेड़ के इनपुट के रूप में दिया गया पोस्टफिक्स ऑर्डर ['1', '2', '+', '3', '4', '+', '*'] है। व्यंजक यदि मूल्यांकन किया जाता है, तो बन जाता है (1 - 2) * (3 + 4); जो -7 के बराबर है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• बाएँ =0 दाएँ =1

• फ़ंक्शन का मूल्यांकन करें () परिभाषित करें। यह जड़ लेगा

  • यदि रूट का मान एक संख्यात्मक मान है, तो

    • जड़ के मान का पूर्णांक प्रतिनिधित्व लौटाएं

  • left_val :=मूल्यांकन (रूट के बाएँ)

  • right_val :=मूल्‍यांकन करें (रूट के दाएं)

  • यदि मूल का मान ='+', तो

    • बाएँ_वल + दाएँ_वल पर लौटें

  • अन्यथा जब रूट का मान ='-', तब

    • बाएं_वल - दाएं_वल पर लौटें

  • अन्यथा जब रूट का मान ='*', तब

    • बाएं_वल * दाएं_वल पर लौटें

  • अन्यथा जब रूट का मान ='/', तब

    • (बाएं_वल / दाएं_वल)

      . का वापसी तल मान

• एक फ़ंक्शन को परिभाषित करें buildTree() । इसमें पोस्टफिक्स लगेगा

  • जड़:=शून्य

  • स्टैक :=एक नई सूची

  • जबकि पोस्टफिक्स खाली नहीं है, करें

    • 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