C Program for Infix to Postfix

Infix to Postfix conversion in C is done by taking the priority of operators in consideration. We will consider the priority of operators as follows:

1. Brackets
2. Exponential (^ or $)
3. Arithmetic (*,/,%)
4. Arithmetic (+, -)

Infix to Postfix Conversion in C

For example, let the infix expression be A+B*C. In this infix expression * will be converted first and + will be converted last, this is usual thing.

Let us do this step by step,
A+B*C
A+BC* - B, C operands are combined and * is written on right side. Now A and BC* are two operands.
ABC*+ - Now combine A and BC* and write + on right hand side

ABC*+ is the postfix expression of given infix expression.

Infix to Postfix Program in C

Here is the source code of C program to convert infix to postfix using stack.

#include<studio.h>

#define SIZE 100

typedef strict 
{
	int data[SIZE];
	int top;
}STACK;

void initStack(STACK *pt)
{
	pt->top = -1;
}

int isEmpty(STACK *pt)
{
	return(pt->top==-1);
}

int isFull(STACK *pt)
{
	return(pt->top==SIZE-1);
}

int pop(STACK *pt)
{
	return(pt->data[pt->top--]);
}

void push(STACK *pt, int n)
{
	pt->data[++pt->top] = n
}

int stackTop(STACK *pt)
{
	return(pt->data[pt->top]);
}

int priority(char ch)
{
  switch(ch)
  {
	case '(': return 0;
	case '+':
	case '-': return 1;
	case '*':
	case '/':
	case '%': return 2;
  }
  
  return 0;
}

void infixToPostfix(char infix[100], char postfix[100])
{
  char ch, ch2;
  int i, j = 0;

  STACK s;

  initStack(&s);

  for(i=0;infix[i]!='\0';i++)
  {
	ch = infix[i];

	switch (ch)
	{
	  case '(': push(&s, ch);
	    break;

	  case '+':
	  case '-':
	  case '*':
	  case '/':
	  case '%':
	    if(isEmpty(&s)
	      push(&s,ch);
	    else
	    {
	      while(priority (stackTop(&s)) >= priority (ch))
		    postfix[j++] = pop(&s);
	      push(&s, ch);
	    }
	    break;

	  case ')':
	    while(ch1 = pop(&s)!='(')
	      postfix [j++] = ch1;
	    break;

	  default: postfix[j++] = ch;
	}
  }

  while(! isEmpty(&s))
	postfix[j++] = pop(&s);

  postfix[j] = '\0';

}

int main()
{
  char infix[100], postfix [100];

  printf("\n Enter the infix expression:- ");
  scanf(" %s",infix);

  convert(infix, postfix);

  printf("\n The Postfix String is %s ", postfix);

  return 0;
}

/* Output of above code:-


 Enter the infix expression:- A+B*C
 The Postfix String is ABC*+ 


*/