Infix to Prefix conversion using stack

10 min read

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 20
void push(int);
char pop();
void infix_to_prefix();
int precedence (char);
char stack[20],infix[20],prefix[20];
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 stack
void 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 them
char 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 expressions

void infix_to_prefix()
{
int i = 0,j = 0;
strrev(infix); // Reverse the infix expression
while(infix[i] != '\0')
{
// if an alphabet is found then copy it to the output string
if(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 stack
else if(infix[i] == ')' || infix[i] == '}' || infix[i] == ']')
{
push(i);
i++;
}
// if an opening bracket is found, then
else 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 stack
if(top == -1)
{
push(i);
i++;
}
// if the precedence of operator is less than the stack top then
else if( precedence(infix[i]) < precedence(stack[top]))
{
prefix[j] = pop(); // pop the stack top and add it to the prefix string
j++;
// if you have an operator that has precedence greater than operator
while(precedence(stack[top]) > precedence(infix[i])){
prefix[j] = pop(); // Pop the operator
j++;
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 stack
i++;
}}}
// At the end remove all the operators from the stack
while(top != -1)
{
prefix[j] = pop();
j++;
}
// Reverse the final string before output
strrev(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

infix to prefix

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error