/* 
* Code example for CP264 Data Structures II
* expression tree to infix, postfix, and prefix, tree 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;  // 0:operant; 1:operator; 3:parenthesis
  struct tree_node *left;
  struct tree_node *right;
} tnode;

tnode *new_node(int data, int type);
void print_tree(tnode *root, int prelen);
void print_infix(tnode *root);
void print_prefix(tnode *root);
void print_postfix(tnode *root);
void clean_tree(tnode **rootp);
int evalulate_expression_tree(tnode *root);

int main() {
// test 1
  printf("test 1\n"); 
  tnode *root = new_node('+', 1);
  root->left = new_node('*', 1);
  root->left->left = new_node(5, 0);
  root->left->right = new_node(4, 0);
  root->right = new_node('-', 1);
  root->right->left = new_node(100, 0);
  root->right->right = new_node(20, 0);

  print_tree(root, 0);
  printf("\ninfix expression and evaluation: ");
  print_infix(root);  
  printf(" = %d", evalulate_expression_tree(root));

  printf("\npostfix expression: ");
  print_postfix(root);
  printf("\nprefix expression: ");
  print_prefix(root);
  clean_tree(&root);

// test 2
  printf("\ntest 2\n"); 
  root = new_node('+', 1);
  root->left = new_node('*', 1);
  root->left->left = new_node(5, 0);
  root->left->right = new_node(4, 0);
  root->right = new_node('-', 1);
  root->right->left = new_node(100, 0);
  root->right->right = new_node('/', 1);
  root->right->right->left = new_node(20, 0);
  root->right->right->right = new_node(2, 0);

  print_tree(root, 0);
  printf("\ninfix expression and evaluation:");  
  print_infix(root);
  printf(" = %d\n", evalulate_expression_tree(root));
  printf("postfix expression: ");
  print_postfix(root);
  printf("\nprefix expression: ");
  print_prefix(root);
  clean_tree(&root);

  return 0;
}

tnode *new_node(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 evalulate_expression_tree(tnode *root)
{
  if (root == NULL) 
    return 0;
  else if (root->type != 1) 
    return root->data.operant;
  else {
    int l = evalulate_expression_tree(root->left);
    int r = evalulate_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)
      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) {
    if (root->left)
      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);
  }
}

/*

|___+
    |___-
        |___20
        |___100
    |___*
        |___4
        |___5

infix expression and evaluation: ((5*4)+(100-20)) = 100
postfix expression: 5 4 * 100 20 - +
prefix expression: + * 5 4 - 100 20
|___+
    |___-
        |___/
            |___2
            |___20
        |___100
    |___*
        |___4
        |___5

infix expression and evaluation: ((5*4)+(100-(20/2))) = 110
postfix expression: 5 4 * 100 20 2 / - +
prefix expression: + * 5 4 - 100 / 20 2
*/