C++ प्रोग्राम: पोस्टफिक्स एक्सप्रेशन के लिए एक्सप्रेशन ट्री बनाना

एक एक्सप्रेशन ट्री मूल रूप से एक बाइनरी ट्री है जिसका उपयोग एक्सप्रेशन्स को दर्शाने के लिए किया जाता है। एक्सप्रेशन ट्री में, नोड्स ऑपरेटर से मेल खाते हैं और प्रत्येक लीफ नोड ऑपरेंड से मेल खाता है। यह पोस्टफिक्स एक्सप्रेशन के लिए एक्सप्रेशन ट्री बनाने का C++ प्रोग्राम है जो इनऑर्डर, प्रीऑर्डर और पोस्टऑर्डर ट्रैवर्सल में होता है।

एल्गोरिदम

शुरुआत
    फ़ंक्शन r() में एक कैरेक्टर वेरिएबल पैरामीटर के रूप में होता है
        यदि कैरेक्टर + या - या * या / हैं तो
            -1 लौटाएं
        यदि कैरेक्टर A से Z हैं तो
            1 लौटाएं
        यदि कैरेक्टर a से z हैं तो
            1 लौटाएं
        अन्यथा
            -100 लौटाएं
    एक्सप्रेशन ट्री बनाने के लिए construct_expression_tree() फ़ंक्शन
    स्टैक में मान पुश करने के लिए push() फ़ंक्शन
    स्टैक से मान पॉप करने के लिए pop() फ़ंक्शन
    प्री-ऑर्डर ट्रैवर्सल के लिए preOrder() फ़ंक्शन
    इन-ऑर्डर ट्रैवर्सल के लिए inOrder() फ़ंक्शन
    पोस्ट-ऑर्डर ट्रैवर्सल के लिए postOrder() फ़ंक्शन
समाप्ति

उदाहरण कोड

#include <iostream>
#include <cctype>
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 (isalpha(inputch))
        return 1;
    else if (isdigit(inputch))
        return 1;
    else
        return -100;
}

void push(n* tree) {
    top++;
    a[top] = tree;
}

n* pop() {
    return a[top--];
}

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() {
    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+

व्याख्या

पोस्टफिक्स 762*+6+ के लिए:

इनऑर्डर (इनफिक्स): 7 + 6 * 2 + 6
प्रीऑर्डर (प्रीफिक्स): + + 7 * 6 2 6
पोस्टऑर्डर (पोस्टफिक्स): 7 6 2 * + 6 +

सुधार

मूल कोड में inputch >= 'A' || inputch <= 'Z' गलत था (हमेशा सत्य)। सही: isalpha(inputch) या (inputch >= 'A' && inputch <= 'Z') || (inputch >= 'a' && inputch <= 'z')
डिजिट्स के लिए isdigit() जोड़ा गया
मेमोरी लीक ठीक करने के लिए डिलीट फ़ंक्शन जोड़ना चाहिए

एक्सप्रेशन ट्री संरचना