এই সমস্যায়, আমাদেরকে একটি এক্সপ্রেশন ট্রি দেওয়া হয়েছে যা +, - , /, * এর মতো বাইনারি অপারেশন নিয়ে গঠিত। আমাদের এক্সপ্রেশন ট্রিটির মূল্যায়ন করতে হবে এবং তারপর ফলাফলটি ফেরত দিতে হবে।
এক্সপ্রেশন ট্রি একটি বিশেষ ধরনের বাইনারি ট্রি যার প্রতিটি নোড হয় একটি অপারেটর বা অপারেন্ড নিয়ে গঠিত যা-
হিসাবে বিতরণ করা হয়- গাছের লিফ নোড হল সেই মান যার উপর অপারেশন করা হয়।
- নন-লিফ নোডগুলি বাইনারি অপারেটর নিয়ে গঠিত সম্পাদিত অপারেশন নির্দেশ করে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট:
আউটপুট: 1
ব্যাখ্যা:
এক্সপ্রেশন ট্রি ডিকোডিং,
মেয়াদ =( (5+9) / (2*7))
=( 14 / 14 )
=1
সমাধান পদ্ধতি:
সমস্যার একটি সহজ সমাধান হল রুট থেকে প্রতিটি অপারেশন করে, অপারেন্ডের জন্য আমরা সাবট্রি সমাধান করব। যেহেতু সমস্ত ক্রিয়াকলাপ বাইনারি হয় একটি গাছের নোডগুলির হয় দুটি সন্তান থাকে বা একটিও নেই৷
আমরা প্রতিটি নোডের বাইনারি অপারেশন সমাধান করতে পুনরাবৃত্তি ব্যবহার করব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class node {
public:
string value;
node *left = NULL, *right = NULL;
node(string x)
{
value = x;
}
};
int solveExpressionTree(node* root) {
if (!root)
return 0;
if (!root->left && !root->right)
return stoi(root->value);
int leftSubTreeSol = solveExpressionTree(root->left);
int rightSubTreeSol = solveExpressionTree(root->right);
if (root->value == "+")
return leftSubTreeSol + rightSubTreeSol;
if (root->value == "-")
return leftSubTreeSol - rightSubTreeSol;
if (root->value == "*")
return leftSubTreeSol * rightSubTreeSol;
if (root -> value == "/")
return leftSubTreeSol / rightSubTreeSol;
return -1;
}
int main()
{
node *root = new node("/");
root->left = new node("+");
root->left->left = new node("9");
root->left->right = new node("5");
root->right = new node("*");
root->right->left = new node("2");
root->right->right = new node("7");
cout<<"The evaluation of expression tree is "<<solveExpressionTree(root);
return 0;
} আউটপুট −
The evaluation of expression tree is 1
