#include "y.tab.c"

void printTree(Tree* t) { 
  switch(t->C) {

  case s:
    printf("S");
    break;
  case k:
    printf("K");
    break;

  default: // wasn't a leaf
    printf("(");
    printTree(t->N->left);
    printf(" ");
    printTree(t->N->right);
    printf(")");
  }
}

Tree* reduce(Tree* t) {
  // reduce using pointer reversal
  Tree* back;
  Tree* current = t;
  int node_count = 0;

  while (1) {
    while (current->C != s && current->C != k) {
      // scan down to left-most leaf
      
      Tree* current_ = current->N->left;
      current->N->left = back;
      back = current;
      current = current_;
      node_count++;
    }

    if (current->C == s && node_count >= 3) {
      // do an S-reduce
      Tree *f, *g, *fTree, *gTree, *x;
      
      f = back->N->right;
      current = back;
      back = back->N->left;
      current->N->left = f;
      fTree = current;
      
      g = back->N->right;
      current = back;
      back = back->N->left;
      current->N->left = g;
      gTree = current;
      
      x = back->N->right;
      fTree->N->right = x;
      gTree->N->right = x;
      back->N->right = gTree;
      current = fTree;
      
      node_count -= 2;
    }
    else if (current->C == k && node_count >= 2) {
      // do a K-reduce
      
      Tree* x = back->N->right;
      current = back->N->left;
      back = current->N->left;
      current = x;
      
      node_count -= 2;
    }
    else {
      // no more reductions
      break;
    }
  }

  // tidy up pointers
  while (node_count > 0) {
    Tree* back_ = back->N->left;
    back->N->left = current;
    current = back;
    back = back_;
    node_count--;  
  }

  return current;
}

int main() {
  Tree* ptree;
  int parseret;
  while (1) {
    printf("> ");
    parseret = yyparse();
    if (parseret != 1) {
      ptree = reduce((Tree*) parseret);
      printTree(ptree);
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}