एक्सप्रेशन ट्री वे होते हैं जिनमें लीफ नोड्स के संचालन के लिए मान होते हैं, और आंतरिक नोड्स में वह ऑपरेटर होता है जिस पर लीफ नोड का प्रदर्शन किया जाएगा।
उदाहरण:4 + ((7 + 9) * 2) एक एक्सप्रेशन ट्री होगा जैसे -
इस समस्या को हल करने का तरीका
किसी दिए गए एक्सप्रेशन के लिए एक्सप्रेशन ट्री बनाने के लिए, हम आम तौर पर स्टैक डेटा स्ट्रक्चर का उपयोग करते हैं। प्रारंभ में हम दिए गए पोस्टफिक्स एक्सप्रेशन पर पुनरावृति करते हैं और नीचे दिए गए चरणों का पालन करते हैं -
- अगर हमें दिए गए एक्सप्रेशन में ऑपरेंड मिलता है, तो उसे स्टैक में पुश करें। यह अभिव्यक्ति वृक्ष का मूल बन जाएगा।
- यदि किसी ऑपरेटर को एक्सप्रेशन में दो मान मिलते हैं, तो एक्सप्रेशन ट्री को उसके बच्चे के रूप में जोड़ें, और उन्हें वर्तमान नोड में पुश करें।
- चरण-1 और चरण-2 को तब तक दोहराएं जब तक कि हम दिए गए व्यंजक को पूरा न कर लें।
उदाहरण
class stack: def __init__(self): self.arr = [] def push(self, data): self.arr.append(data) def pop(self): try: return self.arr.pop(-1) except: pass def top(self): try: return self.arr[-1] except: pass def size(self): return len(self.arr) # node class for expression tree class node: def __init__(self, data): self.data = data self.left = None self.right = None # expression tree class class exp_tree: def __init__(self, postfix_exp): self.exp = postfix_exp self.root = None self.createTree(self.exp) def isOperator(self, char): optr = [" ", "-", "*", "/", "^"] if char in optr: # if given char is operator return True # then return true return False # else return false def createTree(self, exp): s = stack() # store those operator node whose any child node is NULL self.root = node(exp[-1]) # last character of postfix expression is always an operator s.push(self.root) # travel on rest of the postfix expression for i in "".join(reversed(exp[:-1])): curr_node = s.top() if not curr_node.right: # if right node of current node is NULL temp = node(i) curr_node.right = temp if self.isOperator(i): s.push(temp) else: # if left node of current node is NULL temp = node(i) curr_node.left = temp # if no child node of current node is NULL s.pop() # pop current from stack if self.isOperator(i): s.push(temp) def inorder(self, head): # inorder traversal of expression tree # inorder traversal = > left, root, right if head.left: self.inorder(head.left) print(head.data, end=" ") if head.right: self.inorder(head.right) def infixExp(self): # inorder traversal of expression tree give infix expression self.inorder(self.root) print() if __name__ == "__main__": postfixExp = "ab ef*g*-" et = exp_tree(postfixExp) et.infixExp()
उपरोक्त कोड को चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
(a + b - e * f * g)
स्पष्टीकरण:
किसी दिए गए एक्सप्रेशन से ट्री बनाने से ऐसा आउटपुट जेनरेट होगा कि ऑपरेंड नोड का रूट बन जाएगा और बाकी नंबर एक्सप्रेशन ट्री के चाइल्ड नोड बन जाएंगे।