Convert Infix to Prefix Expression

To solve expressions by the computer, we can either convert it in postfix form or to the prefix form. Here we will see how infix expressions are converted to prefix form.

At first infix expression is reversed. Note that for reversing the opening and closing parenthesis will also be reversed.

for an example: The expression: A + B * (C - D)

after reversing the expression will be: ) D – C ( * B + A

so we need to convert opening parenthesis to closing parenthesis and vice versa.

After reversing, the expression is converted to postfix form by using infix to postfix algorithm. After that again the postfix expression is reversed to get the prefix expression.

Input and Output

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

Algorithm

infixToPrefix(infix)

Input − Infix expression to convert into prefix form.

Output − The prefix expression.

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

Example

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

Output

Prefix Form Is: +/^xy*5z2