// Infix to postfix for subset of C expressions
// BPW, 9/2012

// Also computes abstract syntax tree

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

// Not much of a language, but representative of expression elements
// a-z identifiers
// + additive operator
// * multiplicative operator
// < comparison
// & logical and
// | logical or
// ! logical not
// ( 
// )
// Expression is delimited by $ and #

// Operators and corresponding precedences
char alpha[]={'(',')','!','*','+','<','&','|','$','#'};
int prec[]=  {20, 30, 90, 80, 70, 60, 50, 40, 0,  10};

char program[1000];
int programSize;

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 symbol2prec(char ch)
{
int i;

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

void readInput()
{
int i,j;

scanf("%s",program);
programSize=strlen(program);
for (i=1;i<programSize-1;i++)
{ // Check non $ and # symbols
  if (program[i]>='a' && program[i]<='z')
    continue;

  for (j=0;j<sizeof alpha-2 && program[i]!=alpha[j];j++)
    ;
  if (j==sizeof alpha-2)
  {
    printf("bonk on input %c\n",program[i]);
    exit(0);
  }
}
// Check $ and # symbols to bracket input
if (program[0]!='$' || program[programSize-1]!='#')
{
  printf("$ error\n");
  exit(0);
}
}

void checkAdjacentSymbols(char first,char second)
{ // Streamlined check on adjacent symbols in input
int firstIsOperand=first==')' || first>='a' && first<='z',
    secondIsOperand=second>='a' && second<='z' || second=='('
                    || second=='!';

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

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

lastSymbol='(';   // Safe way to initialize this
operatorStack[++operatorSP]=0;  // push initial $ to stack
nextSymbol=1;
for (nextSymbol=1; nextSymbol<programSize;nextSymbol++)
{
  checkAdjacentSymbols(lastSymbol,program[nextSymbol]);
  if (program[nextSymbol]>='a' && program[nextSymbol]<='z')
  {
    postfixIndex[postfixLength++]=nextSymbol;
    waitingOperands++;
  }
  else if (program[nextSymbol]=='(' || program[nextSymbol]=='!')
    operatorStack[++operatorSP]=nextSymbol;
  else
  {
    // Move ripe operators to postfix.  Everything is left-associative
    while (symbol2prec(program[nextSymbol])
          <=symbol2prec(program[operatorStack[operatorSP]]))
    {
      switch(program[operatorStack[operatorSP]])
      {
        case '(':
          printf("Parenthesis mismatch detected at pos %d\n",nextSymbol);
          exit(0);
        case '!':
          if (waitingOperands<1)
          {
            printf("No operands for ! at position %d\n",
              operatorStack[operatorSP]);
            exit(0);
          }
          postfixIndex[postfixLength++]=operatorStack[operatorSP];
          break;
        case '*':   case '+':   case '<':   case '&':   case '|':
          if (waitingOperands<2)
          {
            printf("Only %d operands for %c at position %d\n",
              waitingOperands,program[operatorStack[operatorSP]],
              operatorStack[operatorSP]);
            exit(0);
          }
          postfixIndex[postfixLength++]=operatorStack[operatorSP];
          waitingOperands--;
          break;
        default:
          printf("Uncovered case: %c\n",program[operatorStack[operatorSP]]);
          break;
      } // end switch

      operatorSP--;
    } // end while

    if (program[nextSymbol]==')')
      if (program[operatorStack[operatorSP]]=='(')
        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 (program[postfixIndex[i]]>='a' && program[postfixIndex[i]]<='z')
  {
    ast[postfixIndex[i]].left=(-1);
    ast[postfixIndex[i]].right=(-1);
    evalStack[++evalSP]=postfixIndex[i];
  }
  else if (program[postfixIndex[i]]=='!')
  {
    ast[postfixIndex[i]].left=evalStack[evalSP--];
    ast[postfixIndex[i]].right=(-1);
    evalStack[++evalSP]=postfixIndex[i];
  }
  else
  {
    ast[postfixIndex[i]].right=evalStack[evalSP--];
    ast[postfixIndex[i]].left=evalStack[evalSP--];
    evalStack[++evalSP]=postfixIndex[i];
  }

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("%c (%d,%d,%d)\n",program[x],x,ast[x].left,ast[x].right);
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: ");
for (i=0;i<postfixLength;i++)
  printf("%c",program[postfixIndex[i]]);
printf("\n");

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