/*
* infix -> postfix (singly linked list)
* postfix -> expression tree -> infix, postfix, prefix, prefix evaluation 
* expression tree -> infix, postfix, prefix, 
* prefix evaluation
* HBF
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef union ledata {
   int operant;
   char operator;
   char parenthesis;
} DATA;

typedef struct tree_node
{
  DATA data;
  int type;
  struct tree_node *left;
  struct tree_node *right;
} tnode;
tnode *new_tnode(int data, int type);
void print_tree(tnode *root, int space);
void print_infix(tnode *root);
void print_prefix(tnode *root);
void print_postfix(tnode *root);
void clean_tree(tnode **rootp);
int evaluate_expression_tree(tnode *root);


// infix to postfix converstion
typedef struct node {
  DATA data;
  int type;  
  struct node *next;
} sqnode;

sqnode *new_sqnode(DATA data, int type);
void display_forward(sqnode *start);
void clean(sqnode **startp);
sqnode *dequeue(sqnode **frontp, sqnode **rearp);
void enqueue(sqnode **frontp, sqnode **rearp, sqnode *np);
void push(sqnode **topp, sqnode *np);
sqnode *pop(sqnode **topp);
void infix_to_postfix(char *infixstr, sqnode **frontp, sqnode **rearp);
int evaluate_postfix(sqnode **frontp, sqnode **rearp);
int get_priority(char opr);
int is_operator(char op);
int is_symbol(char s);

// postfix queue to expression tree
typedef struct stnode {
  tnode *tnp;  
  struct stnode *next;
} stnode;
void tpush(stnode **topp, tnode *tnp);
tnode *tpop(stnode **topp);
tnode *postfix_to_expression_tree(sqnode *front);

void expression_tree_to_prefix(tnode *root, sqnode **frontp, sqnode **rearp);
int evaluate_prefix(sqnode *front);

int main() {
 
  printf("infix string to postfix queue\n");
  char *infixstr = "((5*52)+(100-20))";
  sqnode *front = NULL, *rear = NULL;
  infix_to_postfix(infixstr, &front, &rear);
  
  printf("%s -> ", infixstr);
  display_forward(front);
  
  tnode *root = postfix_to_expression_tree(front) ;
  printf("\nexpression tree \n");
  print_tree(root, 0);
  
  
  printf("\nexpression tree to infix and expression tree evaluation\n");  
  print_infix(root);
  printf(" = %d\n", evaluate_expression_tree(root));
  
  printf("\nexpression tree to prefix and prefix evaluation");
  sqnode *pffront = NULL, *pfrear = NULL;
  expression_tree_to_prefix(root, &pffront, &pfrear);
  printf("\n");
  display_forward(pffront);
  printf(" = %d\n", evaluate_prefix(pffront));
  clean(&pffront);

  clean_tree(&root);
  return 0;
}

tnode *new_tnode(int data, int type)
{
  tnode *np = (tnode *) malloc(sizeof(tnode));
  if (np == NULL) return NULL;
  
  np->type = type; 
  if (type == 0)
    np->data.operant = data;  
  else if (type == 1)
  np->data.operator = data; 
  
  np->left = NULL;
  np->right = NULL;
  return np;
}


void print_tree(tnode *root, int prelen) {
  int i;
  if (root != NULL) {
    for (i=0; i < prelen; i++) 
    printf("%c", ' ');
    printf("%s", "|___");
  
  if (root->type == 0)
    printf("%d\n", root->data.operant);
  else if (root->type == 1)
    printf("%c\n", root->data.operator);
  
    print_tree(root->right, prelen+4);
    print_tree(root->left, prelen+4);  
  }
}

void clean_tree(tnode **rootp) {
  tnode *root = *rootp;
  if (root) {
    if (root->left)
      clean_tree(&root->left);
    if (root->right)
      clean_tree(&root->right);
    free(root);
  }
  *rootp = NULL;
}

int evaluate_expression_tree(tnode *root)
{
  if (root == NULL) 
    return 0;
  else if (root->type == 0)
    return root->data.operant;
  else if (root->type == 1) {
    int l = evaluate_expression_tree(root->left);
    int r = evaluate_expression_tree(root->right);
    switch(root->data.operator) {
      case '+': return l+r;
      case '-': return l-r;
      case '*': return l*r;
      case '/': return l/r;
      case '%': return l%r;
    };
  }
}

void print_infix(tnode  *root)
{
  if (root != NULL)
  {
    if (root->type == 1) 
    printf("(");
    
  print_infix(root->left);
  
  if (root->type == 0) {
    if (root->data.operant < 0)
        printf("(%d)", root->data.operant);
    else 
      printf("%d", root->data.operant);
    }
  else if (root->type == 1) {
    printf("%c", root->data.operator);
  }
  
  print_infix(root->right);
  
    if (root->type == 1)
      printf(")");
  }
}

void print_prefix(tnode  *root) {
  if (root) {
  if (root->type == 0)  
      printf("%d ", root->data.operant);
    else if (root->type == 1)  
      printf("%c ", root->data.operator);

    print_prefix(root->left);
    print_prefix(root->right);
  }
}

void print_postfix(tnode  *root) {
  if (root) {
      print_postfix(root->left);
      print_postfix(root->right);
  
  if (root->type == 0)  
      printf("%d ", root->data.operant);
    else if (root->type == 1)  
      printf("%c ", root->data.operator);
  }
}

tnode *postfix_to_expression_tree(sqnode *p) { 
  stnode *top = NULL;
  tnode *t, *t1, *t2; 
    
  while (p) {
    
    if ( p->type == 0)  
    { 
      t = new_tnode(p->data.operant, 0); 
      tpush(&top, t); 
    } 
	else 
	{ 
      t = new_tnode(p->data.operator, 1); 
	  t1 = tpop(&top); 
      t2 = tpop(&top); 
	  t->right = t1; 
	  t->left = t2; 
	  tpush(&top, t); 
	}
    p = p->next;    
  } 
  t = tpop(&top); 
  return t; 
} 
  
void infix_to_postfix(char *infixstr, sqnode **frontp, sqnode **rearp) {
  sqnode *top=NULL;
  char *p = infixstr;
  int sign = 1;
  int num = 0;
  
  while (*p) {  
    if ( *p == '-' && (p == infixstr || *(p-1) == '(')  ) {
      sign = -1;
    }  
    else if (*p >= '0' && *p <= '9'){
      num = *p-'0';
      while ((*(p+1) >= '0' && *(p+1) <= '9')) {
         num = num*10 + *(p+1)-'0';
         p++;
      }
  
      enqueue(frontp, rearp, new_sqnode((DATA)(sign*num), 0));
      sign = 1;  
    }
    else if (*p == '(') {
      push(&top, new_sqnode((DATA)'(', 3));
    }
    else if (*p == ')') {
      while (top){
        if (top->type == 3) {
          free(pop(&top));
          break;
        }
        enqueue(frontp, rearp, pop(&top));  
      }
    } else if (is_operator(*p)) {
      while (top && top->type==1 && get_priority(top->data.operator) >= get_priority(*p))
        enqueue(frontp, rearp, pop(&top));  
      push(&top, new_sqnode((DATA) *p, 1));
    }
    p++;
  }
  
  while (top) {    
    enqueue(frontp, rearp, pop(&top));  
  }
}

//postfix expression queue evaluation
int evaluate_postfix(sqnode **frontp, sqnode **rearp) {
  sqnode *top = NULL;
  int type = 0;
  sqnode *p = *frontp;
  
  while (p) {
    type = p->type;
  
    if (type == 0) {    // operant
      push(&top, new_sqnode(p->data, 0));
    }    
    else if (type==1){  // operator
      char operator = p->data.operator;
    
      sqnode *oprand2 = pop(&top);
      sqnode *oprand1 = pop(&top);
      int b = oprand2->data.operant;
      int a = oprand1->data.operant;
      int c; 
      
      if (operator == '+')
        c = a + b;
      else if (operator == '-')
        c = a - b;
      else if (operator == '*')
        c = a * b;
      else if (operator == '/')
        c = a / b;
      else if (operator == '%')
        c = a % b;
        
      push(&top, new_sqnode((DATA) c, 0));
    
      free(oprand1);
      free(oprand2);
    
	}
  
    p = p->next;
  }

  int result = top->data.operant;
  clean(&top);  
  return result;
}

sqnode *new_sqnode(DATA data, int type) {
  sqnode *np = (sqnode *) malloc(sizeof(sqnode));
  np->type = type; 
  np->data = data;  
  np->next = NULL;
  return np;
}

void push(sqnode **topp, sqnode *np) {
  if (*topp == NULL) {
    *topp = np;
    np->next = NULL;
  }
  else {
    np->next = *topp;
    *topp = np;
  }
}

sqnode *pop(sqnode **topp) {
  if (*topp) {
    sqnode *tmp = *topp;
    *topp = tmp->next;
    tmp->next = NULL;
    return tmp;
    
  } else 
  return NULL;
}

void enqueue(sqnode **topp, sqnode **bottom, sqnode *np) {
  if (*topp == NULL) {
    *topp = np;
    *bottom = np;
    np->next = NULL;
  }
  else {
    (*bottom)->next = np;
    *bottom = np;  
  }
}  

sqnode *dequeue(sqnode **frontp, sqnode **rearp) {
  sqnode *ptr = *frontp;
  if (ptr == NULL) return NULL;
  if (ptr == *rearp) {
    *frontp = NULL;
    *rearp = NULL;
  } 
  else {
    *frontp = ptr->next;    
  } 
  return ptr; 
}

int get_priority(char op) {
  if (op == '/' || op == '*' || op == '%') return 1;
  else if (op == '+' || op == '-') return 0;
  return 0;
}

int is_operator(char op) {
  if (op == '/' || op == '*' || op == '%' || op == '+' || op == '-')
    return 1;
  else
    return 0;
}

int is_symbol(char s) {
  if (!is_operator(s) && !isdigit(s) && s != ')' && s != '(') {
    return 1;
  } else
    return 0;
}

void clean(sqnode **topp) {
  sqnode *curr = *topp;
  while (curr) {
    sqnode *tmp = curr;
    curr = curr->next;
    free(tmp);
  }
  *topp = NULL;
}

void tpush(stnode **topp, tnode *tnp) {
  stnode *stnp = (stnode *) malloc(sizeof(stnode));
  stnp->tnp = tnp;
  
  if (*topp)
  stnp->next = *topp;
  else 
  stnp->next = NULL;
  
  *topp = stnp;
}

tnode *tpop(stnode **topp) {
  if (*topp == NULL ) return NULL;
  else {
  stnode *p = *topp;
  tnode *tp = p->tnp;
  *topp = p->next;
  free(p);
  return tp;
  }
}

void expression_tree_to_prefix(tnode *root, sqnode **frontp, sqnode **rearp) {
  if (root) {

  enqueue(frontp, rearp, new_sqnode(root->data, root->type));
  

  expression_tree_to_prefix(root->left, frontp, rearp);
  expression_tree_to_prefix(root->right, frontp, rearp);  
  }
}

//postfix expression queue evaluation
int evaluate_prefix(sqnode *front) {
  
  sqnode *pftop = NULL; // stack to hold prefix for evaluation
  while (front) {
  push(&pftop, new_sqnode(front->data, front->type));  
  front = front->next;  
  }     
  
  sqnode *top = NULL;  // prefix evaluation stack
  int type, operator, opr1, opr2, value;
  sqnode *oprand1,*oprand2;
  DATA data;
  
  while (pftop) {
    type = pftop->type;
    if (type == 0) {    // operant
      push(&top, new_sqnode(pftop->data,0));
    }    
    else if (type == 1){  // operator
      operator = pftop->data.operator;
      oprand1 = pop(&top);
    oprand2 = pop(&top);
    opr1 = oprand1->data.operant;
    opr2 = oprand2->data.operant;
    
      
      if (operator == '+')
        value = opr1 + opr2;
      else if (operator == '-')
         value = opr1 - opr2;
      else if (operator == '*')
         value = opr1 * opr2;
      else if (operator == '/')
        value = opr1 / opr2;
          
    data.operant = value;
    
    push(&top, new_sqnode(data,0));
      
      free(oprand1);  
      free(oprand2);
    }
  
  pop(&pftop);
  }

  int result = top->data.operant;
  clean(&top);
  return result;
}

void display_forward(sqnode *front) {
  while (front) {
  if (front->type == 0)
    printf("%d ", front->data.operant);
    else 
    printf("%c ", front->data.operator);  
  
  front = front->next;
  }
}  


/*
infix string to postfix queue
((5*52)+(100-20)) -> 5 52 * 100 20 - +
expression tree
|___+
    |___-
        |___20
        |___100
    |___*
        |___52
        |___5

expression tree to infix and expression tree evaluation
((5*52)+(100-20)) = 340

expression tree to prefix and prefix evaluation
+ * 5 52 - 100 20  = 340
*/