Infix to postfix conversion using stack

Infix to postfix conversion using stack

Today, we will discuss another problem which uses stacks, problem is to convert Infix to postfix expression. Infix expression is where the operator comes in between two operand. For example  4+5/6*7 is an infix expression. Postfix expression is where operator comes after operands like 43+5* is a postfix expression. Let’s take an example and come with algorithm to convert infix to postfix

Algorithm for infix to postfix conversion

Infix expression : 4+5*6/7
We need to move all operator at the end of operands to which it applies.

Start with first digit 4, it is an operand onto expression string. Next character is ‘+’, keep it aside on stack as it needs to come at end of all operands it applies to. Next is 5, not an operator, put it with 4 in expression string, so current state of stack and output postfix string:
infix to post conversion

Next we get ‘*’, this is an operator. Here is some work we need to do. Check if there is an operator already encountered, which has higher precedence than current operator. If not, then we are fine, we will add this operator in the set of operators onto stack but not yet added to postfix expression.

If there is operator which has higher precedence, then take out one by one all such operator (in the order they were encountered), till an operator with lower precedence is seen. Add all these operators to the postfix expressions string. Put the current operator in the set.

In this case + has lower precedence than *, hence stack has two operators (+, *). 
infix to postfix

Next character is 6. Add it to postfix expression, it becomes 456 . Visit ‘/’. Since it has higher priority than + and *, it gets added to list. Set becomes (+,*, /).

infix to postfix conversion
Check 7 and add it to post expression, expression becomes 4567.

Now we reached at the end of the expression. Now go to stack and pop operators one by one and add them to postfix expression string. Resultant postfix expression is :

Let’s see another example :(4+8)*(6-5)/((3-2)*(2+2))

This is execution trace of the function which converts this infix expression to postfix. It explains the algorithm very well.

