এক্সপ্রেশন ট্রি মূলত একটি বাইনারি ট্রি যা এক্সপ্রেশন উপস্থাপন করতে ব্যবহৃত হয়। এক্সপ্রেশন ট্রিতে, নোডগুলো অপারেটরকে উপস্থাপন করে এবং প্রতিটি লিফ নোড অপারেন্ডকে উপস্থাপন করে। এটি ইনঅর্ডার, প্রিঅর্ডার ও পোস্টঅর্ডার ট্রাভার্সালে পোস্টফিক্স এক্সপ্রেশনের জন্য এক্সপ্রেশন ট্রি কনস্ট্রাক্ট করার একটি C++ প্রোগ্রাম।
অ্যালগরিদম
শুরু Function r() একটি ক্যারেক্টার ভেরিয়েবল প্যারামিটার হিসেবে নেয়। যদি ক্যারেক্টারগুলো + বা - বা * বা / হয় তবে রিটার্ন হবে -1 যদি ক্যারেক্টারগুলো A থেকে Z হয় তবে রিটার্ন হবে 1। যদি ক্যারেক্টারগুলো a থেকে z হয় তবে রিটার্ন হবে 1। Else রিটার্ন -100। Function construct_expression_tree() এক্সপ্রেশন ট্রি কনস্ট্রাক্ট করতে। Function push() স্টকে ভ্যালু পুশ করতে। Function pop() স্টক থেকে ভ্যালু পপ করতে। Function preOrder() প্রি-অর্ডার ট্রাভার্সালের জন্য। Function inOrder() ইন-অর্ডার ট্রাভার্সালের জন্য। Function postOrder() পোস্ট-অর্ডার ট্রাভার্সালের জন্য। শেষ।
উদাহরণ কোড
#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 << "পোস্টফিক্স এক্সপ্রেশন লিখুন: "; cin >> pf; construct_expression_tree(pf); cout << "\nইন-অর্ডার ট্রাভার্সাল: "; inOrder(a[0]); cout << "\nপ্রি-অর্ডার ট্রাভার্সাল: "; preOrder(a[0]); cout << "\nপোস্ট-অর্ডার ট্রাভার্সাল: "; postOrder(a[0]); return 0; }আউটপুট
পোস্টফিক্স এক্সপ্রেশন লিখুন: 762*+6+ ইন-অর্ডার ট্রাভার্সাল: 7+6*2+6 প্রি-অর্ডার ট্রাভার্সাল: ++7*626 পোস্ট-অর্ডার ট্রাভার্সাল: 762*+6+
