/*
Name: bhavna kapoor 
Description: This program accepts an infix expression with single-variable inputs , converts the same to corresponding prefix or postfost forms and then evaluates these expressions by accepting the values of the variables from the user. 
*/

/*-------------------------------------------------------------------- 
EXPRESSION CONVERSION AND EVALUATION 

---------------------------------------------------------------------*/ 

/* 
top = indicates top of operator or operand stack. 
MAXSIZE = maximum size of the stack and the expression. 
arr[MAXSIZE] = array used to implement either stack. 
prefix[] 
postfix[] 
infix[] = strings to store expression. 
underflow = flag to indicate stack empty. 
temp = temporary variable to store element while 
traversing an infix, postfix or prefix string. 
flag = variable which indicates infix-postfix conversion 
(when flag=0) and infix-prefix conversion (when 
flag=1). 
x = variable to store popped element from a stack. 
variable[] = array to store the independent variables in an 
expression for evaluation. 
value[] = array to store the numerical values of the variables 
stored in variable[] array. Value[j] <-> Variable[j]. 
unary = flag which indicates presence of unary operator(~) 
during evaluation. 

Imp. Note1 :- Although we have used 'float' in the operand stack, 
we cannot directly scan any values into this float 
array. Hence, we declare a float value[] array in the 
evaluation subroutine into which we scan the required 
values and then transfer these to the operand stack 
float array. 

Imp. Note2 :- Whenever we convert the infix expression to prefix, 
we traverse the infix string from the right to the 
left as against the left->right traversal in infix- 
to-postfix conversion. The elements are inserted into 
the prefix string from the right too. Even while 
evaluating prefix expression, we follow right->left 
traversal. 
*/ 

#include <stdio.h> 
#include <conio.h> 
#include <math.h> 
#include <stdlib.h> 
#include <string.h> 
#define MAXSIZE 50 
#define TRUE 1 
#define FALSE 0 

/*-----------------------STRUCTURE DECLARATION-------------------------*/ 
struct operandstack 
{ 
int top; 
float arr[MAXSIZE]; 
}; 

struct operatorstack 
{ 
int top; 
char arr[MAXSIZE]; 
}; 
/*---------------------------------------------------------------------*/ 

/*----------------------FUNCTION DECLARATION---------------------------*/ 

int isanoper(char x); 
int validity2(char infix[]); 
int empty1(struct operatorstack *s1); 
int pop1(struct operatorstack *s1); 
float pop2(struct operandstack *s2); 
void push1(struct operatorstack *s1, char x ); 
void push2(struct operandstack *s2, float x ); 
int validity1(struct operatorstack *s1,char infix[] ); 
int check(char temp); 
int precedence1( char x, char y, int flag); 
void evaluate( char postfix[]); 
void evaluate2( char prefix[]); 
float calculate( float operand1, float operand2, char temp,int fl); 
void post_fix(struct operatorstack *s1,char infix[], char postfix[], int flag); 
void poptest1(struct operatorstack *s1,char *temp, int *underflow); 
void pre_fix(struct operatorstack *s1, char infix[], char prefix[], int flag); 

/*--------------------------------------------------------------------------*/ 


/*-----------------------MAIN-----------------------------------------------*/ 
main() 
{ 
char infix[MAXSIZE]={'A'}, postfix[MAXSIZE]={'A'}, prefix[MAXSIZE]={'A'}; 
int q,p,ch,i; 
struct operatorstack opstack1; 
while(TRUE) 
{ 
clrscr(); 
printf("\n\n Enter the infix expression:\n"); 
scanf("%s", infix); 
p=validity1(&opstack1, infix); 
if (p==0) 
{ 
printf ("\n Sorry, expression is invalid from parenthesis point of view."); 
getch(); 
exit(0); 
} 
q=validity2(infix); 
if (q==0) 
{ 
printf ("\n Sorry, expression is invalid from operator/operand point of view."); 
getch(); 
exit(0); 
} 
printf("\n Expression is valid.\n"); 
do 
{ 
printf("\n What would you like to do with this expression?"); 
printf("\n"); 
printf("\n 1.Convert it to Postfix."); 
printf("\n 2.Convert it to Prefix."); 
printf("\n 3.Evaluate Postfix."); 
printf("\n 4.Evaluate Prefix."); 
printf("\n 5.Exit."); 
printf("\n Enter choice:"); 
scanf("%d", &ch); 

switch(ch) 
{ 
case 1: post_fix(&opstack1,infix,postfix, 0); 
break; 
case 2: pre_fix(&opstack1,infix,prefix,0); 
break; 
case 3: post_fix(&opstack1, infix, postfix, 1); 
break; 
case 4: pre_fix(&opstack1,infix,prefix,1); 
break; 
case 5: exit(1); 
} 
}while (ch!=6); 
getch(); 
} 
} 
/*--------------------------------------------------------------------*/ 


