इनफिक्स को पोस्टफिक्स एक्सप्रेशन में बदलना

इनफिक्स एक्सप्रेशन मनुष्यों द्वारा पढ़ने और हल करने योग्य होते हैं। हम ऑपरेटर्स के क्रम को आसानी से अलग कर सकते हैं, और गणितीय एक्सप्रेशन को हल करते समय उस भाग को पहले हल करने के लिए पैरेंथेसिस का भी उपयोग कर सकते हैं। कंप्यूटर ऑपरेटर्स और पैरेंथेसिस को आसानी से अलग नहीं कर सकता, इसलिए पोस्टफिक्स रूपांतरण की आवश्यकता होती है।

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

नोट: यहां हम केवल {+, -, *, /, ^} ऑपरेटर्स पर विचार करेंगे, अन्य ऑपरेटर्स को नजरअंदाज किया जाता है।

इनपुट और आउटपुट

इनपुट: इनफिक्स एक्सप्रेशन: x^y/(5*z)+2
आउटपुट: पोस्टफिक्स फॉर्म है: xy^5z*/2+

एल्गोरिदम

infixToPostfix(infix)

इनपुट: इनफिक्स एक्सप्रेशन
आउटपुट: इनफिक्स एक्सप्रेशन को पोस्टफिक्स रूप में बदलें

शुरुआत
    शुरू में स्टैक में कुछ विशेष कैरेक्टर जैसे # पुश करें
    इनफिक्स एक्सप्रेशन से प्रत्येक कैरेक्टर ch के लिए, करें
        यदि ch अल्फान्यूमेरिक कैरेक्टर है, तो
            ch को पोस्टफिक्स एक्सप्रेशन में जोड़ें
        अन्यथा यदि ch = ओपनिंग पैरेंथेसिस (, तो
            ( को स्टैक में पुश करें
        अन्यथा यदि ch = ^, तो
            // उच्च प्राथमिकता का एक्सपोनेंशियल ऑपरेटर
            ^ को स्टैक में पुश करें
        अन्यथा यदि ch = क्लोजिंग पैरेंथेसिस ), तो
            जब तक स्टैक खाली नहीं है और स्टैक टॉप ≠ (,
                स्टैक से पॉप करें और पोस्टफिक्स एक्सप्रेशन में जोड़ें
            पूर्ण
            ( को भी स्टैक से पॉप करें
        अन्यथा
            जब तक स्टैक खाली नहीं है AND ch की प्राथमिकता <= स्टैक टॉप तत्व की प्राथमिकता, करें
                पॉप करें और पोस्टफिक्स एक्सप्रेशन में जोड़ें
            पूर्ण
            नए आने वाले कैरेक्टर को पुश करें
    पूर्ण
    जब तक स्टैक में कुछ शेष कैरेक्टर हैं, करें
        पॉप करें और पोस्टफिक्स एक्सप्रेशन में जोड़ें
    पूर्ण
    वापस पोस्टफिक्स
अंत

उदाहरण (C++ कोड)

#include <iostream>
#include <stack>
#include <locale>
using namespace std;

int preced(char ch) {
    if(ch == '+' || ch == '-')
        return 1;
    else if(ch == '*' || ch == '/')
        return 2;
    else if(ch == '^')
        return 3;
    else
        return 0;
}

string inToPost(string infix) {
    stack stk;
    stk.push('#');
    string postfix = "";
    string::iterator it;
    
    for(it = infix.begin(); it != infix.end(); it++) {
        if(isalnum(char(*it)))
            postfix += *it;
        else if(*it == '(')
            stk.push('(');
        else if(*it == '^')
            stk.push('^');
        else if(*it == ')') {
            while(stk.top() != '#' && stk.top() != '(') {
                postfix += stk.top();
                stk.pop();
            }
            stk.pop();
        } else {
            if(preced(*it) > preced(stk.top()))
                stk.push(*it);
            else {
                while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
                    postfix += stk.top();
                    stk.pop();
                }
                stk.push(*it);
            }
        }
    }
    
    while(stk.top() != '#') {
        postfix += stk.top();
        stk.pop();
    }
    return postfix;
}

int main() {
    string infix = "x^y/(5*z)+2";
    cout << "Postfix Form Is: " << inToPost(infix) << endl;
}

आउटपुट

Postfix Form Is: xy^5z*/2+