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

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

सबसे पहले इनफिक्स एक्सप्रेशन को उल्टा किया जाता है। ध्यान दें कि उल्टा करने पर ओपनिंग और क्लोजिंग पैरेंथेसिस भी उल्टे हो जाएंगे।

उदाहरण के लिए: एक्सप्रेशन: A + B * (C - D)

उल्टा करने के बाद एक्सप्रेशन होगा: ) D - C ( * B + A

इसलिए हमें ओपनिंग पैरेंथेसिस को क्लोजिंग पैरेंथेसिस में और इसके विपरीत बदलने की आवश्यकता है।

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

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

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

एल्गोरिदम

infixToPrefix(infix)

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

शुरुआत
    इनफिक्स एक्सप्रेशन को उल्टा करें
    उल्टे इनफिक्स एक्सप्रेशन के प्रत्येक कैरेक्टर ch के लिए, करें
        यदि ch = ओपनिंग पैरेंथेसिस, तो
            ch को क्लोजिंग पैरेंथेसिस में बदलें
        अन्यथा यदि ch = क्लोजिंग पैरेंथेसिस, तो
            ch को ओपनिंग पैरेंथेसिस में बदलें
    पूर्ण
    postfix := परिवर्तित इनफिक्स एक्सप्रेशन को पोस्टफिक्स एक्सप्रेशन में ढूंढें
    prefix := हाल ही में गणना किए गए पोस्टफिक्स रूप को उल्टा करें
    वापस prefix
अंत

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

#include <iostream>
#include <stack>
#include <locale>
#include <algorithm>
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;
}

string inToPre(string infix) {
    string prefix;
    reverse(infix.begin(), infix.end());
    string::iterator it;
    
    for(it = infix.begin(); it != infix.end(); it++) {
        if(*it == '(')
            *it = ')';
        else if(*it == ')')
            *it = '(';
    }
    
    prefix = inToPost(infix);
    reverse(prefix.begin(), prefix.end());
    return prefix;
}

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

आउटपुट

Prefix Form Is: +/^xy*5z2