Thursday 29 November 2012

Infix to postfix expression conversion algorithm


//Convert a expression infix to postfix
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>
#define  MAX 10
#define  EMPTY -1

struct stack
{
 char data[MAX];
 int top;
};

int isempty(struct stack *s)
{
 return (s->top == EMPTY) ? 1 : 0;
}

void emptystack(struct stack* s)
{
 s->top=EMPTY;
}

void push(struct stack* s,int item)
{
 if(s->top == (MAX-1))
 {
  printf("\nSTACK FULL");
 }
 else
 {
  ++s->top;
  s->data[s->top]=item;
 }
}

char pop(struct stack* s)
{
 char ret=(char)EMPTY;
 if(!isempty(s))
 {
  ret= s->data[s->top];
  --s->top;
 }
 return ret;
}

void display(struct stack s)
{
 while(s.top != EMPTY)
 {
  printf("\n%d",s.data[s.top]);
  s.top--;
 }
}

int isoperator(char e)
{
 if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%') return 1;
 else return 0;
}

int priority(char e)
{
 int pri = 0;
 if(e == '*' || e == '/' || e =='%') pri = 2;
 else
 {
  if(e == '+' || e == '-')
  pri = 1;
 }
 return pri;
}

void infix2postfix(char* infix, char * postfix, int insertspace)
{
 char *i,*p;
 struct stack X;
 char n1;
 emptystack(&X);
 i = &infix[0];
 p = &postfix[0];
 while(*i)
 {
  while(*i == ' ' || *i == '\t')
  {
   i++;
  }
  if( isdigit(*i) || isalpha(*i) )
  {
   while( isdigit(*i) || isalpha(*i))
   {
    *p = *i;
    p++;
    i++;
   }
   if(insertspace)
   {
    *p = ' ';
    p++;
   }
  }
   if( *i == '(' )
   {
    push(&X,*i);
    i++;
   }
   if( *i == ')')
   {
    n1 = pop(&X);
    while( n1 != '(' )
    {
     *p = n1;
     p++;
     if(insertspace)
     {
      *p = ' ';
      p++;
     }
     n1 = pop(&X);
    }
    i++;
   }
   if( isoperator(*i) )
   {
    if(isempty(&X))
    push(&X,*i);
    else
    {
     n1 = pop(&X);
     while(priority(n1) >= priority(*i))
     {
      *p = n1;
      p++;
      if(insertspace)
      {
       *p = ' ';
       p++;
      }
      n1 = pop(&X);
     }
     push(&X,n1);
     push(&X,*i);
    }
    i++;
   }
  }
  while(!isempty(&X))
  {
   n1 = pop(&X);
   *p = n1;
   p++;
   if(insertspace)
   {
    *p = ' ';
    p++;
   }
  }
 *p = '\0';
}

void main()
{
 clrscr();
 char in[50],post[50];
 strcpy(&post[0],"");
 printf("\nEnter Expression (Infix) : ");
 fflush(stdin);
 gets(in);
 infix2postfix(&in[0],&post[0],1);
 printf("Postfix Expression is : %s\n",&post[0]);
 getch();
}
//program written by Mars. 17/10/2012. Compiler lab.

No comments:

Post a Comment

You are welcome, your comment helps me to make this blog more better.