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

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

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

उदाहरण के लिए:व्यंजक:A + B * (C - D)

व्यंजक को उलटने के बाद होगा:) D – C (* B + A

इसलिए हमें शुरुआती कोष्ठक को बंद करने वाले कोष्ठक में बदलना होगा और इसके विपरीत।

उलटने के बाद, व्यंजक पोस्टफ़िक्स . में बदल जाता है इंफिक्स टू पोस्टफिक्स एल्गोरिथम का उपयोग करके फॉर्म। उसके बाद फिर से उपसर्ग अभिव्यक्ति प्राप्त करने के लिए उपसर्ग अभिव्यक्ति को उलट दिया जाता है।

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

Input:
Infix Expression: x^y/(5*z)+2
Output:
Prefix Form Is: +/^xy*5z2

एल्गोरिदम

infixToPrefix(infix)

इनपुट - उपसर्ग रूप में बदलने के लिए इन्फिक्स व्यंजक।

आउटपुट - उपसर्ग अभिव्यक्ति।

Begin
   reverse the infix expression
   for each character ch of reversed infix expression, do
      if ch = opening parenthesis, then
         convert ch to closing parenthesis
      else if ch = closing parenthesis, then
         convert ch to opening parenthesis
   done

   postfix := find transformed infix expression to postfix expression
   prefix := reverse recently calculated postfix form
   return prefix
End

उदाहरण

#include<iostream>
#include<stack>
#include<locale> //for function isalnum()
#include<algorithm>
using namespace std;

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

string inToPost(string infix) {
   stack<char> stk;
   stk.push('#');    //add some extra character to avoid underflow
   string postfix = "";   //initially the postfix string is empty
   string::iterator it;

   for(it = infix.begin(); it!=infix.end(); it++) {
      if(isalnum(char(*it)))
         postfix += *it;    //add to postfix when character is letter or number
      else if(*it == '(')
         stk.push('(');
      else if(*it == '^')
         stk.push('^');
      else if(*it == ')') {
         while(stk.top() != '#' && stk.top() != '(') {
            postfix += stk.top();    //store and pop until ( has found
            stk.pop();
         }

         stk.pop();    //remove the '(' from stack
      }else {
         if(preced(*it) > preced(stk.top()))
            stk.push(*it);    //push if precedence is high
         else {
            while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
               postfix += stk.top();    //store and pop until higher precedence is found
               stk.pop();
            }
            stk.push(*it);
         }
      }
   }

   while(stk.top() != '#') {
      postfix += stk.top();    //store and pop until stack is not empty

      stk.pop();

   }
   return postfix;
}

string inToPre(string infix) {
   string prefix;
   reverse(infix.begin(), infix.end());    //reverse the infix expression
   string::iterator it;

   for(it = infix.begin(); it != infix.end(); it++) {    //reverse the parenthesis after reverse
      if(*it == '(')
         *it = ')';
      else if(*it == ')')
         *it = '(';
   }

   prefix = inToPost(infix);                 //convert new reversed infix to postfix form.
   reverse(prefix.begin(), prefix.end());    //again reverse the result to get final prefix form
   return prefix;
}

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

आउटपुट

Prefix Form Is: +/^xy*5z2