中置を接頭辞式に変換する

コンピューターで式を解決するには、式を接尾辞形式または接頭辞形式に変換します。ここでは、中置式がどのように接頭辞形式に変換されるかを確認します。

最初は中置式が逆になります。開き括弧と閉じ括弧を逆にすると、括弧も逆になることに注意してください。

例：式：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