Character being considered : (  Stack is :  Postfix exp is :  
Character being considered : 4  Stack is :  (  Postfix exp is : 4  
Character being considered : +  Stack is : ( +  Postfix exp is : 4  
Character being considered : 8  Stack is : ( +  Postfix exp is : 4 8  
Character being considered : )  Stack is : (  Postfix exp is : 4 8 +  
Character being considered : *  Stack is :  Postfix exp is : 4 8 +  
Character being considered : (  Stack is : *  Postfix exp is : 4 8 +  
Character being considered : 6  Stack is : * (  Postfix exp is : 4 8 + 6 
Character being considered : -  Stack is : * ( -  Postfix exp is : 4 8 + 6  
Character being considered : 5 Stack is : * ( -  Postfix exp is : 4 8 + 6 5
Character being considered : )  Stack is : *  Postfix exp is : 4 8 + 6 5 -  
Character being considered : /  Stack is : /  Postfix exp is : 4 8 + 6 5 - * 
Character being considered : (  Stack is : / (  Postfix exp is : 4 8 + 6 5 - *  
Character being considered : (  Stack is : / ( (  Postfix exp is : 4 8 + 6 5 - *  
Character being considered : 3  Stack is : / ( (  Postfix exp is : 4 8 + 6 5 - * 3
Character being considered : -  Stack is : / ( ( -  Postfix exp is : 4 8 + 6 5 - * 3  
Character being considered : 2  Stack is : / ( ( -  Postfix exp is : 4 8 + 6 5 - * 3 2  
Character being considered : )  Stack is : / (   Postfix exp is : 4 8 + 6 5 - * 3 2 -  
Character being considered : *  Stack is : / ( *  Postfix exp is : 4 8 + 6 5 - * 3 2 -  
Character being considered : (  Stack is : / ( * (   Postfix exp is : 4 8 + 6 5 - * 3 2 -  
Character being considered : 2  Stack is : / ( * (  Postfix exp is : 4 8 + 6 5 - * 3 2 - 2  
Character being considered : +  Stack is : / ( * ( +   Postfix exp is : 4 8 + 6 5 - * 3 2 - 2  
Character being considered : 2  Stack is : / ( * ( +  Postfix exp is : 4 8 + 6 5 - * 3 2 - 2 2  
Character being considered : )  Stack is : / ( *  Postfix exp is : 4 8 + 6 5 - * 3 2 - 2 2 + 
Character being considered : ) Stack is : /  Postfix exp is : 4 8 + 6 5 - * 3 2 - 2 2 + *  

Infix to postfix implementation

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define MAX_LENGTH_EXPRESSION 100
 
typedef struct stack {
	char items[MAX_LENGTH_EXPRESSION];
	int top;
}stack;
 
void push(stack *s, char element){
	if(s->top == MAX_LENGTH_EXPRESSION ){
		printf("\n Stack is full");
		return;
	}
	s->items[++s->top] = element;
	return;
}
 
char pop(stack *s){
	if(s->top == -1){
		printf("\n Stack empty");
	}
	return s->items[s->top--];
}
char peek(stack *s){
	if(s->top == -1){
		printf("\n Stack empty");
	}
	return s->items[s->top];
}
 
void initialize(stack *s){
	s->top = -1;
}
 
int empty(stack *s){
	if(s->top == -1) return 1;
	return 0;
}
/* This function return true or false based on whether 
character is operator or not */
int is_operand(char op){ 
  if(op == '+' || op == '-' || op == '*' || op == '/' || op =='%')
    return 1;  
  return 0;
}
 
/* This function returns associated precedence to an operator */
int precedence(char op){ 
  switch (op){   
    case '+' : 
    case '-' :
            return 1; 
    case '/' : 
    case '*' : 
            return 2;     
    case '%' :    
            return 3; 
    default : 
            return 4;  
    }
 }
/* This function tell if the op1 has lower precedence than op2 */
int lower_precedence(char op1, char op2){
  if(precedence (op1) < precedence(op2)) 
       return 1; 
    return 0;
}
 
void printStack(stack *s){
	printf("\n Stack is:");
	for(int i =0; i<= s->top; i++){
		printf("%c", s->items[i]);
	}
}
 
void infix_to_postfix(char *s){
    stack ms;
 
    initialize(&ms);
 
    char *p = (char *) malloc(strlen(s));
    char *post = p;
    char temp;
 
   /* Wrong input */
    if(!s) return ;
 
    if(*s == '\0') return ;
 
 
   	while(*s != '\0'){
		/* Case 1. If '(', push on to stack */
        if(*s == '('){
           push(&ms, *s);
        }
 	   /* Case 2. If ')', pop all op from stack till 
            we see '(', Discard ')' */
        else if(*s == ')'){
           while(!empty(&ms) && peek(&ms) != '('){
                *p  = pop(&ms);
                 p++;
           }
           if(!empty(&ms))
               pop(&ms);
       }
	   /* Case 3. If it is operator, pop all op on stack which are of higher 
  		precedence than it. Push this onto stack */
        else if(is_operand(*s)){
            while(!empty(&ms) && (!lower_precedence(peek(&ms), *s))){
               *p  = pop(&ms);
                p++;
            }
            push(&ms, *s);
        }
        /* Case 4. If it neither of above, add it to postfix expression */
 
        else{
            *p = *s;
             p++;
        }
        s++;
    }
    /*Flush all ops from stack once infix is completely visited */
    while(!empty(&ms)){
 
        *p  = pop(&ms);
        p++;
   }
   printf("\nPostfix expression is : ");
   printf("%s\n" , post);
}

int main(void) {
	infix_to_postfix("4+5*6/7");
	return 0;
}

Code runs in O(N) time with O(N) space complexity.

Test cases

1. (4+8)*(6-5)/((3-2)*(2+2)) 
4 8 + 6 5 - * 3 2 - 2 2 + */

2. 4+8/7*8
487/8*+

3. 4
4

4. +
+ (No validation on expression).

Please share if there is something wrong or missing. If you are interested in contributing to website, please contact us.

  • DasBlues

    You are completely wrong. Time complexity should be O(n^2). In fact, your code is wrong. Firstly you close the brace of your function “infix_to_postifx” at the wrong position and moreover your program don’t have the necessary mechanism to traverse the whole string.

    • http://algorithmsandme.com/ Jitendra Sangar

      I have updated the post, thanks for pointing out. I understand that traversing of stack inside while loop may have complexity of O(n) and if it happens for each operation, worst case complexity may go O(n2). Regarding the code I am in process of migrating all codes to ideone, so that at least compilation part and basic cases work for code published on blog. So, please bear with me till the time migration happens, I would love to hear from you if you find any other mistakes in code published. Thanks!

  • Pingback: Stack data structure c implemetation - Algorithms and Me()