// Infix to postfix for subset of C expressions
// 3302 lab2fall12 (with connections to lab1fall12)
// BPW, 9/2012

// Also computes abstract syntax tree
// Does Java-style type checking, i.e. bools are not confused with ints

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

// Not much of a language, but representative of expression elements
// 10 character lower-case alphabetic identifiers (name)
// +, - numop
// *, / numop
// <, >, ==, !=, <=, >= compop
// && boolop
// || boolop
// ! boolop
// ( lparen
// ) rparen
// ? condop
// : condsep
// Expression is delimited by $ and #

// Operators and corresponding precedences
char alpha[][3]={"(",")","!","*","/","+","-","<",">","<=",">=","==","!=","&&","||","?",":","$","#"};
int prec[]=     {10, 15, 60, 55, 55, 50, 50, 45, 45, 45,  45,  40,  40,  35,  30,  25, 25, 0,  5};
//int prec[]=     {10, 15, 60, 55, 55, 50, 50, 45, 45, 45,  45,  40,  40,  35,  30,  25, 20, 0,  5};
//int prec[]=     {20, 30, 90, 80, 80, 70, 70, 60, 60, 60,  60,  55,  55,  50,  40,  33, 32, 0,  10};

int m,n,p;  // #s of boolean identifier, integer identifiers, & tokens from lab 1

char **boolId,**intId;  // Symbol tables

typedef enum {UNKNOWN,BOOLVAL,INTVAL} expType;

typedef struct {
char token[11];
char classif[8];
expType typ;
} tokenPair;

tokenPair *program;

int operatorStack[2000]; // entries point to program[]
int operatorSP=(-1);     // initial empty stack

int nextSymbol; // Simple scan

int postfixIndex[1000]; // Needed to build AST
int postfixLength=0;
int waitingOperands=0; // Indicates hypothetical unconsumed operands

typedef struct
{
  int left,right;
} astType;
astType ast[1000];

int isName(tokenPair x)
{
return strcmp(x.classif,"name")==0;
}

int isNamePicBool(tokenPair x)
{
return strcmp(x.classif,"name")==0
    || strcmp(x.classif,"pic")==0
    || strcmp(x.classif,"bool")==0;
}

int symbol2prec(char ch[11])
{
int i;

for (i=0;
     i<sizeof(alpha)/sizeof(*alpha) && strcmp(alpha[i],ch)!=0;
     i++)
  ;
if (i==sizeof(alpha)/sizeof(*alpha))
{
  printf("symbol2prec: bad symbol %c\n",ch);
  exit(0);
}
return prec[i];
}

void readInput()
{
int i,j;

scanf("%d %d %d",&m,&n,&p);
p+=2;  // For $ and #

boolId=(char**) malloc(m*sizeof(char*));
intId=(char**) malloc(n*sizeof(char*));
program=(tokenPair*) malloc(p*sizeof(tokenPair));
if (!boolId || !intId || !program)
{
  printf("malloc failed\n");
  exit(0);
}

// Load symbol tables
for (i=0;i<m;i++)
{
  boolId[i]=(char*) malloc(11*sizeof(char));
  if (!boolId[i])
  {
    printf("malloc failed\n");
    exit(0);
  }
  scanf("%10s",boolId[i]);
}
for (i=0;i<n;i++)
{
  intId[i]=(char*) malloc(11*sizeof(char));
  if (!intId[i])
  {
    printf("malloc failed\n");
    exit(0);
  }
  scanf("%10s",intId[i]);
}

strcpy(program[0].token,"$");
strcpy(program[0].classif,"$");
for (i=1;i<p-1;i++)
  scanf("%10s %7s",program[i].token,program[i].classif);
strcpy(program[p-1].token,"#");
strcpy(program[p-1].classif,"#");

for (i=1;i<p-1;i++)
{ // Check non $ and # symbols
  if (isName(program[i]))
  { // Classify name as bool or int
    for (j=0;
         j<m && strcmp(program[i].token,boolId[j])!=0;
         j++)
      ;
    if (j<m)
    {
      program[i].typ=BOOLVAL;
      continue;
    }

    for (j=0;
         j<n && strcmp(program[i].token,intId[j])!=0;
         j++)
      ;
    if (j<n)
    {
      program[i].typ=INTVAL;
      continue;
    }
    printf("Untyped name %s\n",program[i].token);
    exit(0);
  }
  else if (strcmp(program[i].classif,"pic")==0)
    program[i].typ=INTVAL;
  else if (strcmp(program[i].classif,"bool")==0)
    program[i].typ=BOOLVAL;
  else
    program[i].typ=UNKNOWN;

  for (j=0;
       j<sizeof(alpha)/sizeof(*alpha)-2 && strcmp(program[i].token,alpha[j]);
       j++)
    ;
  if (j==sizeof(alpha)/sizeof(*alpha))
  {
    printf("bonk on input %s\n",program[i].token);
    exit(0);
  }
}
}

