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);
    return top;
}

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;
}
copyright (c) 2015 K Sreram. 
About my blog