Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

Friday, 3 April 2015

program to evaluate infix expressions

Program to evaluate infix expressions

/*
* Program to convert an infix arithmetic expression to
* postfix and to thereby evaluate the result.
*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <process.h> // for exit
#include <ctype.h> // for isdigit()
#include <string.h>

enum BOOL {FALSE, TRUE};
typedef int BOOL;

struct NODE;
struct InfixSymbol;
typedef struct NODE Node;
typedef Node* PtrNode;
typedef PtrNode Stack;
typedef struct InfixSymbol DataType;

struct InfixSymbol{
int data;
BOOL is_symbol;
};

struct NODE{
DataType data;
PtrNode next;
};

BOOL IsEmpty(Stack s)
{
return ((s!=NULL)&&(s->next == NULL));
}
Stack NewStack()
{
Stack s = malloc(sizeof(Node));
s->next = NULL;
return s;
}

PtrNode NewNode()
{
PtrNode n = malloc(sizeof(Node));
return n;
}
void Delete(PtrNode n)
{
free(n);
}
void Push(Stack s, DataType data)
{
PtrNode n = NewNode();
if(n == NULL)
{
fprintf(stderr, "error: memory allocation using malloc function failed");
return;
}
n->data = data;
n->next = s->next;
s->next = n;
}

DataType Top(Stack s)
{
if(s==NULL || s->next == NULL) // this is a fatal error
{
fprintf(stderr, "error: stack is empty");
exit(-1);
}
return s->next->data;
}

void Pop(Stack s)
{
if(s==NULL || s->next == NULL) // this is a fatal error
{
fprintf(stderr, "error: stack is empty");
exit(-1);
}
PtrNode temp = s->next;
s->next = s->next->next;
Delete(temp);
}

DataType TopAndPop (Stack s)
{ // pops and returns the top value
DataType top = Top(s);
Pop(s);
}

void PopAll(Stack s)
{ // clears the Stack
while (!IsEmpty(s))
Pop(s);
}

void DisposeStack(Stack* s)
{
PopAll(*s);
Delete(*s);
*s = NULL;
}
int strToInt(char* str) // this function unlike atoi, neglects sign.
{  // follows ASCII convention
int retVal = 0, i = 0;
while(str[i]!='\0') // skips space
if(isspace(str[i]))
++i;
else
break;

for(; str[i]!='\0'; ++i)
{
if(isdigit(str[i]))
retVal = retVal*10 + str[i] - '0';
else
break; // break when other symbols are read
}
return retVal;
}
BOOL IsBracket(DataType data) // assumes data.is_symbol to be true
{
return (data.data == (int)'(')||(data.data == (int)')');
}
BOOL IsOperator(DataType data)// assumes data.is_symbol to be true
{
return ((data.data == (int)'+') ||
(data.data == (int)'-') ||
(data.data == (int)'*') ||
(data.data == (int)'/'));
}
BOOL IsSymbol(DataType data)
{
return IsBracket(data) || IsOperator(data);
}
BOOL IsVar(DataType data)// uses data.is_symbol to check for equality to FALSE
{
return data.is_symbol == FALSE;
}
int FindPriority(DataType symbol)
{ // allots the priority of the symbols used
if(symbol.data == (int)'(' || symbol.data == (int)')')
return 10;
else if ((symbol.data == (int)'/') || (symbol.data == (int)'*'))
return 8;
else if ((symbol.data == (int)'+') ||(symbol.data == (int)'-'))
return 6;
else return 0;
}

void evaluate(Stack symbolStack, Stack VariableStack)
{ // evaluates using the last symbol once
DataType Symbol = TopAndPop(symbolStack);
DataType v1 = TopAndPop(VariableStack);
DataType v2 = TopAndPop(VariableStack);
DataType v3; v3.is_symbol = FALSE;
if(Symbol.data == (int)'+')
v3.data = v2.data + v1.data;
else if (Symbol.data == (int)'-')
v3.data = v2.data - v1.data;
else if (Symbol.data == (int)'*')
v3.data = v2.data * v1.data;
else if(Symbol.data == (int)'/')
v3.data = v2.data / v1.data;
else
{
fprintf(stderr, "error: unrecognised symbol");
v3.data = 0;
}
Push(VariableStack, v3);
}
int EvaluateExpression(Stack infix)
{/// evaluates the infix expression and returns the result
int retVal;
Stack VariableStack = NewStack();
Stack SymbolStack = NewStack();
DataType temp;
while(!IsEmpty(infix))
{
temp = Top(infix);
if(temp.is_symbol && temp.data == (int)'(')
{
Push(SymbolStack, temp);
Pop(infix);
}
else if(temp.is_symbol && IsOperator(temp))
{
while((Top(SymbolStack).data!=(int)'(') &&
(FindPriority(temp) <= FindPriority(Top(SymbolStack))))
evaluate(SymbolStack, VariableStack);
/*checks if the symbol on top is '(' or greater in priority,
for which the evaluation function is called
*/
Push(SymbolStack, temp);
Pop(infix);
}
else if( IsVar(temp))
{
Push(VariableStack, temp);
Pop(infix);
}
else if(temp.is_symbol && temp.data == (int)')')
{
if(Top(SymbolStack).data == (int)'(')
{
Pop(SymbolStack);
Pop(infix);
}
else evaluate(SymbolStack, VariableStack);// evaluate is called until
// the symbol '(' us reached, until which
// top of infix remains to be ')'
}
}

retVal = TopAndPop(VariableStack).data;
if(!IsEmpty(VariableStack))
{
fprintf(stderr, "syntax error in evaluation");
return 0;
}
DisposeStack(&SymbolStack);
DisposeStack(&VariableStack);
return retVal;
}
Stack ReverseStack(Stack s)
{ // reverses the stack direction
Stack tempStack =NewStack();
while(!IsEmpty(s))
Push(tempStack, TopAndPop(s));
return tempStack;
}
int sizeofIntiger(int a)
{ // returns the number of digits
int i = 0;
while(a!=0)
{
a=a/10;
++i;
}
return i;
}
Stack GetExpressionStack()
{ // reads the expression from the user as a
// C string and converts it to expression stack
char expression[100];
int len, i;
Stack infix = NewStack();
scanf("%s", expression);
len = strlen(expression);
DataType temp;
for(i=0; i<len; ++i)
{
temp.data = expression[i];
temp.is_symbol = FALSE;
if(isdigit(temp.data))
{
temp.is_symbol = FALSE;
temp.data = strToInt(expression + i);
i=i+sizeofIntiger(temp.data)-1;
Push(infix, temp);
}
else if(IsSymbol(temp))
{
temp.is_symbol = TRUE;
Push(infix, temp);
}
/// all other characters are ignored
}
Stack retVal = ReverseStack(infix);
DisposeStack(&infix);
return retVal;
}
int main()
{
printf("Program to evaluate simple expressions \n");
printf("Enter the expression: \n");
Stack expression = GetExpressionStack();
int Result = EvaluateExpression(expression);
printf("the result of the expression is, %d", Result);
DisposeStack(&expression);
getch();
return 0;
}