# 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:

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 (+, *).

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 (+,*, /).

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).
```