इस समस्या में, हमें एक एक्सप्रेशन ट्री दिया गया है जिसमें +, -, /, * जैसे बाइनरी ऑपरेशन होते हैं। हमें इस एक्सप्रेशन ट्री का मूल्यांकन करके परिणाम वापस करना होता है।
एक्सप्रेशन ट्री क्या है?
एक्सप्रेशन ट्री एक विशेष प्रकार का बाइनरी ट्री है जिसमें प्रत्येक नोड या तो एक ऑपरेटर होता है या एक ऑपरेंड, जो इस प्रकार वितरित होते हैं:
- ट्री के लीफ नोड्स वे मान होते हैं जिन पर ऑपरेशन किया जाना है।
- नॉन-लीफ नोड्स में बाइनरी ऑपरेटर होता है जो किए जाने वाले ऑपरेशन को दर्शाता है।
उदाहरण से समझते हैं:
इनपुट:
आउटपुट: 1
व्याख्या:
एक्सप्रेशन ट्री को डीकोड करने पर:
Exp = ( (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
