#ifndef MYSTACK_H
#define MYSTACK_H
#define STACK_SIZE 50
// stack datastructure
typedef struct stack
{
char data[STACK_SIZE];
int top;
} STACK;
typedef struct istack
{
float data[STACK_SIZE];
int top;
} ISTACK;
// stack function starts
void initstack(STACK *stack);
int push(STACK *stack, char ch);
char pop(STACK *stack);
int isempty(STACK *stack);
// stack function ends
// istack function starts
void initistack(ISTACK *stack);
int ipush(ISTACK *stack, float i);
float ipop(ISTACK *stack);
// istack function ends
///////////////Stack function starts
int isempty(STACK *stack)
{
if(stack->top == -1) return 1; // true
else return 0; // false
}
void initstack(STACK *stack)
{
strcpy(stack->data,""); // default initialization
stack->top = -1;
}
char pop(STACK *stack)
{
if (stack->top == -1)
return 0;
char c;
c = stack->data[stack->top];
stack->top -= 1;
return c;
}
int push(STACK *stack, char ch)
{
// inserts an element into the stack
stack->top += 1;
if(stack->top == STACK_SIZE)
{
stack->top -= 1; return -1; // error status
}
stack->data[stack->top] = ch; // assign data
return 0; // success
}
///////////////Stack function ends
///////////////IStack function starts
void initistack(ISTACK *stack)
{
int i;
for(i=0;idata[i] = 0.0f;
stack->top = -1;
}
float ipop(ISTACK *stack)
{
if (stack->top == -1)
return 0;
float c;
c = stack->data[stack->top];
stack->top -= 1;
return c;
}
int ipush(ISTACK *stack, float ch)
{
// inserts an element into the stack
stack->top += 1;
if(stack->top == STACK_SIZE)
{
stack->top -= 1; return -1; // error status
}
stack->data[stack->top] = ch; // assign data
return 0; // success
}
///////////////IStack function ends
#endif
/*
Program to evaluate arithmetic expressions.........
*/
# include
# include
# include
# include
# include
#include "mystack.h"
int exp_val(char *pstr);
typedef union
{
float idata;
char cdata;
} DATA;
// function forward declaration
void exp_check(char *str);
int nextToken(char **, DATA *data);
void finish(STACK *stack_optr, ISTACK *stack_oprd);
void fupto(STACK *stack_optr, ISTACK *stack_oprd);
float execute(float oprd1,float oprd2, char ch);
int getpriority(char oprt);
// user defined function definition starts................
int main()
{
char *str;
// allocate input string memory
str = malloc(sizeof(char)*140);
printf("\n\n\tAllowed operators are +, -, *, /, (, and )");
printf("\n\n\tOperands can be both integers and decimal numbers..");
printf("\n\n\tEnter an expression > ");
scanf("%139s",str);
exp_check(str);
exp_val(str);
printf("\n");
return 0;
}
void exp_check(char *str)
{
int i=0;
STACK stack;
initstack(&stack); // initialize stack........
while((str[i]) != '\0')
{
if( str[i] == '(' ) push(&stack,str[i]);
if( str[i] == ')' )
{
char temp;
temp = pop(&stack);
if( temp != '(' )
{
printf("\n\n\tMismatch occurs...\n\n");
exit( -1 );
}
}
i++;
}
if(stack.top != -1)
{
printf("\n\nImproper number of braces......\n\n");
exit(-1);
}
else
printf("\n\nThe expression is valid..\n\n");
}
int exp_val(char *pstr)
{
STACK stack_optr;
ISTACK stack_oprd;
DATA data;
int rval;
float fresult;
char ch;
initstack(&stack_optr); // initialize stack........
initistack(&stack_oprd); // initialize stack........
while((rval=nextToken(&pstr,&data))!= -1)
{ // implementation goes here ..................
if ( rval == 0 ) // operand in the expression.................
{
ipush(&stack_oprd, data.idata);
}
else if ( rval == 1) // operator in the expression..........
{
float oprd1, oprd2, result=0.0;
char prev;
if( data.cdata == '(' )
{
push(&stack_optr,data.cdata);
continue;
}
else if( data.cdata == ')')
{
fupto(&stack_optr,&stack_oprd);
continue;
}
if( isempty(&stack_optr) ) // if operator stack is empty just store the operator......
push(&stack_optr,data.cdata);
else
{
prev = pop(&stack_optr); // pop the operator...............
// check the priority of the operator with the current one....
if( prev == '(' )
{
push(&stack_optr,prev);
push(&stack_optr,data.cdata);
continue;
}
if( getpriority(data.cdata) > getpriority(prev) )
{
// just store the hight priority operator after the current one.......
push(&stack_optr,prev);
push(&stack_optr,data.cdata);
}
else if( getpriority(data.cdata) == getpriority(prev))
{
// execute the operation for current availabe and store the result.....
oprd2 = ipop(&stack_oprd);
oprd1 = ipop(&stack_oprd);
result = execute(oprd1,oprd2,prev);
ipush(&stack_oprd,result); // store the result...
push(&stack_optr,data.cdata); // store the new operator...
}
else
{
push(&stack_optr,prev);
fupto(&stack_optr,&stack_oprd);
push(&stack_optr, data.cdata); // store the low priority operator alone...
}
}
}
} // end of while........
if(!isempty(&stack_optr)) // if not empty
finish(&stack_optr,&stack_oprd);
fresult = ipop(&stack_oprd);
printf("\n\n\t\t| Result is > %f |\n",fresult);
}
float execute(float oprd1,float oprd2, char ch)
{
float result;
switch(ch)
{
case '+':
result = oprd1 + oprd2;
break;
case '-':
result = oprd1 - oprd2;
break;
case '*':
result = oprd1 * oprd2;
break;
case '/':
result = oprd1 / oprd2;
break;
}
return result;
}
void finish(STACK *stack_optr, ISTACK *stack_oprd)
{
char ch;
float oprd1,oprd2,result;
while (!isempty(stack_optr)) // while not empty
{
oprd2 = ipop(stack_oprd);
oprd1 = ipop(stack_oprd);
ch = pop(stack_optr);
result = execute(oprd1,oprd2,ch);
ipush(stack_oprd,result);
}
}
void fupto(STACK *stack_optr, ISTACK *stack_oprd)
{
char ch;
float oprd1,oprd2,result;
while ( !isempty(stack_optr) && (ch = pop(stack_optr)) != '(') // while not empty
{
oprd2 = ipop(stack_oprd);
oprd1 = ipop(stack_oprd);
result = execute(oprd1,oprd2,ch);
ipush(stack_oprd,result);
}
}
int nextToken(char **ppstr, DATA *data)
{
// returns 0 if integer token (operand)
// returns 1 if char token (operator)
// returns -1 if no token is available.
static int i=0;
int slen=0;
float fp=0;
if( *((*ppstr) + i) == '\0' )
return -1;
if( (*((*ppstr)+i) >= 48 && *((*ppstr)+i) <= 57) || *((*ppstr)+i) == 46)
{
// integer token so parse it.........
int fflag=0; char tt[40];
int jj=0;
while( (*((*ppstr)+i) == 46) || ( (*((*ppstr)+i) !='\0') && ( *((*ppstr)+i) >= 48 && *((*ppstr)+i) <= 57) ) )
{
if(*((*ppstr)+i) == 46)
fflag = 1;
else
fflag =0;
if(fflag)
tt[jj] = '.';
else
tt[jj] = *((*ppstr)+i);
jj++;
i++;
}
tt[jj]='\0';
sscanf(tt,"%f",&fp);
data->idata = fp;
return 0;
}
else
data->cdata = *((*ppstr) + i); // store the character....
i++;
return 1;
}
int getpriority(char oprt)
{
if( oprt == '+' || oprt == '-' )
return 1; // low priority
else if ( oprt == '*' || oprt == '/')
return 2; // high priority
}
No comments:
Post a Comment