ইনফিক্সকে প্রিফিক্স এক্সপ্রেশনে রূপান্তর করুন

কম্পিউটার দ্বারা অভিব্যক্তি সমাধান করার জন্য, আমরা এটিকে পোস্টফিক্স ফর্মে বা প্রিফিক্স ফর্মে রূপান্তর করতে পারি। এখানে আমরা দেখব কিভাবে ইনফিক্স এক্সপ্রেশনগুলি উপসর্গ আকারে রূপান্তরিত হয়।

প্রথম ইনফিক্স এক্সপ্রেশন বিপরীত হয়. নোট করুন যে খোলার এবং বন্ধ বন্ধনী বিপরীত করার জন্যও উল্টানো হবে।

একটি উদাহরণের জন্য:অভিব্যক্তি:A + B * (C - D)

বিপরীত করার পরে অভিব্যক্তিটি হবে:) D – C ( * B + A

তাই আমাদের খোলা বন্ধনীকে ক্লোজিং বন্ধনীতে এবং এর বিপরীতে রূপান্তর করতে হবে।

বিপরীত করার পরে, অভিব্যক্তিটি পোস্টফিক্স-এ রূপান্তরিত হয় পোস্টফিক্স অ্যালগরিদম থেকে infix ব্যবহার করে ফর্ম. এর পরে আবার পোস্টফিক্স এক্সপ্রেশনটি প্রিফিক্স এক্সপ্রেশন পেতে বিপরীত হয়।

ইনপুট এবং আউটপুট

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