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