INFIX TO POSTFIX CONVERSION & EVALUATION
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>
#include<math.h>
#define
MAXCOLS 80
#define
TRUE 1
#define
FALSE 0
struct
stack
{
int top;
char items[MAXCOLS];
};
struct
ostack
{
int top;
double items[MAXCOLS];
};
double eval(char[]);
double pop1(struct ostack *);
void push1(struct ostack *);
int isdigit(char);
double oper(int,double,double);
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
push1(struct ostack *ps, double x)
{
ps->items[++(ps->top)]=x;
}
void
push(struct stack *ps, char x)
{
ps->items[++(ps->top)]=x;
}
char
pop(struct stack *ps)
{
return (ps->items[ps->top--]);
}
double
pop1(struct ostack *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);
printf("\n The
value of the postfix expression is:%1.2f",eval(postx));
return;
}
double
eval(char postx[])
{
int c,position;
double opnd1,opnd2,value;
struct ostack opndstk;
opndstk.top=-1;
for(position=0;(c=postx[position])!='\0';
position++)
{
if(isdigit(c))
push1(&opndstk,(double)(c-'0'));
else
{
opnd2=pop1(&opndstk);
opnd1=pop1(&opndstk);
value=oper(c,opnd1,opnd2);
push1(&opndstk,value);
}
}
return(pop1(&opndstk));
}
double
oper(int symb,double op1,double op2)
{
switch(symb)
{
case '+':
return(op1+op2);
case '-':
return(op1-op2);
case '*':
return(op1*op2);
case '/':
return(op1/op2);
case '^':
return(pow(op1,op2));
}
}
int
isdigit (char symb)
{
return(symb>='0'
&& symb<='9');
}
No comments:
Post a Comment