एक एक्सप्रेशन ट्री मूलतः एक बाइनरी ट्री है जिसका उपयोग एक्सप्रेशन को दर्शाने के लिए किया जाता है। एक एक्सप्रेशन ट्री में, इंटरनल नोड्स ऑपरेटर्स से संबंधित होते हैं और प्रत्येक लीफ नोड ऑपरेंड्स से संबंधित होते हैं। यहां इनऑर्डर, प्रीऑर्डर और पोस्टऑर्डर ट्रैवर्सल में प्रीफिक्स एक्सप्रेशन के लिए एक्सप्रेशन ट्री का निर्माण करने के लिए एक C++ प्रोग्राम है।
एल्गोरिदम
Begin class ExpressionTree जिसमें निम्नलिखित फंक्शन्स हैं: function push() ट्री में नोड्स को पुश करने के लिए: यदि स्टैक नल है तो नोड को पहले एलिमेंट के रूप में पुश करें अन्यथा नोड को पुश करें और इसे टॉप बनाएं function pop() ट्री से नोड्स को पॉप आउट करने के लिए: यदि स्टैक नल है तो अंडरफ्लो प्रिंट करें अन्यथा नोड को पॉप आउट करें और टॉप को अपडेट करें function insert() कैरेक्टर्स को इन्सर्ट करने के लिए: यदि यह डिजिट है तो इसे पुश करें। अन्यथा यदि यह ऑपरेटर है तो इसे पॉप करें। अन्यथा "invalid Expression" प्रिंट करें function postOrder() पोस्टऑर्डर ट्रैवर्सल के लिए: यदि ट्री खाली नहीं है postOrder(ptr->l) postOrder(ptr->r) रूट को ptr->d के रूप में प्रिंट करें function inOrder() इनऑर्डर ट्रैवर्सल के लिए: यदि ट्री खाली नहीं है inOrder(ptr->l) रूट को ptr->d के रूप में प्रिंट करें inOrder(ptr->r) function preOrder() प्रीऑर्डर ट्रैवर्सल के लिए: यदि ट्री खाली नहीं है रूट को ptr->d के रूप में प्रिंट करें preOrder(ptr->l) preOrder(ptr->r) End
उदाहरण कोड
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> using namespace std; class TreeN//नोड डिक्लेरेशन { public: char d; TreeN *l, *r; TreeN(char d) { this->d = d; this->l = NULL; this->r = NULL; } }; class StackNod// स्टैक डिक्लेरेशन { public: TreeN *treeN; StackNod *n; StackNod(TreeN*treeN)//कंस्ट्रक्टर { this->treeN = treeN; n = NULL; } }; class ExpressionTree { private: StackNod *top; public: ExpressionTree() { top = NULL; } void clear() { top = NULL; } void push(TreeN *ptr) { if (top == NULL) top = new StackNod(ptr); else { StackNod *nptr = new StackNod(ptr); nptr->n = top; top = nptr; } } TreeN *pop() { if (top == NULL) { cout<<"Underflow"<<endl; } else { TreeN *ptr = top->treeN; top = top->n; return ptr; } } TreeN *peek() { return top->treeN; } void insert(char val) { if (isDigit(val)) { TreeN *nptr = new TreeN(val); push(nptr); } else if (isOperator(val)) { TreeN *nptr = new TreeN(val); nptr->l = pop(); nptr->r= pop(); push(nptr); } else { cout<<"Invalid Expression"<<endl; return; } } bool isDigit(char ch) { return ch >= '0' && ch <= '9'; } bool isOperator(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } int toDigit(char ch) { return ch - '0'; } void buildTree(string eqn) { for (int i = eqn.length() - 1; i >= 0; i--) insert(eqn[i]); } void postfix() { postOrder(peek()); } void postOrder(TreeN*ptr) { if (ptr != NULL) { postOrder(ptr->l); postOrder(ptr->r); cout<<ptr->d; } } void infix() { inOrder(peek()); } void inOrder(TreeN *ptr) { if (ptr != NULL) { inOrder(ptr->l); cout<<ptr->d; inOrder(ptr->r); } } void prefix() { preOrder(peek()); } void preOrder(TreeN *ptr) { if (ptr != NULL) { cout<<ptr->d; preOrder(ptr->l); preOrder(ptr->r); } } }; int main() { string s; ExpressionTree et; cout<<"\nEnter equation in Prefix form: "; cin>>s; et.buildTree(s); cout<<"\nPrefix : "; et.prefix(); cout<<"\n\nInfix : "; et.infix(); cout<<"\n\nPostfix : "; et.postfix(); }आउटपुट
Enter equation in Prefix form: ++7*626 Prefix : ++7*626 Infix : 7+6*2+6 Postfix : 762*+6+
