#include <stdio.h>
#include<iostream.h>
#include <conio.h>
#include<alloc.h>
#include<process.h>
#include<ctype.h>

// precedence matrixchar prec[6][6] = {'x','+','*','(',')',']',
            '+','>','<','<','>','>',
            '*','>','>','<','>','>',
            '(','<','<','<','=','x',
            ')','>','>','x','>','>',
            '[','<','<','<','x','='};

struct node
{
    char symbol;
    struct node* lptr;
    struct node* rptr;
}*x, *temp;

struct stk
{
    char oper;                // operations on stackstruct node* optr;            //
}stack[10];

char exp[20];        // expression to be scannedint top=-1;                // top of stackint sb=1;                // stack base pointerint ssm=0;                // source string markerint cur=1;                // current stringvoid main()
{
    char chpr(char,char);
    void inorder(struct node *);
    void postorder(struct node *);
    void preorder(struct node *);
    char res;
    clrscr();
    cout<<"enter the expression between [] brackets\n";
    gets(exp);
    top++;

    stack[top].oper = '[';
    while(1)
    {
         if (isalpha(exp[cur]))
         {
        x = (struct node *)malloc(sizeof(struct node));
        x->symbol = exp[cur];
        x->lptr = NULL;
        x->rptr = NULL;
        stack[top].optr = x;
        ssm++;
        }
        else
        {
        res = chpr(stack[top].oper , exp[cur]);
        while(res == '>')
        {
          x = (struct node *)malloc(sizeof(struct node));
          x->symbol = stack[top].oper;
          x->lptr = stack[top-1].optr;
          x->rptr = stack[top].optr;
          top--;
          stack[top].optr = x;
          res = chpr(stack[top].oper , exp[cur]);
        }
        if(res == '<')
        {
          top++;
          stack[top].oper = exp[cur];
        }
        if(res == '=')
        {
          if(stack[top].oper == '[')
          break;
          if(stack[top].oper == '(')
          {
            temp = stack[top].optr;
            top--;
            stack[top].optr = temp;
          }
        }
        }
       cur++;
    }
node * root=stack[0].optr;

cout<< "THE OUTPUT OF THE PARSING FROM DIFFERENT TRAVERSALS ARE:"<<endl;
cout<<endl;
cout<<"INORDER TRAVERSAL OF TREE"<<endl;
inorder(root);
cout<<endl;
cout<<"POSTORDER TRAVERSAL OF THE TREE"<<endl;
postorder(root);
cout<<endl;
cout<<"PREORDER TRAVERSAL OF THE TREE"<<endl;
preorder(root);

getch();

}


char chpr(char x,char y)
{
    int i=0,j=0;
    while(prec[i][0] != x && i<6)
    i++;
    while(prec[0][j] != y && j<6)
    j++;
    return prec[i][j];
}

void preorder(struct node * root)
{
    struct node * ptr;
    ptr = root;
    if(ptr != NULL)
     {
    cout<<ptr->symbol;
    preorder(ptr->lptr);
    preorder(ptr->rptr);
    }
}

void postorder(struct node * root)
{
    struct node * ptr;
    ptr = root;
    if(ptr!=NULL)
    {
      postorder(ptr->lptr);
      postorder(ptr->rptr);
      cout<<ptr->symbol;
    }
}

void  inorder( node * root)
{
    struct node * ptr;
    ptr = root;
    if(ptr!=NULL)
    {
      inorder(ptr->lptr);
      cout<<ptr->symbol;
      inorder(ptr->rptr);
    }
}

/*OUTPUT
enter the expression between [] brackets
[a+b*(c+d)]
THE OUTPUT OF THE PARSING FROM DIFFERENT TRAVERSALS ARE:

INORDER TRAVERSAL OF TREE
a+b*c+d
POSTORDER TRAVERSAL OF THE TREE
abcd+*+
PREORDER TRAVERSAL OF THE TREE
+a*b+cd
*/