// Infix to postfix for subset of C expressions
// BPW, 9/2012
// BPW, 2/2014, included stack and output tracing

#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};
int alphaSize;
char program[1000];
int programSize;

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

int nextSymbol; // Simple scan

char postfix[1000];
int postfixLength=0;
int waitingOperands=0; // Indicates hypothetical unconsumed operands

int symbol2prec(char ch)
{
int i;

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

void readInput()
{
int i,j;

alphaSize=strlen(alpha);
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<alphaSize-2 && program[i]!=alpha[j];j++)
    ;
  if (j==alphaSize-2)
  {
    printf("bonk on input %c\n",program[i]);
    exit(0);
  }
}
// Check $ symbols
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
int p;

lastSymbol='(';   // Safe way to initialize this
operatorStack[++operatorSP]=0;  // push initial $ to stack
nextSymbol=1;
for (nextSymbol=1; nextSymbol<programSize;nextSymbol++)
{
  printf("Input: %c",program[nextSymbol]);
  printf(" Stack: ");
  for (p=0;p!=operatorSP+1;p++)
    printf("%c",program[operatorStack[p]]);
  printf(" Output: ");
  for (p=0;p<postfixLength;p++)
    printf("%c", postfix[p]);
  printf("\n");

  checkAdjacentSymbols(lastSymbol,program[nextSymbol]);
  if (program[nextSymbol]>='a' && program[nextSymbol]<='z')
  {
    postfix[postfixLength++]=program[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) // Can't be true due to other checks?
          {
            printf("No operands for ! at position %d\n",
              operatorStack[operatorSP]);
            exit(0);
          }
          postfix[postfixLength++]='!';
          break;
        case '*':   case '+':   case '<':   case '&':   case '|':
          if (waitingOperands<2) // Can't be true due to other checks?
          {
            printf("Only %d operands for %c at position %d\n",
              waitingOperands,program[operatorStack[operatorSP]],
              operatorStack[operatorSP]);
            exit(0);
          }
          postfix[postfixLength++]=program[operatorStack[operatorSP]];
          waitingOperands--;
          break;
        default:  // Can't be true due to other checks?
          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
}

main()
{
int i,j;


readInput();

translate();

if (waitingOperands!=1)  // Can't be true due to other checks?
  printf("Extra operands\n");
if (operatorSP!=1)
  printf("Stack not empty\n");
postfix[postfixLength]='\0';
printf("%s\n",postfix);
}