/*---------------------VALIDITY OF PARENTHESIS------------------------*/ 

int validity1( struct operatorstack *s1, char infix[]) 
{ 
int i; 
char x; 
s1->top=-1; 
for (i=0; infix[i]!='\0'; i++) 
{ 
if (infix[0]==')' || infix[0]==']' || infix[0]=='}') 
return(0); 
if (infix[i]=='(') 
push1(s1,')'); 
if (infix[i]=='{') 
push1(s1,'}'); 
if (infix[i]=='[') 
push1(s1,']'); 
if (infix[i]==')' || infix[i]=='}' || infix[i]==']') 
{ 
if ((x=pop1(s1)) !=infix[i]) 
return (0); 
} 
} 
if (infix[i]=='[' || infix[i]=='{' || infix[i]=='(') 
return(0); 
if (!empty1(s1)) 
return(0); 
else 
return(1); 
} 
/*--------------------------------------------------------------------*/ 

/*-----------------------VALIDITY OF OPERATOR/OPERAND-----------------*/ 

int validity2(char infix[]) 
{ 
int i,j; 
char x; 
int p,q; 
for (j=0,i=1; infix[i]!='\0';j++, i++) 
{ 
p=check(infix[j]); 
q=check(infix[i]); 
if ((p==1 && q==1) || (p==2 && q==2) || (p==3 && q==3) || (p==4 && q==4)) 
return(0); 
if (j==0 && (p==2 || p==4)) 
return(0); 
if ((p==2 && q!=4) || (p==1 && q!=3) || (q==2 && p!=3) || (q==1 && p!=4)) 
return(0); 
if (p==5 && (q==2 || q==4 || q==5)) 
return(0); 
} 
return(1); 
} 
/*---------------------------------------------------------------------*/ 

/*-------------TO CHECK FOR OPERATOR/OPERAND/PARENTHESIS---------------*/ 

int check( char temp) 
{ 
if (temp=='(' || temp=='{' || temp=='[' ) 
return(1); /* Opening Parenthesis */ 
if (temp==')' || temp=='}' || temp==']') 
return(2); /* Closing Parenthesis */ 
if (temp>=97 && temp<=122) 
return(3); /* Operand */ 
if (temp==126) 
return(5); /* Unary Operator */ 
else 
return(4); /* Operator */ 

} 
/*---------------------------------------------------------------------*/ 

/*----------------------TO CHECK FOR OPERATOR/OPERAND------------------*/ 
int isanoper( char temp) 
{ 
if ((temp<97 || temp>122) && temp!=126) 
return(1); 
else 
return(0); 
} 
/*--------------------------------------------------------------------*/ 

/*------------------------PRECEDENCE OF OPERATOR----------------------*/ 
int precedence1( char x, char y, int flag) 
{ 
switch(x) 
{ 
case '+': 
case '-': if (flag==0) 
{ 
if (y=='+' || y=='-'|| y=='*' || y=='/' || y=='{' || y=='[' || y=='(') 
return(FALSE); 
} 
else 
{ 
if (y=='+' || y=='-'||y=='*' || y=='/' || y=='}' || y==']' || y==')') 
return(FALSE); 
} 
break; 

case '*': 
case '/': if (y=='+' || y=='-' ) 
return(TRUE); 
if (flag==0) 
{ 
if (y=='*' || y=='/'|| y=='$' || y=='(' || y=='{' || y=='[') 
return(FALSE); 
} 
else 
{ 
if (y=='*' || y=='/'|| y==')' || y=='}' || y==']') 
return(FALSE); 
} 
break; 


case '$': if (y=='+' || y=='-' || y=='*' || y=='/') 
return(TRUE); 
if (flag==0) 
{ 
if (y=='(' || y=='{' || y=='[') 
return(FALSE); 
} 
else 
{ 
if (y==']' || y=='}' || y==')') 
return(FALSE); 
} 
break; 
} 
if (flag==0) 
{ 
if (x=='(' && y!=')') 
return(0); 
if (x=='[' && y!=']') 
return(0); 
if (x=='{' && y!='}') 
return(0); 
if ((x=='(' && y==')') || (x=='[' && y==']') || (x=='{' && y=='}')) 
return(0); 
if (y==')' || y==']' || y=='}') 
return(1); 
} 
else 
{ 
if (x==')' && y!='(') 
return(0); 
if (x==']' && y!='[') 
return(0); 
if (x=='}' && y!='{') 
return(0); 
if ((x==')' && y=='(') || (x==']' && y=='[') || (x=='}' && y=='{')) 
return(0); 
if (y==')' || y==']' || y=='}') 
return(1); 
} 
} 
/*--------------------------------------------------------------------*/ 


