แปลง Infix เป็น Prefix Expression

ในการแก้ไขนิพจน์โดยใช้คอมพิวเตอร์ เราสามารถแปลงเป็นรูปแบบ postfix หรือแบบฟอร์มคำนำหน้า ที่นี่เราจะดูว่านิพจน์ infix ถูกแปลงเป็นรูปแบบคำนำหน้าอย่างไร

ในตอนแรกนิพจน์ infix จะกลับรายการ โปรดทราบว่าการกลับวงเล็บเปิดและปิดจะเป็นการกลับรายการด้วย

ตัวอย่างเช่น นิพจน์:A + B * (C - D)

หลังจากย้อนกลับนิพจน์จะเป็น:) D – C ( * B + A

เราจึงต้องแปลงวงเล็บเปิดเป็นวงเล็บปิด และในทางกลับกัน

หลังจากย้อนกลับ นิพจน์จะถูกแปลงเป็น postfix แบบฟอร์มโดยใช้อัลกอริทึม infix ถึง postfix หลังจากนั้นอีกครั้ง นิพจน์ postfix จะกลับกันเพื่อรับนิพจน์คำนำหน้า

อินพุตและเอาต์พุต

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

อัลกอริทึม

infixToPrefix(infix)

ป้อนข้อมูล - นิพจน์ 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