 # Infix to Prefix conversion using stack

Expression conversion is the most important application of stacks. Given an infix expression, it can be converted to both prefix and postfix notations. Now, let us see how to convert an expression from infix to prefix.

• Infix notation ( a operator b ): For example, a + b is an infix notation.
• Prefix notation ( operator a b ): + a b  is the equivalent prefix notation of a + b.

The compiler scans the given expression either from left to right or from right to left.

Consider the below expression: a + b / c - d

• At first, compiler scans the expression to evaluate the expression b / c, then scans the expression again to add a to it. The result is then subtracted with d after another scan.
• This repeated scanning makes the process very inefficient and time consuming. It will be much easier if the expression is converted to prefix (or postfix) before evaluation.
• The corresponding expression in prefix form is: -+a/bcd. The prefix expressions can be easily evaluated using a stack.

## Steps to convert infix expression to prefix

1. First, reverse the given infix expression.
2. Scan the characters one by one.
3. If the character is an operand, copy it to the prefix notation output.
4. If the character is a closing parenthesis, then push it to the stack.
5. If the character is an opening parenthesis, pop the elements in the stack until we find the corresponding closing parenthesis.
6. If the character scanned is an operator
• If the operator has precedence greater than or equal to the top of the stack, push the operator to the stack.
• If the operator has precedence lesser than the top of the stack, pop the operator and output it to the prefix notation output and then check the above condition again with the new top of the stack.

7. After all the characters are scanned, reverse the prefix notation output.

For example, consider the infix expression a/b-(c+d)-e.

After reversing, the notation becomes, e-(d+c)-b/a. While reversing, change open parenthesis to closed parenthesis and vice versa.

 INPUT CHARACTER OPERATION ON STACK STACK PREFIX NOTATION e EMPTY e - PUSH - e ( POP IN STACK until ')' - e d - ed + +- ed c +- edc ) POP FROM STACK TO OUTPUT - edc+ - PUSH -- edc+ b -- edc+b / PUSH /-- edc+b a edc+ba END OF INPUT POP TILL EMPTY -- edc+ba/ - edc+ba/- EMPTY edc+ba/--

Now, reverse the PREFIX NOTATION from the table,

The prefix notation of the infix expression a/b-(c+d)-e is --/ab+cde.

Now, let us see a C program to convert an infix expression to prefix expression

## C program to convert an expression from Infix to Postfix

`#include<stdio.h>#include<math.h>#include<string.h>#include <stdlib.h>#define MAX 20void push(int);char pop();void infix_to_prefix();int precedence (char);char stack,infix,prefix;int top = -1;int main(){printf("\nINPUT THE INFIX EXPRESSION : ");scanf("%s",infix);infix_to_prefix();return 0;}// method that pushes the elements onto the character stackvoid push(int pos){if(top == MAX-1){printf("\nSTACK OVERFLOW\n");}else {top++;stack[top] = infix[pos];}}// method that removes character from stack and returns themchar pop(){char ch;if(top < 0){printf("\nSTACK UNDERFLOW\n");exit(0);}else{ch = stack[top];stack[top] = '\0';top--;return(ch);}return 0;}// method that converts String from infix to prefix// all the strings are assumed to be valid expressionsvoid infix_to_prefix(){int i = 0,j = 0;strrev(infix); // Reverse the infix expressionwhile(infix[i] != '\0'){// if an alphabet is found then copy it to the output stringif(infix[i] >= 'a' && infix[i] <= 'z'){prefix[j] = infix[i];j++;i++;}// In the reversed string, closing bracket will be found first so put it in the stackelse if(infix[i] == ')' || infix[i] == '}' || infix[i] == ']'){push(i);i++;}// if an opening bracket is found, thenelse if(infix[i] == '(' || infix[i] == '{' || infix[i] == '[') /* when closing bracket is found */{if(infix[i] == '('){while(stack[top] != ')') /* pop till opening bracket is found */{prefix[j] = pop();j++;}pop();i++;}else if(infix[i] == '['){while(stack[top] != ']') /* pop till corresponding opening bracket is found */{prefix[j] = pop();j++;}pop();i++;}else if(infix[i] == '{'){while(stack[top] != '}') /*pop till corresponding opening bracket is found*/{prefix[j] = pop();j++;}pop();i++;}}else{// if the stack if empty, then we simply put the operator in stackif(top == -1){push(i);i++;}// if the precedence of operator is less than the stack top thenelse if( precedence(infix[i]) < precedence(stack[top])){prefix[j] = pop();  // pop the stack top and add it to the prefix stringj++;// if you have an operator that has precedence greater than operatorwhile(precedence(stack[top]) > precedence(infix[i])){prefix[j] = pop();    // Pop the operatorj++;if(top < 0) {break;}}push(i);i++;}// if the precedence of operator is greater than or equal to the stack top else if(precedence(infix[i]) >= precedence(stack[top])){push(i);  //  Push it onto the stacki++;}}}// At the end remove all the operators from the stackwhile(top != -1){prefix[j] = pop();j++;}// Reverse the final string before outputstrrev(prefix);prefix[j] = '\0';printf("EQUIVALENT PREFIX NOTATION : %s ",prefix);}/* Function to return precedence of operators */int precedence(char alpha){if(alpha == '+' || alpha =='-'){return(1);}if(alpha == '*' || alpha =='/'){return(2);}return 0;}`

OUTPUT ### Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`