/* lazy.c - evaluates all expressions in both ways.
 *
 * possible improvement would be to construct a dependency
 * graph and automatically disregard all cycles -> that means
 * recurrencies (incl. indirect), however that is not yet enough 
 * to see whether the function terminates, since we don't know what 
 * (possibly functional arguments) will be passed to the functions */
      
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h> 

#define ADD   -1     /* internal coding of built-in functions */
#define SUB   -2
#define MULT  -3
#define DIV   -4
#define REM   -5
#define EQ    -6
#define GT    -7
#define TRUE  -8
#define FALSE -9

/* parsed expression - in the first round, name contains the
    real name of the function; after functions are sorted, the
    function is identified by n = index to ind[] -> names[];
    argument is only used in the body of function definition
    and the whole argument expression gets replaced by pointer
    to the expression passed in the argument;
    use_counter is used so that expression gets deallocated when
    not used anymore */

typedef struct raw_str {
  enum { constant, name, argument, fcall } expr_type;
  char *name;  /* function name, name */
  int n;       /* number or argument or function or number of subexpressions */
  struct raw_str **sub; /* subexpression pointers array, if fcall */
  int use_counter;
} expression;

static char names[1000][33];    /* list of user-defined functions */
static expression *body[1000];  /* user-defined function bodies */
static int ind[1000];           /* sorted index for names[] and bodies[] */
static int nf;                  /* number of user-defined functions */
static int functions_loaded;    /* are all function definitions parsed? (0/1) */
static int loops;               /* 1:this expression loops, skip */
static int neval;               /* number of function evaluations in this expression */

static int op[9][4];                   /* the resulting statistics */
static char *opname[9] = { "add", "sub", "mult", "div", "rem", "eq", "gt", "true", "false" };

/* skip to next literal or ) */
char *minp(char *a, char *b)
{
  if ((a == 0) && (b == 0)) return 0;
  if (a == 0) return b;
  if (b == 0) return a + 1;
  if (a < b) return a + 1;
  return b;
}

/* find the length of this literal */
char *min2(char *a, char *b)
{
  if (a == 0) return b;
  if (b == 0) return a;
  if (a < b) return a;
  else return b;
}

/* mark the expression as stored again */
void stored(expression *e)
{
  e->use_counter++;
}

/* release the expression once, if this was the
   last instance, free from memory */
void free_expression(expression *e)
{
  int i;

  e->use_counter--;
  if (!e->use_counter) 
  {
    if (e->expr_type == fcall)
    {
      for (i = 1; i < e->n; i++)
        free_expression(e->sub[i]);
      free_expression(e->sub[0]);
    }
    free(e);
  }
}

/* convert function name to index (binary search) */
int lookup_function(char *name)
{
 int guess, cmp;
 int lo = 0; 
 int hi = nf;

 while (hi > lo)
 {
   guess = (hi + lo) / 2;
   cmp = strcmp(names[ind[guess]], name);
   if (!cmp) return guess;
   if (cmp < 0) lo = guess + 1;
   else hi = guess;
 }
 /* function not found -> must be built-in */
 for (guess = 0; guess < 8; guess++)
  if (strcmp(opname[guess], name) == 0) break;

 return -1 - guess;
}

/* convert string to internal expression representation (newly allocated)
   return pointer to the next literal in *rest */