/*-------------------INFIX TO POSTFIX CONVERSION----------------------*/ 
void post_fix(struct operatorstack *s1, char infix[], char postfix[], int flag) 
{ 
int i=0,k=0,underflow; 
char temp, x; 
postfix[0]='\0'; 
s1->top=-1; 
while (infix[i]!='\0') 
{ 
temp=infix[i]; 
if (isanoper(temp)) 
{ 
poptest1(s1,&x, &underflow); 
while(underflow==0 && precedence1(x,temp,0)) 
{ 
postfix[k]=x; 
k++; 
x=pop1(s1); 
push1(s1,temp); 
poptest1(s1,&temp, &underflow); 
} 
if (underflow==0) 
push1(s1,x); 
if (underflow==1 || (temp!=')' && temp!=']' && temp!='}')) 
push1(s1,temp); 
else 
x=pop1(s1); 
} 
else 
{ 
postfix[k]=infix[i]; 
k++; 
} 
i++; 
} 
while(!empty1(s1)) 
{ 
x=pop1(s1); 
if (x!='(' && x!='[' && x!='{') 
{ 
postfix[k]=x; 
k++; 
} 
else if (x=='(' || x=='[' || x=='{') 
k--; 
} 
postfix[k]='\0'; 
if (flag==0) 
{ 
printf("\n Postfix expression is %s", postfix); 
getch(); 
return; 
} 
evaluate(postfix); 
} 
/*--------------------------------------------------------------------*/ 

/*-------------------INFIX TO PREFIX CONVERSION-----------------------*/ 
void pre_fix(struct operatorstack *s1, char infix[], char prefix[], int flag) 
{ 
int i, k=0, j=0, underflow,size; 
char t, temp, x; 
prefix[0]='\0'; 
i=strlen(infix)-1; /* This is the size of infix string, 
inclusive of parenthesis */ 
s1->top=-1; 
t=infix[j]; 
while (t!='\0') 
{ 
if ( t==']' || t==')' || t=='}' || t=='[' || t=='(' || t=='{') 
k++; /* This counts no. of parenthesis in infix string */ 
j++; 
t=infix[j]; 
} 
k=i-k; 
size=k; /* This is the size of prefix string*/ 
while (i>=0) 
{ 
temp=infix[i]; /* Last element of infix string*/ 
if (isanoper(temp)) 
{ 
poptest1(s1, &x, &underflow); 
while( !underflow && precedence1(x, temp,1)) 
{ 
prefix[k]=x; 
k--; 
poptest1(s1,&x, &underflow); 
} 
if (underflow!=1) 
push1(s1,x); 
if (underflow || (temp!='(' && temp!='[' && temp!='{')) 
push1(s1,temp); 
else 
x=pop1(s1); 
} 
else 
{ 
prefix[k]=infix[i]; 
k--; 
} 
i--; 
} 
while(!empty1(s1)) 
{ 
x=pop1(s1); 
if (x!=')' && x!=']' && x!='}') 
{ 
prefix[k]=x; 
k--; 
} 
else 
k++; 
} 
prefix[size+1]='\0'; 
if (flag==0) 
{ 
printf("\n Prefix expression is %s", prefix); 
getch(); 
return; 
} 
else 
evaluate2(prefix); 
} 
/*--------------------------------------------------------------------*/ 

/*--------------------EMPTY STACK-------------------------------------*/ 
int empty1(struct operatorstack *s1) 
{ 
if (s1->top==-1) 
return(TRUE); 
else 
return(FALSE); 
} 

int empty2(struct operandstack *s2) 
{ 
if (s2->top==-1) 
return(TRUE); 
else 
return(FALSE); 
} 
/*--------------------------------------------------------------------*/ 

/*-------------------PUSH ONTO STACK---------------------------------*/ 
void push1(struct operatorstack *s1, char x) 
{ 
s1->arr[++s1->top]=x; 
return; 
} 

void push2(struct operandstack *s2, float x) 
{ 
s2->arr[++s2->top]=x; 
return; 
} 
/*--------------------------------------------------------------------*/ 


/*---------------------POP FROM STACK---------------------------------*/ 
int pop1(struct operatorstack *s1) 
{ 
char v; 
if (empty1(s1)) 
{ 
printf("\n Sorry, Stack is empty hence cannot pop"); 
getch(); 
exit(0); 
} 
return(v=s1->arr[s1->top--]); 
} 

float pop2(struct operandstack *s2) 
{ 
if (empty2(s2)) 
{ 
printf("\n Sorry, Stack is empty hence cannot pop"); 
getch(); 
exit(0); 
} 
return(s2->arr[s2->top--]); 
} 
/*--------------------------------------------------------------------*/ 

