Expression trees वे होते हैं जिनमें leaf nodes में operate किए जाने वाले values होते हैं, और internal nodes में operator होता है जिस पर leaf node perform किया जाएगा।
उदाहरण: 4 + ((7 + 9) * 2) का expression tree ऐसा होगा -
Problem हल करने का दृष्टिकोण
दिए गए expression के लिए Expression Tree construct करने के लिए, हम generally Stack Data Structure का उपयोग करते हैं। Initially हम दिए गए postfix expression पर iterate करते हैं और नीचे दिए गए steps का पालन करते हैं:
- यदि हमें दिए गए expression में operand मिलता है, तो उसे stack में push करें। यह expression Tree का root बनेगा।
- यदि operator को expression में दो values मिलते हैं, तो उन्हें expression tree में child के रूप में add करें, और current node में push करें।
- Step-1 और Step-2 को तब तक repeat करें जब तक हम अपने दिए गए expression पर complete नहीं कर लेते।
उदाहरण
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()
उपरोक्त code चलाने से output generate होगा:
आउटपुट
(a + b - e * f * g)
व्याख्या:
दिए गए expression से tree construct करने से output generate होगा जैसे कि operand node का root बनेगा और बाकी numbers expression tree के child nodes बनेंगे।