expression *parse_expression(char *s, char **rest, int argc, char **argv)
{
  expression *e;
  char *i;
  int j;

  e = (expression *) malloc(sizeof(expression));
  if (((s[0] >= '0') && (s[0] <= '9')) || (s[0] == '-')) /* constant */
  {
    e->expr_type = constant;
    sscanf(s, "%d", &e->n);
    *rest = minp(strchr(s, ' '), strchr(s, ')'));
  }
  else if (s[0] != '(') /* name */
  {
    i = min2(strchr(s, ' '), strchr(s, ')'));
    if (!i) i = s + strlen(s);
    e->name = (char *)malloc(i - s + 1);
    strncpy(e->name, s, i - s);
    *(e->name + (i - s)) = '\0';
    e->expr_type = name;
    if (functions_loaded) 
    {
      e->n = lookup_function(e->name);
      free(e->name);
    }
    for (j = 0; j < argc; j++)
      if (strcmp(argv[j], e->name) == 0) 
      {
        e->expr_type = argument;
        e->n = j;
        free(e->name);
        break;
      }
    *rest = minp(strchr(s, ' '), strchr(s, ')'));
  }
  else /* function call */
  {
    e->expr_type = fcall;
    e->sub = (expression **) malloc(sizeof(expression *));
    e->sub[0] = parse_expression(s + 1, rest, argc, argv);
    stored(e->sub[0]);
    j = 1;
    while (**rest != ')')
    {
      j++;
      e->sub = (expression **) realloc(e->sub, j * sizeof(expression *));
      s = (*rest);
      e->sub[j - 1] = parse_expression(s, rest, argc, argv);
      stored(e->sub[j - 1]);
    }
    (*rest)++;
    while (**rest == ' ') (*rest)++;
    e->n = j;
  }
  e->use_counter = 0;
  return e;
}

/* load user-defined function to memory */
void parse_definition(char *s)
{
  int a = 0;        /* number of formal parameters */
  char *args[500];  /* names of formal parameters */ 
  char *t;

  strtok(s, " ");
  strncpy(names[nf], s, 32);

  while (((t = strtok(0, " "))[0]) != '=')  
    args[a++] = t;
  
  t++; t++;
  body[nf] = parse_expression(t, &t, a, args);
  stored(body[nf]);
  ind[nf] = nf;
  nf++;
}

/* comparison function for standard quicksort */
int compare_names(const void *i1, const void *i2)
{
  return strcmp(names[*((int *)i1)], names[*((int *)i2)]);
}

void process_expression(expression *e, int strict);

/* evaluate built-in function call; returns 0 if this is not built-in function */
int builtin(expression *e, int strict)
{
  int f = e->sub[0]->n;

  if (f < 0) 
  {
    op[-1-f][strict]++;
    if (strict || (f >= -7)) /* arithmetic -> both arguments evaluated */
    {
      process_expression(e->sub[1], strict);
      if (!loops) process_expression(e->sub[2], strict);
      e->expr_type = constant;
      if (!loops)
      {
        switch (f) {
          case ADD: e->n = e->sub[1]->n + e->sub[2]->n; break;
          case SUB: e->n = e->sub[1]->n - e->sub[2]->n; break;
          case MULT: e->n = e->sub[1]->n * e->sub[2]->n; break;
          case DIV: e->n = e->sub[1]->n / e->sub[2]->n; break;
          case REM: e->n = e->sub[1]->n % e->sub[2]->n; break;
          case EQ: e->expr_type = name; if (e->sub[1]->n == e->sub[2]->n) e->n = TRUE; else e->n = FALSE; break;
          case GT: e->expr_type = name; if (e->sub[1]->n > e->sub[2]->n) e->n = TRUE; else e->n = FALSE; break;
          case TRUE: e->n = e->sub[1]->n; e->expr_type = e->sub[1]->expr_type; break;
          case FALSE: e->n = e->sub[2]->n; e->expr_type = e->sub[2]->expr_type; break;
        } 
      } /* loops */
    }
    else
    {
      process_expression(e->sub[TRUE - f + 1], strict);
      if (!loops)
      {
        e->n = e->sub[TRUE - f + 1]->n;
        e->expr_type = e->sub[TRUE - f + 1]->expr_type;
      }
      else e->expr_type = constant; 
    }
    free_expression(e->sub[0]);
    free_expression(e->sub[1]);
    free_expression(e->sub[2]);
    free(e->sub);
    return 1;
  }
  return 0;
}

/* perform deep-copy of expression, and substitute all arguments for
   given expressions */
