এক্সপ্রেশন ট্রি
এক্সপ্রেশন ট্রি হল সেই ট্রি যেগুলোর লিফ নোডে অপারেট করা ভ্যালু থাকে, এবং ইন্টারনাল নোডে অপারেটর থাকে যার ওপর লিফ নোড অপারেট করা হবে।
উদাহরণ
4 + ((7 + 9) * 2)-এর এক্সপ্রেশন ট্রি নিচের মতো হবে
এক্সপ্রেশন ট্রি কনস্ট্রাক্ট করার অ্যালগরিদম
T হল এক্সপ্রেশন ট্রি।
If T is not NULL:
If T->data is an operand:
return T.data
A = solve(T.left)
B = solve(T.right)
--> Calculate operator for 'T.data' on A and B, and call recursively,
return calculate(A, B, T.data)
এক্সপ্রেশন ট্রি কীভাবে কনস্ট্রাক্ট করবেন?
প্রদত্ত এক্সপ্রেশনের জন্য এক্সপ্রেশন ট্রি কনস্ট্রাক্ট করার জন্য, আমরা সাধারণত স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করি।
প্রথমে আমরা প্রদত্ত পোস্টফিক্স এক্সপ্রেশন ইটারেট করি এবং নিচের ধাপগুলো অনুসরণ করি -
- যদি প্রদত্ত এক্সপ্রেশনে একটি অপারেন্ড পাই, তবে সেটি স্টকে পুশ করুন। এটি এক্সপ্রেশন ট্রির রুট হবে।
- যদি এক্সপ্রেশনে একটি অপারেটর দুটি ভ্যালু পায়, তবে সেটি এক্সপ্রেশন ট্রিতে এর চাইল্ড হিসেবে যোগ করুন, এবং বর্তমান নোডে পুশ করুন।
- ধাপ-১ এবং ধাপ-২ পুনরাবৃত্তি করুন যতক্ষণ না প্রদত্ত এক্সপ্রেশন সম্পূর্ণ হয়।
- এখন চেক করুন যে প্রতিটি রুট নোডে শুধু অপারেন্ড আছে এবং প্রতিটি চাইল্ড নোডে শুধু ভ্যালু আছে।