void checkAdjacentSymbols(tokenPair first,tokenPair second)
{ // Streamlined check on adjacent symbols in input
int firstIsOperand=first.token[0]==')' || isNamePicBool(first),
    secondIsOperand=isNamePicBool(second) || second.token[0]=='('
                    || strcmp(second.token,"!")==0;

if (firstIsOperand==secondIsOperand)
{
  printf("%s followed by %s\n",first.token,second.token);
  exit(0);
}
}

int isBinOp(tokenPair x)
{
return strcmp(x.token,"+")==0
    || strcmp(x.token,"-")==0
    || strcmp(x.token,"*")==0
    || strcmp(x.token,"/")==0
    || strcmp(x.token,"<")==0
    || strcmp(x.token,">")==0
    || strcmp(x.token,"==")==0
    || strcmp(x.token,"!=")==0
    || strcmp(x.token,"<=")==0
    || strcmp(x.token,">=")==0
    || strcmp(x.token,"&&")==0
    || strcmp(x.token,"||")==0
    || strcmp(x.token,"?")==0  // even though ternary, ? : is treated as two binary ops, see postfix2ast()
    || strcmp(x.token,":")==0;
}

void translate()
{
tokenPair lastSymbol;  // For detecting improper adjacent symbols

strcpy(lastSymbol.token,"(");   // Safe way to initialize this
strcpy(lastSymbol.classif,"lparen");
operatorStack[++operatorSP]=0;  // push initial $ to stack
nextSymbol=1;
for (nextSymbol=1; nextSymbol<p;nextSymbol++)
{
  checkAdjacentSymbols(lastSymbol,program[nextSymbol]);
  if (isNamePicBool(program[nextSymbol]))
  {
    postfixIndex[postfixLength++]=nextSymbol;
    waitingOperands++;
  }
  else if (program[nextSymbol].token[0]=='('
        || strcmp(program[nextSymbol].token,"!")==0)
    operatorStack[++operatorSP]=nextSymbol;
  else
  {
    // Move ripe operators to postfix.  Everything is left-associative
    // except ? :
    while (symbol2prec(program[nextSymbol].token)<symbol2prec(program[operatorStack[operatorSP]].token)
    || symbol2prec(program[nextSymbol].token)==symbol2prec(program[operatorStack[operatorSP]].token)
       && strcmp(program[operatorStack[operatorSP]].token,":")==0
       && strcmp(program[nextSymbol].token,":")==0)
    {
      if (strcmp(program[operatorStack[operatorSP]].token,"(")==0)
      {
        printf("Parenthesis mismatch detected at pos %d\n",nextSymbol);
        exit(0);
      }
      else if (strcmp(program[operatorStack[operatorSP]].token,"!")==0)
      {
        if (waitingOperands<1)
        {
          printf("No operands for ! at position %d\n",
            operatorStack[operatorSP]);
          exit(0);
        }
        postfixIndex[postfixLength++]=operatorStack[operatorSP];
      }
      else if (strcmp(program[operatorStack[operatorSP]].token,":")==0)
      {
        if (strcmp(program[operatorStack[operatorSP-1]].token,"?")!=0)
        {
          printf(": at position %d expects ? at position %d (%s instead)\n",
            operatorStack[operatorSP],operatorStack[operatorSP-1],
            program[operatorStack[operatorSP-1]].token);
          exit(0);
        }
        // Process :
        if (waitingOperands<2)
        {
          printf("Only %d operands for %s at position %d\n",
            waitingOperands,program[operatorStack[operatorSP]].token,
            operatorStack[operatorSP]);
          exit(0);
        }
        postfixIndex[postfixLength++]=operatorStack[operatorSP--];  // -- needed here
        waitingOperands--;
        // Process matching ?
        if (waitingOperands<2)
        {
          printf("Only %d operands for %s at position %d\n",
            waitingOperands,program[operatorStack[operatorSP]].token,
            operatorStack[operatorSP]);
          exit(0);
        }
        postfixIndex[postfixLength++]=operatorStack[operatorSP]; // -- before // end while
        waitingOperands--;
      }
      else if (strcmp(program[operatorStack[operatorSP]].token,"?")==0)
      {
        printf("Unmatched ? at position %d\n",operatorStack[operatorSP]);
        exit(0);
      }
      else if (isBinOp(program[operatorStack[operatorSP]]))
      {
        if (waitingOperands<2)
        {
          printf("Only %d operands for %s at position %d\n",
            waitingOperands,program[operatorStack[operatorSP]].token,
            operatorStack[operatorSP]);
          exit(0);
        }
        postfixIndex[postfixLength++]=operatorStack[operatorSP];
        waitingOperands--;
      }
      else
        printf("Uncovered case: %s\n",program[operatorStack[operatorSP]].token);

      operatorSP--;
    } // end while

    if (program[nextSymbol].token[0]==')')
      if (program[operatorStack[operatorSP]].token[0]=='(')
        operatorSP--;
      else
      {
        printf(") at position %d doesn't match a (\n",nextSymbol);
        exit(0);
      }
    else
      operatorStack[++operatorSP]=nextSymbol;
  }

  lastSymbol=program[nextSymbol];
} // end for
}