/*---------------------POP AND TEST-----------------------------------*/ 
void poptest1(struct operatorstack *s1,char *temp,int *underflow) 
{ 
if (empty1(s1)) 
{ 
*underflow=1; 
return; 
} 
*temp=s1->arr[(s1->top)--]; 
*underflow=0; 
} 
/*--------------------------------------------------------------------*/ 


/*-------------------EVALUATION OF POSTFIX EXPRESSION---------------*/ 
void evaluate(char postfix[]) 
{ 
struct operandstack opstack2; 
char variable[MAXSIZE], temp; 
float value[MAXSIZE], operand1, operand2, val; 
int i=0, j=0, k=0, flag,unary=0; 
while (postfix[i]!='\0') /* To find number of independent variables*/ 
{ 
if (!isanoper(postfix[i]) && postfix[i]!='~') 
{ 
flag=1; 
for (j=0; j<i; j++) 
{ 
if (variable[j]==postfix[i]) 
{ 
flag=0; 
break; 
} 
} 
if (flag==1) 
variable[k++]=postfix[i]; 
} 
i++; 
} 
for (i=0; i<k; i++) 
{ 
printf("\n Enter the value of %c:", variable[i]); 
scanf("%f", &value[i]); 
} 
opstack2.top=-1; 
i=0; 
while (postfix[i]!='\0') 
{ 
temp=postfix[i]; 
if (temp=='~') 
unary=1; 
else if (!isanoper(temp) && temp!='~') 
{ 
for (j=0; variable[j]!=temp; j++); 
if (unary==0) 
push2(&opstack2, value[j]); 
else 
{ 
push2(&opstack2, -(value[j])); 
unary=0; 
} 
} 
else if (isanoper(temp)) 
{ 
operand2=pop2(&opstack2); 
operand1=pop2(&opstack2); 
val=calculate(operand1, operand2, temp,1); 
push2(&opstack2, val); 
} 
i++; 
} 
val=pop2(&opstack2); 
printf("\n Postfix expression is %s ", postfix); 
printf("\n The result is %f", val); 
getch(); 
return; 
} 
/*--------------------------------------------------------------------*/ 

/*-------------------EVALUATION OF PREFIX EXPRESSION---------------*/ 
void evaluate2(char prefix[]) 
{ 
struct operandstack opstack2; 
char variable[MAXSIZE], temp; 
float value[MAXSIZE], operand1, operand2, val; 
int i=0, j=0, k=0, flag, unary=0; 
while (prefix[i]!='\0') /* To find number of independent variables*/ 
{ 
if (!isanoper(prefix[i]) && prefix[i]!='~') 
{ 
flag=1; 
for (j=0; j<i; j++) 
{ 
if (variable[j]==prefix[i]) 
{ 
flag=0; 
break; 
} 
} 
if (flag==1) 
variable[k++]=prefix[i]; 
} 
i++; 
} 
for (i=0; i<k; i++) 
{ 
printf("\n Enter the value of %c:", variable[i]); 
scanf("%f", &value[i]); 
} 
opstack2.top=-1; 
i=strlen(prefix)-1; 
while (i>=0) 
{ 
temp=prefix[i]; 
if (!isanoper(temp)) 
{ 
if (i!=0 && prefix[i-1]=='~') 
{ 
unary=1; 
i--; 
} 
for (j=0; variable[j]!=temp; j++); 
if (unary==0) 
push2(&opstack2, value[j]); 
else if (unary==1) 
{ 
push2(&opstack2, -(value[j])); 
unary=0; 
} 
} 
else if (isanoper(temp)) 
{ 
operand2=pop2(&opstack2); 
operand1=pop2(&opstack2); 
val=calculate(operand1, operand2, temp,0); 
push2(&opstack2, val); 
} 
i--; 
} 
val=pop2(&opstack2); 
printf("\n The result is %f", val); 
getch(); 
return; 
} 
/*--------------------------------------------------------------------*/ 


/*----------------------CALCULATION-----------------------------------*/ 
float calculate( float operand1, float operand2, char temp, int fl) 
{ 
if (fl==0) 
{ 
switch(temp) 
{ 
case '-' : return( operand2 - operand1); 

case '+' : return( operand1 + operand2); 

case '*' : return ( operand1 * operand2); 

case '/' : return (operand2 / operand1); 

case '$' : return(pow(operand2, operand1)); 
} 
} 
else if (fl==1) 
{ 
switch(temp) 
{ 
case '-' : return( operand1 - operand2); 

case '+' : return( operand1 + operand2); 

case '*' : return ( operand1 * operand2); 

case '/' : return (operand1 / operand2); 

case '$' : return(pow(operand1, operand2)); 
} 
} 
} 
/*--------------------------------------------------------------------*/