infix to post-fix conversion program

Infix to post-fix conversion program

/*
 infix to postfix conversion program
*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <process.h>
#include <ctype.h>
#include <strings.h>
enum BOOL {FALSE, TRUE };
typedef int BOOL;

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

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 in Top: 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 in Pop: stack is empty");
        exit(-1);
    }
    PtrNode temp = s->next;
    s->next = s->next->next;
    Delete(temp);
}

DataType TopAndPop (Stack s)
{
    DataType top = Top(s);
    Pop(s);
    return top;
}

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

void DisposeStack(Stack* s)
{
    PopAll(*s);
    Delete(*s);
    *s = NULL;
}
BOOL IsBracket(DataType data)
{
    return (data == '(')||(data == ')');
}
BOOL IsOperator(DataType data)
{
    return ((data == '+') ||
            (data == '-') ||
            (data == '*') ||
            (data == '/'));
}
BOOL IsSymbol(DataType data)
{
    return IsBracket(data) || IsOperator(data);
}
BOOL IsVar(DataType data)
{
    return isalpha(data);
}
int FindPriority(DataType symbol)
{ // allots the priority of the symbols used
    if(symbol == '(' || symbol == ')')
        return 10;
    if(symbol == '(' || symbol == ')')
        return 10;
    else if ((symbol == '/') || (symbol == '*'))
        return 8;
    else if ((symbol == '+') || (symbol == '-'))
        return 6;
    else return 0;
}
void displayStack(Stack s)
{
    PtrNode temp = s->next;
    while(temp != NULL)
    {
        printf("\n%c",temp->data);
        temp = temp->next;
    }
    getch();
}
void evaluate(Stack symbol)
{
     printf("%c", TopAndPop(symbol));
}
void infixToPostfix(Stack infix) /// B, D, M, A, S
{
    Stack symbolStack = NewStack();
    DataType temp;
    while(!IsEmpty(infix))
    {
        temp = Top(infix);
        if(temp == '(')
        {
            Push(symbolStack, temp);
            Pop(infix);
        }
        else if(IsOperator(temp))
        {
            while((Top(symbolStack)!='(') &&
                (FindPriority(temp) <= FindPriority(Top(symbolStack))))
                    evaluate(symbolStack);
            /*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))
            {
                printf("%c", temp);
                Pop(infix);
            }
        else if(temp == ')')
            {
                if(Top(symbolStack) == '(')
                {
                    Pop(symbolStack);
                    Pop(infix);
                }
                else evaluate(symbolStack);// evaluate is called until
                              // the symbol '(' us reached, until which
                            // top of infix remains to be ')'
            }
    }
    DisposeStack(&symbolStack);
}
Stack getInfixStack()
{
    char expression[100];
    int len, i;
    Stack infix = NewStack();
    scanf("%s", expression);
    strrev(expression);
    len = strlen(expression);
    for(i=0; i<len; ++i)
        if(IsSymbol(expression[i])|| IsVar(expression[i]))
            Push(infix, expression[i]);
    return infix;
}

int main()
{
    printf("enter the expression:\n");
    Stack infix = getInfixStack();
    infixToPostfix(infix);
    DisposeStack(&infix);
    getch();
    return 0;
}



copyright (c) 2015 K Sreram.
About my blog