Operation & Algorithm of Expression Tree in Hindi

एक्सप्रेशन ट्री एक बाइनरी ट्री होता है जिसका उपयोग किसी गणितीय या तार्किक अभिव्यक्ति (expression) को दर्शाने के लिए किया जाता है। इसमें ऑपरेटर नोड्स और ऑपरेंड्स (संख्याएं या वेरिएबल्स) होते हैं। एक्सप्रेशन ट्री का उपयोग विभिन्न प्रकार के 

एक्सप्रेशनों जैसे गणितीय (Arithmetic) और तार्किक (Logical) एक्सप्रेशनों को स्टोर और उनका मूल्यांकन (evaluation) करने के लिए किया जाता है।

एक्सप्रेशन ट्री एक महत्वपूर्ण डेटा स्ट्रक्चर है जो गणितीय और तार्किक एक्सप्रेशनों को दर्शाने और उनका मूल्यांकन करने के लिए उपयोग किया जाता है। इसकी संरचना सरल होती है और इसे विभिन्न फॉर्मेट्स में ट्रैवर्स और पुनर्निर्माण किया जा सकता है।

 यह कम्पाइलर्स और इंटरप्रेटर्स में विशेष रूप से उपयोगी होता है।

एक्सप्रेशन ट्री में:

आंतरिक नोड्स (Internal Nodes) ऑपरेटर होते हैं (जैसे +, -, *, /)।

पत्ते (Leaf Nodes) ऑपरेंड्स होते हैं (जैसे संख्या या वेरिएबल)।

उदाहरण:

यदि हमारे पास यह गणितीय एक्सप्रेशन है: A + B * C

तो इसका एक्सप्रेशन ट्री इस प्रकार हो सकता है:

     +

    / \

   A   *

      / \

     B   C

एक्सप्रेशन ट्री को postfix, prefix, या infix एक्सप्रेशनों के आधार पर बनाया जाता है। आमतौर पर postfix एक्सप्रेशन का उपयोग किया जाता है क्योंकि इसे आसानी से स्टैक की मदद से बनाया जा सकता है।

एक्सप्रेशन ट्री का मुख्य उपयोग एक्सप्रेशन का मूल्य निकालने के लिए होता है। एक्सप्रेशन ट्री का वैल्यूएशन तब होता है जब हम ट्रैवर्सल (Inorder, Postorder, Preorder) का उपयोग करके गणितीय या तार्किक ऑपरेशन करते हैं।

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

पुनर्निर्माण (Reconstruction)

आप किसी एक्सप्रेशन को ट्री से पुनः postfix, prefix, या infix फॉर्मेट में परिवर्तित कर सकते हैं। यह ट्रैवर्सल पर निर्भर करता है कि आप किस फॉर्मेट में एक्सप्रेशन को चाहते हैं।

एक्सप्रेशन ट्री को बनाने के लिए postfix (या prefix) एक्सप्रेशन का उपयोग करना सबसे आसान तरीका है। इस एल्गोरिद्म में स्टैक की मदद से ट्री को बनाया जाता है।

#include <iostream>

#include <stack>

using namespace std;

// एक ट्री नोड के लिए क्लास

struct Node {

    char value;

    Node* left, * right;

    

    Node(char data) {

        value = data;

        left = right = NULL;

    }

};

// चेक करें कि यह ऑपरेटर है या नहीं

bool isOperator(char c) {

    return (c == '+' || c == '-' || c == '*' || c == '/');

}

// पोस्टफिक्स से एक्सप्रेशन ट्री का निर्माण करें

Node* constructTree(string postfix) {

    stack<Node*> st;

    Node *t, *t1, *t2;

    

    // पोस्टफिक्स एक्सप्रेशन को बाएं से दाएं स्कैन करें

    for (int i = 0; i < postfix.length(); i++) {

        // अगर ऑपरेटर नहीं है, तो नया नोड बनाएं और स्टैक में डालें

        if (!isOperator(postfix[i])) {

            t = new Node(postfix[i]);

            st.push(t);

        } else {

            // ऑपरेटर है, तो दो नोड्स पॉप करें

            t = new Node(postfix[i]);

            t1 = st.top(); st.pop();

            t2 = st.top(); st.pop();

            

            // पॉप किए गए नोड्स को चाइल्ड्स के रूप में जोड़ें

            t->right = t1;

            t->left = t2;

            

            // इस नोड को स्टैक में डालें

            st.push(t);

        }

    }

    

    // स्टैक का आखिरी नोड एक्सप्रेशन ट्री का रूट होगा

    return st.top();

}

// इनऑर्डर ट्रैवर्सल

void inorder(Node* t) {

    if (t) {

        inorder(t->left);

        cout << t->value << " ";

        inorder(t->right);

    }

}

int main() {

    string postfix = "AB+C*";

    Node* root = constructTree(postfix);

    

    cout << "Inorder Traversal of Expression Tree: ";

    inorder(root);

    

    return 0;

}