C++ প্রোগ্রাম: এক্সপ্রেশন ট্রি অ্যালগরিদম বাস্তবায়ন

এক্সপ্রেশন ট্রি মূলত একটি বাইনারি ট্রি যা এক্সপ্রেশন উপস্থাপন করতে ব্যবহৃত হয়। এক্সপ্রেশন ট্রিতে, ইন্টারনাল নোডগুলো অপারেটর উপস্থাপন করে এবং প্রতিটি ليف নোড অপারেন্ড উপস্থাপন করে। নিচে এক্সপ্রেশন ট্রি অ্যালগরিদম বাস্তবায়নের একটি C++ প্রোগ্রাম দেওয়া হলো যা পোস্টফিক্স এক্সপ্রেশন ইনপুট হিসেবে নিয়ে соответствуюচিত এক্সপ্রেশন ট্রি তৈরি করে এবং ইনঅর্ডারে ট্রভার্স করে।

শুরু
  construct_expression_tree() ফাংশন:
    ফ্ল্যাগ = 1 যখন অপারেন্ড।
    ফ্ল্যগ = -1 যখন অপারেটর।
    S = suffix[0] মানে এক্সপ্রেশন থেকে প্রথম অপারেন্ড পড়ুন।
    i = 0 থেকে s != 0 পর্যন্ত
      সিম্বল অপারেন্ড নাকি অপারেটর তা চেক করুন।
      ইনঅর্ডার ট্রভার্সালের জন্য void inorder() ফাংশন কল করুন।
      ফলাফল প্রিন্ট করুন।
      i বাড়ান।
শেষ

#include 
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 inOrder(n *tree) { // ইনঅর্ডার ট্রভার্সাল
    if (tree != NULL) {
        inOrder(tree->l);
        cout << tree->d;
        inOrder(tree->r);
    }
}

int main(int argc, char **argv) {
    cout << "Enter Postfix Expression : "; cin >> pf;
    construct_expression_tree(pf);
    cout << "\nInfix Expression : "; inOrder(a[0]);
    return 0;
}

Enter Postfix Expression : 762*+6+
Infix Expression : 7+6*2+6