INFIX TO POSTFIX CONVERSION
The programme doesn’t check whether
the infix input is valid or not. The operators allowed are ‘^’, ’*’, ‘/’, ‘+’, ‘-‘
for exponential, multiplication, division, addition and subtraction
respectively. No brackets are allowed in the infix expression (otherwise
incorrect expression for postfix or run time crash)
#include<stdio.h>
#include<stdlib.h>
#define MAXCOLS 80
#define TRUE 1
#define FALSE 0
struct stack
{
int
top;
char
items[MAXCOLS];
};
void
postfix(char *,char *);
int
isoperand(char);
void
pop_test(struct stack *,char *,int *);
int
precedence(char,char);
void
push(struct stack *,char);
char
pop(struct stack *);
int empty(struct stack *);
int
main()
{
char
infix[MAXCOLS],postx[MAXCOLS],c;
int
pos=0;
printf("\nEnter
the infix expression:");
while((infix[pos++]=getchar())!='\n');
infix[--pos]='\0';
printf("\nThe
infix expression is:\n");
puts(infix);
postfix(infix,postx);
return
0;
}
int precedence(char op1,char op2)
{
switch(op1)
{
case
'^':
if(op2=='^')
return
(FALSE);
else
return
(TRUE);
break;
case
'*':
if(op2=='^')
return
(FALSE);
else
return
(TRUE);
break;
case
'/':
if(op2=='^')
return
(FALSE);
else
return
(TRUE);
break;
case
'+':
if(op2=='^'
|| op2=='*' ||op2=='/')
return
(FALSE);
else
return
(TRUE);
break;
case
'-':
if(op2=='^'
|| op2=='*' ||op2=='/')
return
(FALSE);
else
return
(TRUE);
break;
}
}
int isoperand(char symb)
{
if(symb
=='^' ||symb =='*' ||symb =='/' ||symb =='+' ||symb =='-')
return
(FALSE);
else
return
(TRUE);
}
void pop_test(struct stack *ps, char
*topsymp,int *und)
{
if(empty(ps))
{
*und=TRUE;
return;
}
*und=FALSE;
*topsymp=ps->items[ps->top--];
return;
}
void push(struct stack *ps, char x)
{
ps->items[++(ps->top)]=x;
}
char pop(struct stack *ps)
{
return
(ps->items[ps->top--]);
}
int empty(struct stack *ps)
{
if(ps->top==-1)
return
(TRUE);
else
return
(FALSE);
}
void postfix(char infix[],char postx[])
{
int
position,und;
int
outpos=0;
char
topsymb='+';
char
symb;
struct
stack opstk;
opstk.top=-1;
for(position=0;(symb=infix[position])!='\0';position++)
if(isoperand(symb))
postx[outpos++]=symb;
else
{
pop_test(&opstk,&topsymb,&und);
while(!und
&& precedence(topsymb,symb))
{
postx[outpos++]=topsymb;
pop_test(&opstk,&topsymb,&und);
}
if(!und)
push(&opstk,topsymb);
if(und
|| (symb!=')'))
push(&opstk,symb);
else
topsymb=pop(&opstk);
}
while(!empty(&opstk))
postx[outpos++]=pop(&opstk);
postx[outpos]='\0';
printf("\nThe
coressponding postfix expression is:");
puts(postx);
return;
}
No comments:
Post a Comment