पोस्टफिक्स एक्सप्रेशन से स्टैक-आधारित एल्गोरिदम से एक्सप्रेशन ट्री बनाएं और रिकर्सिवली मूल्यांकन करें।
एल्गोरिदम
buildTree(postfix): स्टैक में (नोड, साइड) टपल्स रखें। पोस्टफिक्स से पॉप करके ट्री बनाएं।evaluate(root): अगर नोड न्यूमेरिक तो वैल्यू रिटर्न। वरना लेफ्ट/राइट रिकर्सिवली मूल्यांकन करके ऑपरेटर अप्लाई करें।
उदाहरण कोड
LEFT, RIGHT = 0, 1
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def evaluate(root):
if root.val.isnumeric():
return int(root.val)
left_val = evaluate(root.left)
right_val = evaluate(root.right)
if root.val == '+': return left_val + right_val
if root.val == '-': return left_val - right_val
if root.val == '*': return left_val * right_val
if root.val == '/': return 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
# टेस्ट: ['1','2','+','3','4','+','*'] -> (1+2)*(3+4) = 3*7 = 21?
# नोट: उदाहरण में '-' ऑपरेटर है लेकिन पोस्टफिक्स में '+' दो बार।
# सही: ['1','2','-','3','4','+','*'] -> (1-2)*(3+4) = -7
इनपुट/आउटपुट
इनपुट: ['1','2','+','3','4','+','*'] (नोट: उदाहरण आउटपुट -7 के लिए '-' होना चाहिए)
आउटपुट: -7 (यदि एक्सप्रेशन (1-2)*(3+4) है)
