Infix to postfix conversion using stack

Infix to postfix conversion using stack

Let’s see one more problem which use stack in solution. Problem is to convert infix to postfix expression.
Infix expression is an expression where operator comes in between two operand. For example: A + B is an infix expression as operator + come in between two operands A and B. This is how we human being write and interpret expressions.
Postfix expression is where operator comes after operands like AB+C* is a postfix expression. This is how machines interpret and evaluate expressions.

Infix to postfix conversion : Line of thought

First thing we need to take care of while converting infix expression to postfix is precedence order of operators. Precedence order decides which operation happens in expression before others. For example, if expression is A + B * C, B * C is evaluated first before A+B as * as higher precedence over +.
Another example would be (A + B) * C, in this case A + B is evaluated first, as () has higher precedence over any other operator.

Let’s take an example and see how to convert an infix expression to postfix.

Infix -> A + B

We start with scanning each literal from the expression.As we have to put operator at the end, we will store operator when we see it and put it after operands. In this case, first we see A, we put this literal on output. So, current output would be A.
Next we see +, since it is an operator, we store it on storage. Next literal is B, we append it to output. Current output is AB. We finished scanning string, we will put all the operators on storage. So, the output will be AB+.

Let’s take another example, and see if we can come up with an algorithm.

Infix -> A + B * C

We scan the string, put A on output string. We put + on storage, and then put B on output. Again, we put * on to storage, and then operand C on to output string.
Now, we reached to the end of string, so we put all the operators on storage behind output string. But question is which order operators should be appended to output. If there is no precedence conflict, we should put the last seen operator first. So output will be ABC*+. There is important thing to be noted here : Last in first out pattern and to achieve that, we will use stack to store operators.

Infix to postfix conversion : Algorithm

Now, we know the data structure to use, there is one more thing to understand is how to deal with precedence order.Let’s take an example, and see how it works.

Infix -> A * B + C

Put A on to output, * on to stack, B again on to output. Everything same as above example. Next we see +, that’s where we have to worry. Operator on top of stack is * which has high precedence than +. It means A * B needs to be evaluated before C is added to the result. To achieve this, we will pop all operators from stack which have higher precedence than current operator and append it to output. After that, we will put + on to stack.Current output would be AB*
Append C to output, as we finished scanning string, we will pop all elements on stack and append it to output string. Hence, output would be AB*C+

Let’s apply this algorithm to an expression and see how it works. Expression is 4*5+6/7. Initial state of output and stack would be

Start with first digit 4, it is an operand onto output string.

Next character is *, push it on to stack.

Next is 5, not an operator, put it with 4 in output string, so current state of stack and output string will be as follows

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 *, so we will pop * from stack and put it on output string.

Next character is 6. Add it to postfix exp, it becomes 45*6 .

Now we encounter ‘/’. Since it has higher priority than + , it gets pushed to list.

Check 7 and add it to output postfix expression, 45*67.

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.

convert infix to postfix expression

Infix to postfix conversion : implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 23.9.18.
 */
public class InfixToPostfix {
    /* This function return true or false based on whether
        character is operator or not
    */
    public static boolean isOperator(char op){
        if(op == '+' || op == '-' || op == '*' || op == '/' || op =='%')
            return true;
        return false;
    }

    /* This function returns associated precedence to an operator */
    public static 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 */
    public static boolean isLowerPrecedence(char op1, char op2){
        if(precedence (op1) < precedence(op2))
            return true;
        return false;
    }
    public static String convertInixToPostfix(String infix){
        Stack<Character> stack = new Stack();
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<infix.length(); i++){
            char currentCharacter = infix.charAt(i);
            //If it's an operand, put it on output string
            if(!isOperator(currentCharacter)){
                sb.append(currentCharacter);
            }
            else{
                if(stack.empty()) stack.push(currentCharacter);
                else{
                    while(!stack.empty()
                    && isLowerPrecedence(currentCharacter, stack.peek())){
                        sb.append(stack.pop());
                    }
                    stack.push(currentCharacter);
                }
            }
        }
        while(!stack.empty()) sb.append(stack.pop());

        return sb.toString();
    }

    public static void main(String[] args){
        System.out.println(convertInixToPostfix("4*5+6/7"));
    }
}
#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== NULL) 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;
}

Complexity of algorithm to convert infix to postfix expression is O(n), along with O(m) space complexity, where m is number of operators in expression.

Please share if there is something wrong or missing. If you are interested in taking personal coaching from our experience coaches, please reach out to us at communications@algorithmsandme.com.