C++ প্রোগ্রাম: প্রিফিক্স এক্সপ্রেশন থেকে এক্সপ্রেশন ট্রি তৈরি করা

এক্সপ্রেশন ট্রি মূলত একটি বাইনারি ট্রি যা এক্সপ্রেশন রিপ্রেজেন্ট করতে ব্যবহৃত হয়। এক্সপ্রেশন ট্রিতে ইন্টারনাল নোডগুলো অপারেটর রিপ্রেজেন্ট করে এবং লিফ নোডগুলো অপারেন্ড। এখানে একটি C++ প্রোগ্রাম দেওয়া হলো যা প্রিফিক্স এক্সপ্রেশনের জন্য ইনঅর্ডার, প্রिअর্ডার এবং পোস্টঅর্ডার ট্রাভার্সেল সহ এক্সপ্রেশন ট্রি নির্মাণ করে।

অ্যালগরিদম

শুরু
    ExpressionTree ক্লাস যেটির নিচের ফাংশনগুলো আছে:
    push() ফাংশন - ট্রিতে নোড পুশ করতে:
        যদি স্ট্যাক খালি হয়
            তবে নোডটিকে প্রথম এলিমেন্ট হিসেবে পুশ করো
        অন্যথায়
            নোডটি পুশ করো এবং টপ বানাও
    pop() ফাংশন - ট্রি থেকে নোড পপ করতে:
        যদি স্ট্যাক খালি হয়
            তবে "underflow" প্রিন্ট করো
        অন্যথায়
            নোডটি পপ করো এবং টপ আপডেট করো
    insert() ফাংশন - ক্যারেক্টার ইনসার্ট করতে:
        যদি ডিজিট হয়
            তবে পুশ করো
        অন্যথায় যদি অপারেটর হয়
            তবে পপ করো
        অন্যথায়
            "Invalid Expression" প্রিন্ট করো
    postOrder() ফাংশন - পোস্টঅর্ডার ট্রাভার্সাল:
        যদি ট্রি খালি না হয়
            postOrder(ptr->l)
            postOrder(ptr->r)
            রুট প্রিন্ট করো ptr->d হিসেবে
    inOrder() ফাংশন - ইনঅর্ডার ট্রাভার্সাল:
        যদি ট্রি খালি না হয়
            inOrder(ptr->l)
            রুট প্রিন্ট করো ptr->d হিসেবে
            inOrder(ptr->r)
    preOrder() ফাংশন - প্রिअর্ডার ট্রাভার্সাল:
        যদি ট্রি খালি না হয়
            রুট প্রিন্ট করো ptr->d হিসেবে
            preOrder(ptr->l)
            preOrder(ptr->r)
শেষ

উদাহরণ কোড

#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+