int postfix2ast()
// This is essentially a postfix evaluator:
// operands are just pushed to a stack
// operators pop the appropriate number of operands
// and push the result (root of a subtree) back to the stack.
{
int evalStack[1000];
int evalSP=(-1);
int i;

for (i=0;i<postfixLength;i++)
  if (isNamePicBool(program[postfixIndex[i]]))
  {
    // typ was set in readInput()
    ast[postfixIndex[i]].left=(-1);
    ast[postfixIndex[i]].right=(-1);
    evalStack[++evalSP]=postfixIndex[i];
  }
  else if (strcmp(program[postfixIndex[i]].token,"!")==0)
  {
    ast[postfixIndex[i]].left=evalStack[evalSP--];
    ast[postfixIndex[i]].right=(-1);
    if (program[ast[postfixIndex[i]].left].typ!=BOOLVAL)
    {
      printf("Type error at position %d\n",ast[postfixIndex[i]].left);
      exit(0);
    }
    program[postfixIndex[i]].typ=BOOLVAL;
    evalStack[++evalSP]=postfixIndex[i];
  }
  else if (strcmp(program[postfixIndex[i]].classif,"numop")==0)
  {
    ast[postfixIndex[i]].right=evalStack[evalSP--];
    ast[postfixIndex[i]].left=evalStack[evalSP--];
    if (program[ast[postfixIndex[i]].left].typ!=INTVAL)
    {
      printf("Type error at position %d\n",ast[postfixIndex[i]].left);
      exit(0);
    }
    if (program[ast[postfixIndex[i]].right].typ!=INTVAL)
    {
      printf("Type error at position %d\n",ast[postfixIndex[i]].right);
      exit(0);
    }
    program[postfixIndex[i]].typ=INTVAL;
    evalStack[++evalSP]=postfixIndex[i];
  }
  else if (strcmp(program[postfixIndex[i]].classif,"boolop")==0)
  {
    ast[postfixIndex[i]].right=evalStack[evalSP--];
    ast[postfixIndex[i]].left=evalStack[evalSP--];
    if (program[ast[postfixIndex[i]].left].typ!=BOOLVAL)
    {
      printf("Type error at position %d\n",ast[postfixIndex[i]].left);
      exit(0);
    }
    if (program[ast[postfixIndex[i]].right].typ!=BOOLVAL)
    {
      printf("Type error at position %d\n",ast[postfixIndex[i]].right);
      exit(0);
    }
    program[postfixIndex[i]].typ=BOOLVAL;
    evalStack[++evalSP]=postfixIndex[i];
  }
  else if (strcmp(program[postfixIndex[i]].classif,"compop")==0)
  {
    ast[postfixIndex[i]].right=evalStack[evalSP--];
    ast[postfixIndex[i]].left=evalStack[evalSP--];
    if (program[ast[postfixIndex[i]].left].typ!=program[ast[postfixIndex[i]].right].typ)
    {
      printf("Type conflict at position %d\n",ast[postfixIndex[i]].right);
      exit(0);
    }
    program[postfixIndex[i]].typ=BOOLVAL;
    evalStack[++evalSP]=postfixIndex[i];
  }
  else if (strcmp(program[postfixIndex[i]].classif,"condop")==0)
  { // ?
    ast[postfixIndex[i]].right=evalStack[evalSP--];
    ast[postfixIndex[i]].left=evalStack[evalSP--];
    if (program[ast[postfixIndex[i]].left].typ!=BOOLVAL) // Check expression to left of ?
    {
      printf("Type error at position %d\n",ast[postfixIndex[i]].left);
      exit(0);
    }
    // Type consistency for matching : has already been checked
    program[postfixIndex[i]].typ=program[ast[postfixIndex[i]].right].typ;
    evalStack[++evalSP]=postfixIndex[i];
  }
  else if (strcmp(program[postfixIndex[i]].classif,"condsep")==0)
  { // :
    ast[postfixIndex[i]].right=evalStack[evalSP--]; // Expression to right of :
    ast[postfixIndex[i]].left=evalStack[evalSP--];  // Expression to left of :
    if (program[ast[postfixIndex[i]].left].typ!=program[ast[postfixIndex[i]].right].typ)
    {
      printf("Type conflict at position %d\n",ast[postfixIndex[i]].right);
      exit(0);
    }
    program[postfixIndex[i]].typ=program[ast[postfixIndex[i]].left].typ;
    evalStack[++evalSP]=postfixIndex[i];
  }
  else
  {
    printf("postfix2ast problem %d %s %s\n",postfixIndex[i],program[postfixIndex[i]].token,
      program[postfixIndex[i]].classif);
    exit(0);
  }

return postfixIndex[postfixLength-1];
}

void printAST(int x,int indent)
{
int i;

if (x==(-1))
  return;
printAST(ast[x].right,indent+1);
for (i=0;i<indent;i++)
  printf("  ");
printf("%s %s (%d,%d,%d,",program[x].token,program[x].classif,
  x,ast[x].left,ast[x].right);
switch(program[x].typ)
{
  case UNKNOWN:
    printf("UNKNOWN");
    break;
  case INTVAL:
    printf("INTVAL");
    break;
  case BOOLVAL:
    printf("BOOLVAL");
    break;
}
printf(")\n");
printAST(ast[x].left,indent+1);
}

main()
{
int i;
int astRoot;

readInput();

translate();

if (waitingOperands!=1)
  printf("Extra operands\n");
if (operatorSP!=1)
  printf("Stack not empty\n");
printf("Postfix: \n");
for (i=0;i<postfixLength;i++)
  printf("%d %s %s\n",postfixIndex[i],program[postfixIndex[i]].token,
    program[postfixIndex[i]].classif);

astRoot=postfix2ast();
printf("AST:\n");
printAST(astRoot,0);
}