/* program for conversion of:
1. infix into its postfix form
2. infix into its prefix form
3. Evaluation of postfix expression
4. Evaluation of prefix expression
operators supported '+,-,*,/,%,^,(,)
operands supported -- all single character operands
*/
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define MAX 50
typedef struct stack
{
int data[MAX];
int top;
}stack;
int precedence(char);
void init(stack *);
int empty(stack *);
int full(stack *);
int pop(stack *);
void push(stack *,int );
int top(stack *); //value of the top element
void infix_to_prefix(char infix[],char prefix[]);
void infix_to_postfix(char infix[],char postfix[]);
void eval_prefix(char prefix[]);
void eval_postfix(char postfix[]);
int evaluate(char x,int op1,int op2);
void main()
{ char infix[30],postfix[30],prefix[30];
clrscr();
printf("\nEnter an infix expression : ");
gets(infix);
infix_to_postfix(infix,postfix);
infix_to_prefix(infix,prefix);
printf("\nPostfix : %s\n prefix: %s ",postfix,prefix);
printf("\nPrefix Evaluation : ");
eval_prefix(prefix);
printf("\nPostfix evaluation : ");
eval_postfix(postfix);
getch();
}
void infix_to_prefix(char infix[],char prefix[])
{ int i,j;
char temp,in1[30];
// reverse the infix expression and store it in in1[]
for(i=strlen(infix)-1,j=0;i>=0;i--,j++)
in1[j]=infix[i];
in1[j]='\0';
// reverse the direction of brackets
for(i=0;in1[i]!='\0';i++)
{
if(in1[i]=='(')
in1[i]=')';
else
if(in1[i]==')')
in1[i]='(';
}
// convert from infix to postfix
infix_to_postfix(in1,prefix);
//reverse the final expression
for(i=0,j=strlen(prefix)-1;i<j;i++,j--)
{
temp=prefix[i];
prefix[i]=prefix[j];
prefix[j]=temp;
}
}
void infix_to_postfix(char infix[],char postfix[])
{ stack s;
char x;
int i,j;//i-index for infix[],j-index for postfix
char token;
init(&s);
j=0;
for(i=0;infix[i]!='\0';i++)
{ token=infix[i];
if(isalnum(token))
postfix[j++]=token;
else
if(token == '(')
push(&s,'(');
else
if(token == ')')
while((x=pop(&s))!='(')
postfix[j++]=x;
else
{
while(precedence(token)<=precedence(top(&s)) && !empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
push(&s,token);
}
}
while(!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
postfix[j]='\0';
}
void eval_postfix(char postfix[])
{
stack s;
char x;
int op1,op2,val,i;
init(&s);
for(i=0;postfix[i]!='\0';i++)
{ x=postfix[i];
if(isalpha(x))
{ printf("\nEnter the value of %c : ",x);
scanf("%d",&val);
push(&s,val);
}
else
{ //pop two operands and evaluate
op2=pop(&s);
op1=pop(&s);
val=evaluate(x,op1,op2);
push(&s,val);
}
}
val=pop(&s);
printf("\nvalue of expression = %d",val);
}
void eval_prefix(char prefix[])
{
stack s;
char x;
int op1,op2,val,i;
init(&s);
for(i=strlen(prefix)-1;i>=0;i--)
{ x=prefix[i];
if(isalpha(x))
{ printf("\nEnter the value of %c : ",x);
scanf("%d",&val);
push(&s,val);
}
else
{ //pop two operands and evaluate
op1=pop(&s);
op2=pop(&s);
val=evaluate(x,op1,op2);
push(&s,val);
}
}
val=pop(&s);
printf("\nvalue of expression = %d",val);
}
int evaluate(char x,int op1,int op2)
{
if(x=='+') return(op1+op2);
if(x=='-') return(op1-op2);
if(x=='*') return(op1*op2);
if(x=='/') return(op1/op2);
if(x=='%') return(op1%op2);
}
int precedence(char x)
{
if(x == '(') return(0);
if(x == '+' || x == '-') return(1);
if(x == '*' || x == '/' || x == '%') return(2);
return(3);
}
void init(stack *s)
{
s->top=-1;
}
int empty(stack *s)
{
if(s->top==-1) return(1);
return(0);
}
int full(stack *s)
{
if(s->top==MAX-1) return(1);
return(0);
}
void push(stack *s,int x)
{
s->top=s->top+1;
s->data[s->top]=x;
}
int pop(stack *s)
{
int x;
x=s->data[s->top];
s->top=s->top-1;
return(x);
}
int top(stack * p)
{
return(p->data[p->top]);
}
1. infix into its postfix form
2. infix into its prefix form
3. Evaluation of postfix expression
4. Evaluation of prefix expression
operators supported '+,-,*,/,%,^,(,)
operands supported -- all single character operands
*/
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define MAX 50
typedef struct stack
{
int data[MAX];
int top;
}stack;
int precedence(char);
void init(stack *);
int empty(stack *);
int full(stack *);
int pop(stack *);
void push(stack *,int );
int top(stack *); //value of the top element
void infix_to_prefix(char infix[],char prefix[]);
void infix_to_postfix(char infix[],char postfix[]);
void eval_prefix(char prefix[]);
void eval_postfix(char postfix[]);
int evaluate(char x,int op1,int op2);
void main()
{ char infix[30],postfix[30],prefix[30];
clrscr();
printf("\nEnter an infix expression : ");
gets(infix);
infix_to_postfix(infix,postfix);
infix_to_prefix(infix,prefix);
printf("\nPostfix : %s\n prefix: %s ",postfix,prefix);
printf("\nPrefix Evaluation : ");
eval_prefix(prefix);
printf("\nPostfix evaluation : ");
eval_postfix(postfix);
getch();
}
void infix_to_prefix(char infix[],char prefix[])
{ int i,j;
char temp,in1[30];
// reverse the infix expression and store it in in1[]
for(i=strlen(infix)-1,j=0;i>=0;i--,j++)
in1[j]=infix[i];
in1[j]='\0';
// reverse the direction of brackets
for(i=0;in1[i]!='\0';i++)
{
if(in1[i]=='(')
in1[i]=')';
else
if(in1[i]==')')
in1[i]='(';
}
// convert from infix to postfix
infix_to_postfix(in1,prefix);
//reverse the final expression
for(i=0,j=strlen(prefix)-1;i<j;i++,j--)
{
temp=prefix[i];
prefix[i]=prefix[j];
prefix[j]=temp;
}
}
void infix_to_postfix(char infix[],char postfix[])
{ stack s;
char x;
int i,j;//i-index for infix[],j-index for postfix
char token;
init(&s);
j=0;
for(i=0;infix[i]!='\0';i++)
{ token=infix[i];
if(isalnum(token))
postfix[j++]=token;
else
if(token == '(')
push(&s,'(');
else
if(token == ')')
while((x=pop(&s))!='(')
postfix[j++]=x;
else
{
while(precedence(token)<=precedence(top(&s)) && !empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
push(&s,token);
}
}
while(!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
postfix[j]='\0';
}
void eval_postfix(char postfix[])
{
stack s;
char x;
int op1,op2,val,i;
init(&s);
for(i=0;postfix[i]!='\0';i++)
{ x=postfix[i];
if(isalpha(x))
{ printf("\nEnter the value of %c : ",x);
scanf("%d",&val);
push(&s,val);
}
else
{ //pop two operands and evaluate
op2=pop(&s);
op1=pop(&s);
val=evaluate(x,op1,op2);
push(&s,val);
}
}
val=pop(&s);
printf("\nvalue of expression = %d",val);
}
void eval_prefix(char prefix[])
{
stack s;
char x;
int op1,op2,val,i;
init(&s);
for(i=strlen(prefix)-1;i>=0;i--)
{ x=prefix[i];
if(isalpha(x))
{ printf("\nEnter the value of %c : ",x);
scanf("%d",&val);
push(&s,val);
}
else
{ //pop two operands and evaluate
op1=pop(&s);
op2=pop(&s);
val=evaluate(x,op1,op2);
push(&s,val);
}
}
val=pop(&s);
printf("\nvalue of expression = %d",val);
}
int evaluate(char x,int op1,int op2)
{
if(x=='+') return(op1+op2);
if(x=='-') return(op1-op2);
if(x=='*') return(op1*op2);
if(x=='/') return(op1/op2);
if(x=='%') return(op1%op2);
}
int precedence(char x)
{
if(x == '(') return(0);
if(x == '+' || x == '-') return(1);
if(x == '*' || x == '/' || x == '%') return(2);
return(3);
}
void init(stack *s)
{
s->top=-1;
}
int empty(stack *s)
{
if(s->top==-1) return(1);
return(0);
}
int full(stack *s)
{
if(s->top==MAX-1) return(1);
return(0);
}
void push(stack *s,int x)
{
s->top=s->top+1;
s->data[s->top]=x;
}
int pop(stack *s)
{
int x;
x=s->data[s->top];
s->top=s->top-1;
return(x);
}
int top(stack * p)
{
return(p->data[p->top]);
}
2 Comments
Hi,
ReplyDeleteI have tried these two expression but the output not correct.
1.(9-(((7-3)*(8-5))/3)+4)
2.((3-5)*(8+6))/(9-4).this one shows the prefix and post fix expression correctly but shows prefix evaluation as Abnormal Program Termination.Please help I have an exam tomorrow.
Try this code. This code is for infix to postfix.
DeleteFor anything else , reply back
#include
#include
#define MAX 50
char post[MAX],in[MAX],stack[MAX];
int top=-1,toper=-1;
void insertpostfix(char x);
void insertstack(char x);
void popstack(char x);
int checkprec(char x);
void pop_all();
void main()
{
int i,j,chk,chk2;
clrscr();
printf("\nInsert an infix notation :: ");
gets(in);
stack[++toper]='(';
in[strlen(in)]=')';
printf("\nCharacter\tStack\tPostfix\n");
for(i=0;i='a' && in[i]<='z' || in[i]>='A' && in[i]<='Z' || in[i]>='0'
&& in[i]<='9')
{
insertpostfix(in[i]);
}
else if(in[i]=='(')
{
insertstack(in[i]);
}
else if(in[i]=='+' || in[i]=='-' || in[i]=='/' || in[i]=='*' || in[i]
=='^')
{
chk=checkprec(in[i]);
chk2=checkprec(stack[toper]);
if(chk>chk2)
{
insertstack(in[i]);
}
else
{
popstack(in[i]);
}
}
else if(in[i]==')')
{
pop_all();
}
printf("\n%c\t\t",in[i]);
printf("%s",stack);
printf("\t%s",post);
}
printf("\n\nFinal Postfix Notation :: %s",post);
getch();
}
void insertpostfix(char x)
{
top++;
post[top]=x;
}
void insertstack(char x)
{
toper++;
stack[toper]=x;
}
void popstack(char x)
{
top++;
post[top]=stack[toper];
stack[toper]=x;
}
void pop_all()
{
while(stack[toper]!='(')
{
top++;
post[top]=stack[toper];
stack[toper]='\0';
toper--;
}
stack[toper]='\0';
toper--;
}
int checkprec(char x)
{
switch(x)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
case '(':
return 0;
default:
return 0;
z}
}