एक्सप्रेशन ट्री मूल रूप से एक बाइनरी ट्री है जिसका उपयोग एक्सप्रेशन को दर्शाने के लिए किया जाता है। एक्सप्रेशन ट्री में, नोड्स ऑपरेटर के अनुरूप होते हैं और प्रत्येक लीफ नोड ऑपरेंड से मेल खाता है। यह एक सी++ प्रोग्राम है जो इनऑर्डर, प्रीऑर्डर और पोस्टऑर्डर ट्रैवर्सल में पोस्टफिक्स एक्सप्रेशन के लिए एक्सप्रेशन ट्री बनाने के लिए है।
एल्गोरिदम
Begin Function r() has a character variable as parameter. If the characters are + or - or * or / then Return will be -1 If the characters are from A to Z then Return will be 1. If the characters are from a to z then Return will be 1. Else Return -100. Function construct_expression_tree() to construct the expression tree Function push() to push values in the stack Function pop() to pop values from the stack Function preOrder() for pre-order traversal Function inOrder() for in-order traversal Function postOrder() for post-order traversal End.
उदाहरण कोड
#include <iostream>
using namespace std;
struct n {
char d;
n *l;
n *r;
};
char pf[50];
int top = -1;
n *a[50];
int r(char inputch) {
if (inputch == '+' || inputch == '-' || inputch == '*' || inputch== '/')
return (-1);
else if (inputch >= 'A' || inputch <= 'Z')
return (1);
else if (inputch >= 'a' || inputch <= 'z')
return (1);
else
return (-100);
}
void push(n *tree) {
top++;
a[top] = tree;
}
n *pop() {
top--;
return (a[top + 1]);
}
void construct_expression_tree(char *suffix) {
char s;
n *newl, *p1, *p2;
int flag;
s = suffix[0];
for (int i = 1; s != 0; i++) {
flag = r(s);
if (flag == 1) {
newl = new n;
newl->d = s;
newl->l = NULL;
newl->r = NULL;
push(newl);
} else {
p1 = pop();
p2 = pop();
newl = new n;
newl->d = s;
newl->l = p2;
newl->r = p1;
push(newl);
}
s = suffix[i];
}
}
void preOrder(n *tree) {
if (tree != NULL) {
cout << tree->d;
preOrder(tree->l);
preOrder(tree->r);
}
}
void inOrder(n *tree) {
if (tree != NULL) {
inOrder(tree->l);
cout << tree->d;
inOrder(tree->r);
}
}
void postOrder(n *tree) {
if (tree != NULL) {
postOrder(tree->l);
postOrder(tree->r);
cout << tree->d;
}
}
int main(int argc, char **argv) {
cout << "Enter Postfix Expression : ";
cin >> pf;
construct_expression_tree(pf);
cout << "\nIn-Order Traversal : ";
inOrder(a[0]);
cout << "\nPre-Order Traversal : ";
preOrder(a[0]);
cout << "\nPost-Order Traversal : ";
postOrder(a[0]);
return 0;
} आउटपुट
Enter Postfix Expression : 762*+6+ In-Order Traversal : 7+6*2+6 Pre-Order Traversal : ++7*626 Post-Order Traversal : 762*+6+