Converting Postfix Expression to Prefix Expression and Infix Expression in C

In prefix expression, the operator comes before the operands where as in postfix expression, the operator comes in the end. So to convert a postix expression to a prefix expression, we just have to 

bring the operator in the front for each sub expression.

For doing this we use a stack that stores a 2D character array. We can visualize it like a 1D character array that stores operands. The push operation pushes an operand to the stack and the pop operation returns a pointer to the last operand.

First push the operands on to the stack until an operator is encountered. When an operator is encountered we pop the last two operands and create a new character array.

 Now if we want to convert to infix expression then we store the first operand then the operator and then the second operand. Similarly for prefix expression we first store the operator and then the two operands in order.We then push this newly created character array to the stack.

The logic is that the character array that we pushed will now act as an operand for further operations.

The source code for prefix expression is given below.

//created by Aditya Vijayvergia
//uploaded on thecodingedge.blogspot.com
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define size 20
struct stack
{
  char data[size][size];
  int top;
}s;
void push(char x[20])
{
  int i;
  s.top++;
  for(i=0;i<strlen(x);i++)
   s.data[s.top][i]=x[i];
}
char* pop()
{
char *p;
if(s.top==-1)
  return NULL;
return s.data[s.top--];
}

void main()
{
  char q[50],c[50];
  char *a,*b;
  int i,j,a1,b1;
  s.top=-1;
  clrscr();
  printf("\nenter postfix expression:");
  gets(q);
  for(j=0;j<strlen(q);j++)
  {
  if(q[j]>='a'&&q[j]<='z')
    {
    s.data[++s.top][0]=q[j];
    //printf("\npush %c",q[j]);
    }
  else
  {
  b=pop();
  a=pop();
  //printf("\na=%s\tb=%s",a,b);
  c[0]=q[j];
  a1=strlen(a);
  b1=strlen(b);
  for(i=0;i<a1;i++)
    {
    c[i+1]=*a;
    a++;
    }
  for(i=0;i<b1;i++)
    {
    c[a1+i+1]=*b;
    b++;
    }
  push(c);
  //printf("\npushed operand %s",c);
  }
  a=NULL;
  b=NULL;
  }
  printf("\n\nPrefix expression : %s",pop());
  getch();
}