সি++-এ এক্সপ্রেশন ট্রি মূল্যায়ন

এই সমস্যায় আমাদের একটি এক্সপ্রেশন ট্রি দেওয়া হয়েছে যাতে বাইনারি অপারেশন যেমন +, -, /, * রয়েছে। আমাদের এক্সপ্রেশন ট্রিটি মূল্যায়ন করে ফলাফল ফেরত দিতে হবে।

এক্সপ্রেশন ট্রি কী?

এক্সপ্রেশন ট্রি হলো একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে প্রতিটি নোড অপারেটর বা অপারেন্ড ধারণ করে, যেগুলো নিম্নরূপ বিতরণ করা হয়:

• ট্রির ليف নোডগুলো হলো মান যেখানে অপারেশন انجام করা হবে।
• নন-ليف নোডগুলো বাইনারি অপারেটর ধারণ করে যা কোন অপারেশন করা হবে তা নির্দেশ করে।

উদাহরণ দিয়ে বুঝি

ইনপুট:

আউটপুট: ১

ব্যাখ্যা:

এক্সপ্রেশন ট্রিটি ডিকোড করলে,

Exp = ((৫ + ৯) / (২ × ৭))
        = (১৪ / ১৪)
        = ১

সমাধানের পদ্ধতি

এই সমস্যার একটি সহজ সমাধান হলো রুট থেকে প্রতিটি অপারেশন সম্পাদন করা, অপারেন্ডের জন্য সাবট্রি সমাধান করা। যেহেতু সব অপারেশন বাইনারি, ট্রির নোডগুলোতে হয় দুটি চাইল্ড থাকে বা কোনো চাইল্ড থাকে না।

আমরা রিকার্শন ব্যবহার করে প্রতিটি নোডের বাইনারি অপারেশন সমাধান করব।

সমাধান minhaj করার প্রোগ্রাম

#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