Infix to Postfix 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 postfix and prefix notations. Now, let us see how to convert an infix expression to postfix.

  • Infix notation ( a operator b ): For example, a + b is an infix notation.
  • Postfix notation ( a b operator ): a b + is the equivalent postfix 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 postfix (or prefix) before evaluation.
  • The corresponding expression in postfix form is: abc/+d-. The postfix expressions can be easily evaluated using a stack. 

 

Steps to convert infix expression to postfix

1. Scan the given infix expression from left to right.
2. If the scanned character is an operand, then output it.
3. Else,

  • If the precedence of the scanned operator is greater than the precedence of the operator in the top of the stack(or the stack is empty or if the stack contains a ‘(‘ ), push it.
  • Else, Pop all operators from the stack whose precedence is greater than or equal to that of the scanned operator. Then, push the scanned operator to the top of the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)

4. If the scanned character is  ‘(‘, push it to the stack.
5. If the scanned character is  ‘)’, pop the stack and and output characters until ‘(‘ is encountered, and discard both the parenthesis.
6. Repeat steps 2-5 until infix expression is scanned completely.
7. Print the output.
8. Pop and output from the stack.

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

INPUT CHARACTER OPERATION ON STACK STACK POSTFIX NOTATION
a   EMPTY a
/ PUSH + a
b   + ab
( PUSH -( ab/
c   -( ab/c
+ CHECK AND PUSH -(+ ab/c
d   -(+ ab/cd
) POP AND OUTPUT TILL '(' - ab/cd+
- CHECK AND PUSH - ab/cd+-
e   - ab/cd+-e
END OF INPUT POP TILL EMPTY EMPTY ab/cd+-e-

 

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include <string.h>

/* Variable declarations */
char infix_string[20], postfix_string[20];
int top;
int stack[20];

int pop();
int precedence(char symbol);
int isEmpty();
void infix_to_postfix();
int check_space(char symbol);
void push(long int symbol);

int main()
{
int count, length;
char temp;
top = -1;
printf("\nINPUT THE INFIX EXPRESSION : ");
scanf("%s", infix_string);
infix_to_postfix();
printf("\nEQUIVALENT POSTFIX EXPRESSION : %s\n", postfix_string);
return 0;
}

/* Function to convert from infix to postfix */
void infix_to_postfix()
{
unsigned int count, temp = 0;
char next;
char symbol;
for(count = 0; count < strlen(infix_string); count++)
{
symbol = infix_string[count]; // Scanning the input expression
if(!check_space(symbol))
{
switch(symbol)
{
case '(': push(symbol);
break;
case ')':
while((next = pop()) != '(') // pop until '(' is encountered
{
postfix_string[temp++] = next;
}
break;
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
while(!isEmpty() && precedence(stack[top]) >= precedence(symbol)) // Check precedence and push the higher one
postfix_string[temp++] = pop();
push(symbol);
break;
default:
postfix_string[temp++] = symbol;
}
}
}
while(!isEmpty())
{
postfix_string[temp++] = pop();
}
postfix_string[temp] = '\0';
}

/* Function to check precedence of operators */
int precedence(char symbol)
{
switch(symbol)
{
case '(': return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '^':
return 3;
default:
return 0;
}
}

int check_space(char symbol)
{
if(symbol == '\t' || symbol == ' ' )
{
return 1;
}
else
{
return 0;
}
}

void push(long int symbol)
{
if(top > 20)
{
printf("Stack Overflow\n");
exit(1);
}
top = top + 1;
stack[top] = symbol; // Push the symbol and make it as TOP
}

int isEmpty()
{
if(top == -1)
{
return 1;
}
else
{
return 0;
}
}

int pop()
{
if(isEmpty())
{
printf("Stack is Empty\n");
exit(1);
}
return(stack[top--]); // Pop the symbol and decrement TOP
}


OUTPUT

infix to postfix

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