APPLICATION OF STACK ADT – CONVERSION OF INFIX TO POSTFIX EXPRESSION

SOURCE CODE:

“Iexp.h” File:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define MAX 10
struct stack
{
   int capacity,size,top;
   char *array;
};
typedef struct stack *STACK;
STACK create()
{
   STACK s;
   s=(struct stack*)malloc(sizeof(struct stack));
   s->capacity=MAX;
   s->size=0;
   s->top=-1;
   s->array=(char*)malloc(sizeof(char)*MAX);
   return s;
}

void push(char x,STACK s)
{
   if(s==NULL)
      printf("not yet created");
   else if(s->size==s->capacity)
      printf("stack is full");
   else
   {
      s->top++;
      s->array[s->top]=x;
      s->size++;
   }
}

char pop(STACK s)
{
   int t;
   if(s==NULL)
      printf("not yet created");
   else if(s->top==-1)
      printf("stack is empty");
   else
   {
      t=s->top;
      s->top--;
      s->size--;
   }
   return s->array[t];
}

“Infix.h” File:

#include<stdio.h>
#include"Iexp.h"
#define max 9
char ip[max][2]={{'(',max},{')',0},{'\0',0},{'+',1},{'-',1},{'*',2},{'/',3},{'%',4},{'^',5}};
char sp[max][2]={{'(',-1},{')',0},{'\0',0},{'+',1},{'-',1},{'*',2},{'/',3},{'%',4},{'^',5}};
int indexpriority(char p[][2],char data)
{
   int i;
   for(i=0;i<max;i++)
   {
      if(p[i][0]==data)
      return i;
   }
   return 0;
}
void intopost( char instr[],char poststr[])
{
  STACK s=NULL;
  char ch,item;
  int i=0,st=0,spr,ipr;
  s=create();
  push('\0',s);
  while((ch=instr[st++])!=NULL)
  {
    if(tolower(ch)>='a'&& tolower(ch)<='z')
      poststr[i++]=ch;
    else if(ch=='(')
      push(ch,s);
    else if(ch==')')
    {
      item=pop(s);
      while(item!='(')
      {
    poststr[i++]=item;
    item=pop(s);
      }
    }
    else
    {
      item=pop(s);
      spr=indexpriority(sp,item);
      ipr=indexpriority(ip,ch);
      while(sp[spr][1]>=ip[ipr][1])
       {
    poststr[i++]=item;
    item=pop(s);
    spr=indexpriority(sp,item);
      }
    push(item,s);
    push(ch,s);
    }
  }
  while(s->top!=-1)
  {
    item=pop(s);
    poststr[i++]=item;
  }
}

“Infix.c” File:

#include"infix.h"
void main()
{
char instr[20],poststr[20];
clrscr();
printf("\n Enter the infix expression...\n");
scanf("%s",&instr);
intopost(instr,poststr);
printf("\n The postfix expression of %s",poststr);
getch();
}

OUTPUT:

Enter the Infix Expression:    a+b*c+(d*e+f)*g

The postfix Expression:    abc*+de*f+g*+
Previous
Next Post »

If you still didn't find what you're looking for, you can search this website below: