infix to podtfix using stack in C

/*
Queue implementation using
double ways linked list representations
Here two pointers are required and these are Q.Rear and Q.Front
For single element queue both left and right pointers
are NULL.
*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>

#define MAXSIZE 8

#define TRUE 1
#define FALSE 0

typedef unsigned char Boolean;

typedef struct Node_tag
{
    char Data;
    struct Node_tag *LLink;
    struct Node_tag *RLink;
} NODE;

NODE *GetNode()
{
    NODE *New;
    New = (NODE *) malloc(sizeof(NODE));
    New ->LLink = NULL;
    New ->RLink = NULL;
    return New;
}

typedef struct Stack
{
    NODE *Top;
} STACK;


STACK Initialize(STACK S)
{
    S.Top = NULL;
    return S;
}

Boolean IsFull(STACK S)
{
    NODE *New;
    New = GetNode();
    if(New==NULL)
        return TRUE;
    else
        {
            free(New);
            return FALSE;
        }
}

Boolean IsEmpty(STACK S)
{
    if (S.Top == NULL)
        return TRUE;
    else
        return FALSE;
}

STACK Push(STACK S, char x)
{
    NODE *New;
    New = GetNode();
    if(New==NULL)
        {
            printf("\n STACK overflow error");
            return S;
        }
    New->Data = x;
    if (S.Top== NULL)
    {
        S.Top = New;
    }
    else
    {
        New->RLink=S.Top;
        S.Top->LLink = New;
        S.Top=New;
    }
    return S;
}


/*
STACK Insert(STACK Q, int x)
{
    int i;
    if (Q.Front==0)
        {
            printf("\n STACK overflow error");
            return Q;
        }
    if (Q.Rear == -1)
    {
        Q.Rear = Q.Front = MAXSIZE - 1;
    }
    else
        for(i=Q.Front;i<MAXSIZE;i++)
            Q.Data[i-1]=Q.Data[i];
    Q.Data[Q.Rear] = x;
    return Q;
}
*/

STACK Pop(STACK S, char *x)
{
    NODE *Del;
    if (S.Top == NULL)
    {
        printf("\n STACK underflow error");
        return S;
    }
    Del = S.Top;
    S.Top = Del->RLink;
    if (S.Top!=NULL)
    {
        S.Top->LLink = NULL;
        Del->RLink = NULL;
    }
    *x = Del->Data;
    free(Del);
    return S;
}

/*
STACK Delete(STACK Q, int *x)
{
    int i;
    if (Q.Front == -1)
    {
        printf("\n STACK underflow error");
        return Q;
    }
    *x = Q.Data[Q.Front];
    if (Q.Front == Q.Rear)
        Q.Front = Q.Rear = -1;
    else
        {
            for(i=0;i<Q.Rear;i++)
                Q.Data[i] = Q.Data[i+1];
        }
        Q.Rear= Q.Rear - 1;
    return Q;
}
*/

void Display(STACK S)
{
    NODE *Ptr=S.Top;
    if (S.Top == NULL)
    {
        printf("\nEmpty STACK");
        return;
    }
    printf("\nCurrent content of the STACK:");
    while(1)
    {
        if (Ptr==NULL) return;
        printf("%c ", Ptr->Data);
        Ptr=Ptr->RLink;
    }
}

/*
MAXSIZE = 10
Front = -1
Rear = -1
0 1 2 3 4 5 6 7 8 9

0 1 2 3 4 5 6 7 8 9
A
Front = 0
Rear = 0

0 1 2 3 4 5 6 7 8 9
A B
Front = 0
Rear = 1

0 1 2 3 4 5 6 7 8 9
A B C
Front = 0
Rear = 2

0 1 2 3 4 5 6 7 8 9
I J H U B C D E F G
Front = 4
Rear = 3
*/

