একটি এক্সপ্রেশন ট্রি মূলত একটি বাইনারি ট্রি যা এক্সপ্রেশন উপস্থাপন করতে ব্যবহৃত হয়। এক্সপ্রেশন ট্রিতে, নোডগুলি অপারেটরের সাথে মিলে যায় এবং প্রতিটি লিফ নোড অপারেন্ডের সাথে মিলে যায়। ইনঅর্ডার, প্রিঅর্ডার এবং পোস্টঅর্ডার ট্রাভার্সালে পোস্টফিক্স এক্সপ্রেশনের জন্য একটি এক্সপ্রেশন ট্রি তৈরি করার জন্য এটি একটি C++ প্রোগ্রাম।
অ্যালগরিদম
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+
