/* Problem 5--Logical Evaluation
   This was easily handled by using recursive descent parsing.
   Recursively parse each subexpression until you have completely
   evaluated the expression. */

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

int main (int argc, char **argv);
int Parse (char *logic, char *vars, char **rem);

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

  FILE *in, *out;
  char vars[27], logic[81], *rem;
  int cs;

 in = fopen ("prob5.in","r");
 out = fopen ("prob5.out","w");
 cs = 0;
 while (1) { /* Read in the variable list */
  fscanf (in,"%s",vars);
  if (feof (in)) break;
  fscanf (in,"%s",logic); /* Parse expression */
  fprintf (out,"Case %d: %s\n",++cs,
          Parse (logic,vars,&rem)?"TRUE":"FALSE");
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Parse parses a logical expression with respect to the specified
   variables.  Rem points to the part of the string after the specified
   subexpression is parsed. */
int Parse (char *logic, char *vars, char **rem) {

  char *r, c, *s;
  int a, b;

 if (logic[0] >= 'A' && logic[0] <= 'Z') {
  *rem = &logic[1]; /* If basic variable just evaluate it */
  return vars[logic[0]-'A']=='1';
 } /*If negation, parse the rest and negate */
 if (logic[0] == '~') return !Parse (&logic[1],vars,rem);
 a = Parse (&logic[1],vars,&r);/*Parse first subexpr */
 c = *r; /*Get & or | operation */
 b = Parse (&r[1],vars,&s); /*Parse second subexpr */
 *rem = &s[1]; /* Skip over closing ) */
 if (c=='&') return a&b;
 return a|b;
}