/*
9+8-4
98+4-
$9
$9 8
$17
$17 4
$13

8+4*6/9-(4+6)

(((())())))()

Home Work:
[([{}{}])]({})
*/
/*
Boolean IsAlgebric(char Str[100])
{
    STACK S;
    int i=0;
    char c;
    S = Initialize(S);
    printf("\nInput string: %s\n", Str);
    while(Str[i]!='\0' && Str[i]!='\n')
    {
        //printf("%c ", Str[i]);

        if(Str[i] !='(' && Str[i]!=')')
        {
            printf("\nInvalid Character\n");
            return FALSE;
        }
        if(Str[i] == '(')
            S = Push(S, Str[i]);
        if(Str[i] == ')')
            {
                if(IsEmpty(S))
                    return FALSE;
                S = Pop(S, &c);
            }
        Display(S);
        i++;
    }
    if(!IsEmpty(S))
        return FALSE;
    else
        return TRUE;
}
*/

Boolean IsDigit(char c)
{
    if(c<'0' || c>'9')
        return FALSE;
    else
        return TRUE;
}


Boolean IsOperator(char c)
{
    if(c=='+' || c=='-' || c=='*' || c=='/')
        return TRUE;
    else
        return FALSE;
}


/*
3+(7-8*6)/7
Stack   Symb      Output
$       3
$       +         3
$+      (         3
$+(     7         3
$+(     -         37
$+(-    8         37
$+(-    *         378
$+(-*   6         378
$+(-*   )         3786
$+      /         3786*-
$+/     7         3786*-
$+/     EOS       3786*-7
$                 3786*-7/+

3786*-7/+
$     3
$3    7
$37   8
$378  6
$3786 *
$37 48 -

*/


Boolean IsPrecede(char Opr1, char Opr2)
{
    char Operators[] = {'/','*','+','-'};
    int Preced1,Preced2;
    for(Preced1=0;Preced1<4;Preced1++)
        if (Operators[Preced1]==Opr1)break;
    if (Preced1==4)
    {
        printf("\nInvalid operator");
        exit(0);
    }
    for(Preced2=0;Preced2<4;Preced2++)
        if (Operators[Preced2]==Opr2)break;
    if (Preced2==4)
    {
        printf("\nInvalid operator");
        exit(0);
    }
    if (Preced1<Preced2)
        return TRUE;
    else
        return FALSE;
}

Boolean PopnTest(STACK S, char Symb)
{
    char Opr;
    if (IsEmpty(S))
        return TRUE;
    S = Pop(S, &Opr);
    S = Push(S, Opr);
    if (Opr == '(')
        return TRUE;
    if (IsPrecede(Symb,Opr))
        return TRUE;
    return FALSE;
}

void InFixToPostFix(char Expr[100], char PExpr[100])
{
    STACK S;
    int i=0, j=0;
    char Symb, PopSymb;
    S = Initialize(S);

    // printf("\nInput string: %s\n", Expr);
    Symb = Expr[i];
    while(Symb!='\0' && Symb!='\n')
    {
        printf("\n%c ", Symb);
        if(IsDigit(Symb))
        {
            PExpr[j] = Symb;
            j++;
        }
        else
            if(Symb == '(')
                S = Push(S, Symb);
            else
                if(Symb == ')')
                {
                    while(TRUE)
                    {
                        if(IsEmpty(S))
                        {
                            printf("\nInvalid Expression");
                            exit(0);
                        }
                        S = Pop(S, &PopSymb);
                        if(PopSymb =='(') break;
                            PExpr[j] = PopSymb;
                            j++;
                    }
                }
                else
                    if(IsOperator(Symb))
                        {
                            while(TRUE)
                            {
                                if(PopnTest(S,Symb))
                                {
                                    S = Push(S, Symb);
                                    break;
                                }
                                else
                                {
                                    S = Pop(S, &PopSymb);
                                    PExpr[j] = PopSymb;
                                    j++;
                                }
                            }
                        }
                    else
                        {
                            printf("\nInvalid Expression");
                                exit(0);
                        }
        i++;
        Symb = Expr[i];
    }
    while(!IsEmpty(S))
    {
        S = Pop(S, &PopSymb);
        PExpr[j] = PopSymb;
        j++;
    }
    PExpr[j]='\0';
}


main()
{
    char Expr[100],PExpr[100];
    printf("\nEnter a expression:");
    scanf("%s", &Expr);
    printf("\nInput string:%s", Expr);
    InFixToPostFix(Expr, PExpr);
    printf("\nOutput post-fix expression = %s\n\n",PExpr);
}