Chuyển đổi Infix thành Prefix Expression

Để giải các biểu thức bằng máy tính, chúng ta có thể chuyển nó ở dạng hậu tố hoặc thành dạng tiền tố. Ở đây chúng ta sẽ thấy cách các biểu thức infix được chuyển đổi sang dạng tiền tố.

Lúc đầu, biểu thức infix bị đảo ngược. Lưu ý rằng đối với việc đảo ngược dấu ngoặc mở và đóng ngoặc đơn cũng sẽ được đảo ngược.

cho một ví dụ:Biểu thức:A + B * (C - D)

sau khi đảo ngược biểu thức sẽ là:) D - C (* B + A

vì vậy chúng ta cần chuyển đổi dấu ngoặc mở sang dấu ngoặc đóng và ngược lại.

Sau khi đảo ngược, biểu thức được chuyển đổi thành hậu tố bằng cách sử dụng thuật toán infix để postfix. Sau đó, một lần nữa, biểu thức hậu tố được đảo ngược để có được biểu thức tiền tố.

Đầu vào và Đầu ra

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

Thuật toán

infixToPrefix(infix)

Đầu vào - Biểu thức tiền tố để chuyển đổi thành dạng tiền tố.

Đầu ra - Biểu thức tiền tố.

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

Ví dụ

#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;
}

Đầu ra

Prefix Form Is: +/^xy*5z2