expression *copy_and_substitute(expression *e, int argc, expression **argv)
{
  int a, i;
  expression *e2;

  if (e->expr_type == argument) 
  {
    a = e->n;
    return argv[e->n];
  }
  e2 = (expression *) malloc(sizeof(expression));
  e2->expr_type = e->expr_type;
  e2->n = e->n;
  if (e->expr_type == fcall)
  {
    e2->sub = (expression **) malloc(e->n * sizeof(expression *));
    for (i = 0; i < e->n; i++)
    {
      if (e->sub[i]->expr_type == argument) e2->sub[i] = argv[e->sub[i]->n];
      else e2->sub[i] = copy_and_substitute(e->sub[i], argc, argv);
      stored(e2->sub[i]);
    }
  }
  e2->use_counter = 0;
  return e2;
}

/* evaluate expression in place - replace the expression by the result */
void process_expression(expression *e, int strict)
{
  expression *e2;
  int i;

  if (e->expr_type == fcall) 
  {
    neval++;
    if (neval > 2345) 
    {
      loops = 1;
      return;
    }
    process_expression(e->sub[0], strict);
    if (!loops) 
      if (!builtin(e, strict))
      {
	if (strict) for (i= 1; i < e->n; i++) 
	   process_expression(e->sub[i], strict);
        e2 = copy_and_substitute(body[ind[e->sub[0]->n]], e->n - 1, (e->sub) + 1);
        process_expression(e2, strict);
	if (!loops)
	{
	  while (e->n--) free_expression(e->sub[e->n]);
          e->expr_type = e2->expr_type;
          e->n = e2->n; 
	}
        free_expression(e2);
      }
    if (loops && (e->expr_type == fcall)) 
    {
      while (e->n--) free_expression(e->sub[e->n]);
      e->expr_type = constant;
    }
  }
}

/* convert the representation of function names from strings to index */
void convert_names(expression *e)
{
  int i;

  if (e->expr_type == name) 
  {
    e->n = lookup_function(e->name);
    free(e->name);
  } 
  if (e->expr_type == fcall)
  {
    for (i = 0; i < e->n; i++)
      convert_names(e->sub[i]);
  }
}

int main()  /* here we start */
{
  char s[1002];
  expression *e;
  int i;
  char *t;

  /* read function definitions */
  nf = 0; functions_loaded = 0;
  fgets(s, 1001, stdin);
  do {
    s[strlen(s) - 1] = '\0';
    parse_definition(s);
    fgets(s, 1001, stdin);
  } while (s[0] != '\n');

  /* sort functions according to name */
  qsort(ind, nf, sizeof(int), compare_names); 

  /* change internal representation of function names */
  for (i = 0; i < nf; i++) convert_names(body[i]);
  functions_loaded = 1;

  for (i = 0; i < 5; i++) op[i][2] = op[i][3] = 0;

  /* process all expressions, evaluate in both ways independently */
  fgets(s, 1001, stdin);
  do {
    s[strlen(s) - 1] = '\0';
    for (i = 0; i < 5; i++) op[i][0] = op[i][1] = 0;
    neval = loops = 0;
    e = parse_expression(s, &t, 0, 0);
    process_expression(e, 0);
    free_expression(e);
    if (!loops)
    {
      neval = 0;
      e = parse_expression(s, &t, 0, 0);
      process_expression(e, 1);
      free_expression(e);
      if (!loops)
        for (i = 0; i < 5; i++) 
        {
          op[i][2] += op[i][0];
          op[i][3] += op[i][1];
        }
    }
    if (!fgets(s, 1001, stdin)) break;
  } while (s[0] != '\n');
 
  /* print the results */
  printf("operator lazy_evaluation strict_evaluation\n");
  for (i = 0; i < 5; i++) printf("%s\t\t%d\t\t%d\n", opname[i], op[i][2], op[i][3]);

  for (i = 0; i < nf; i++)
    free_expression(body[i]);

  return 0;
}