/* Problem 6--Making Mountains out of Molehills
   This was probably the poorest problem I've ever seen since I've been
   following this competition.  Not only was it quite hard on general
   principle--a recursive descent parser with lots of things to watch
   out for--but the problem was written ambiguously as well.  No mention
   was made in the description of nested angle brackets, for example,
   but there were examples of them in the judges file.  Do angle
   brackets legally nest?  The problem could fairly be interpreted
   either way.  Order of evaluation was ambiguous, too, and was also
   tested.  Finally, although the problem stated that no input case
   would be longer than 10 lines, the judge's case had a 14-line input!
   Small wonder no team got this problem correct.
   I got this sample solution working after much examination of the
   judges file, something the competitors would have no access to, of
   course. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char MT[810][2][33];

int main (int argc, char **argv);
void Process (FILE *in, FILE *out, int lns, int cs);
char * MacroExpansion (char *T, int *pos, MT Macros, int *mct);
char * MakeString (char *T, MT Macros, int *mct);

int main (int argc, char **argv) {

  int lns, cs;
  FILE *in, *out;

 in = fopen ("prob6.in","r");
 out = fopen ("prob6.out","w");
 for (cs=1;fscanf (in,"%d",&lns),lns>0;cs++)
  Process (in,out,lns,cs);
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Process reads a data case in and computes and prints the output. */

void Process (FILE *in, FILE *out, int lns, int cs) {

  char T[811], *s;
  int i, lc, mct, exact;
  MT Macros;

 for (;fgetc(in)!='\n';); /* Get trailing EOLN */
 for (i=0;i<811;i++) T[i] = 0;
 for (i=lc=0;lc < lns;i++) {
   /* Read in all characters of data case */
  T[i] = fgetc (in);
  if (T[i]=='\n') lc++;
 }
 mct = 0;
 fprintf (out,"Case %d\n",cs);
 for (i=0;i<79;i++) fprintf (out,"-"); /* Row of hyphens */
 fprintf (out,"\n");
 s = MakeString (T,Macros,&mct); /* Evaluate the string */
 for (i=exact=0;s[i]>0;i++) {
  /*Print string, excluding outermost pairs of angle brackets.*/
  if (s[i] == '<') {
   exact++;
   if (exact > 1) fprintf (out,"<");
  } else if (s[i] == '>') {
   exact--;
   if (exact > 0) fprintf (out,">");
  } else fprintf (out,"%c",s[i]);
 }
 free (s);
 for (i=0;i<79;i++) fprintf (out,"-"); /* Row of hyphens */
 fprintf (out,"\n\n");
}

/* MacroExpansion parses and evaluates a particular macro */

char *MacroExpansion (char *T, int *pos, MT Macros, int *mct) {

  char *s, *t;
  int i, exact, act, p;
  char args[10][33];

 act = exact = 0;
 s = (char *)malloc (1000);
 for (i=0;i<1000;i++) s[i] = 0;
 for ((*pos)++;T[*pos]!=']'||exact;(*pos)++) {
   /* Read through macro char by char */
   /* ] means we're done */
  if (T[*pos] == '<') { /* Angle brackets mean no parsing */
   exact++;
   if (exact > 1) s[strlen(s)] = '<';
  } else if (T[*pos] == '>') {
   exact--;
   if (exact > 0) s[strlen(s)] = '>';
  } else if (T[*pos] == ',' && !exact) {
        /* comma means we've read one */
   strcpy (args[act++],s);        /* argument so store it */
   for (i=0;i<1000;i++) s[i] = 0;
  } else if (T[*pos] != '[' || exact) /* Regular char, just copy */
   s[strlen(s)] = T[*pos];
  else {  /* Nested macro, recursively evaluate */
   t = MacroExpansion (T,pos,Macros,mct);
   strcat (s,t);
   free (t);
  }
 }
 strcpy (args[act++],s); /* Now that we've read the macro, we evaluate*/
 for (i=0;i<1000;i++) s[i] = 0;
 if (strcmp(args[0],"def")==0) {  /* If it was a def, add it to list */
  strcpy (Macros[*mct][0],args[1]);
  strcpy (Macros[*mct][1],args[2]);
  (*mct)++;
 } else { /* Otherwise, search for definition of macro */
  for (i=0;strcmp (Macros[i][0],args[0])!=0;i++);
  p = exact = 0;
  for (p = exact = 0;Macros[i][1][p]>0;p++) { /* Parse definition */
   if (Macros[i][1][p] == '<') { /* Angle brackets mean ignore inside*/
    exact++;
    if (exact > 1) s[strlen(s)] = '<';
   } else if (Macros[i][1][p] == '>') {
    exact--;
    if (exact > 0) s[strlen(s)] = '>';
   } else if (Macros[i][1][p] == '$' && !exact) {
            /* If this is an argument*/
    strcat (s,args[Macros[i][1][p+1]-'0']);/* copy in value */
    p++;
   } else s[strlen(s)] =Macros[i][1][p];/*Regular character to copy in*/
  }
 }
 return s;
}

/* MakeString takes a string of text and expands the macros inside.
   Sometimes macro expansion creates new macros in the string.
   These are evaluated, and the process continues until no macros
   remain. */

char * MakeString (char *T, MT Macros, int *mct) {

  char *s, *t;
  int p, found, exact;

 found  = 0;
 s = (char*)malloc (1000);
 for (p=0;p<1000;p++) s[p] = 0;
 for (p=exact=0;T[p]>0;p++) { /* Process string char by char */
  if (T[p] == '<') exact++;
         /* Angle brackets allow for exact interpretation*/
  if (T[p] == '>') exact--;
  if (T[p]=='[' && !exact) { /* Found a macro, expand */
   t = MacroExpansion (T,&p,Macros,mct);
   found = 1;
   strcat (s,t);
   free (t);
  } else s[strlen(s)] = T[p];
 }
 if (found) { /* If any macros are found, we do this again. */
  t = MakeString (s,Macros,mct);
  free (s);
  s = t;
 }
 return s;
}