মান লাগিয়ে, আমাদের একটি এক্সপ্রেশন ট্রির পোস্ট-অর্ডার ট্রাভার্সাল দেওয়া আছে। আমাদের দেওয়া পোস্ট-অর্ডার ট্রাভার্সাল থেকে এক্সপ্রেশন ট্রি বানাতে হবে, এবং তারপর এক্সপ্রেশনটি ইভ্যালুয়েট করতে হবে। আমরা এক্সপ্রেশন ট্রির রুট এবং ট্রির ইভ্যালুয়েটেড মান রিটার্ন করব।
যেমন, ইনপুট যদি এমন হয়:
তবে আউটপুট হবে -7।
ইনপুট হিসেবে দেওয়া ট্রির পোস্টফিক্স অর্ডার হল ['1', '2', '+', '3', '4', '+', '*']। এক্সপ্রেশনটি ইভ্যালুয়েট করলে হয় (1 - 2) * (3 + 4); যা সমান -7।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- LEFT = 0, RIGHT = 1
- একটি ফাংশন evaluate() ডিফাইন করুন। এটি root নেবে:
- যদি root.val न्यুমেরিক ভ্যালু হয়, তবে root.val-এর ইন্টিজার রিপ্রেজেন্টেশন রিটার্ন করুন
- left_val := evaluate(root.left)
- right_val := evaluate(root.right)
- যদি root.val == '+' হয়, তবে left_val + right_val রিটার্ন করুন
- অন্যথায় যদি root.val == '-' হয়, তবে left_val - right_val রিটার্ন করুন
- অন্যথায় যদি root.val == '*' হয়, তবে left_val * right_val রিটার্ন করুন
- অন্যথায় যদি root.val == '/' হয়, তবে (left_val / right_val) এর ফ্লোর ভ্যালু রিটার্ন করুন
- একটি ফাংশন buildTree() ডিফাইন করুন। এটি postfix নেবে:
- root := null
- stack := একটি নতুন লিস্ট
- postfix খালি না হওয়া পর্যন্ত:
- curr := postfix-এর শেষ এলিমেন্ট ডিলিট করুন
- curr_node := curr মান ধারণকারী একটি নতুন নোড
- যদি root খালি হয়, তবে root := curr_node
- যদি stack খালি না হয়, তবে:
- parent := stack-এর শেষ এলিমেন্ট ডিলিট করুন
- side := parent
- যদি side == LEFT হয়, তবে parent.left := curr_node
- অন্যথায়, parent.right := curr_node
- যদি curr न्यুমেরিক্যাল ভ্যালু না হয়, তবে:
- (curr_node, LEFT) stack-এ যোগ করুন
- (curr_node, RIGHT) stack-এ যোগ করুন
- root রিটার্ন করুন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
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
