将中缀转换为前缀表达式

要通过计算机求解表达式，我们可以将其转换为后缀形式或前缀形式。在这里，我们将看到中缀表达式如何转换为前缀形式。

首先，中缀表达式反转。注意，对于反转，圆括号也将反转。

例如：表达式：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