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

#define TOK_NUMBER 1
#define TOK_VARIABLE 2
#define TOK_OPERATOR 3
#define TOK_WHITESPACE 4
#define TOK_NEWLINE 5
#define TOK_EOF 6

#define OPERATORS "+-*/^"

static int toktype[256]; /* all default to 0 */

char *get_tok(void)
{
    static char buff[128]; // TODO: remember to add length check later
    static int pend = -2;
    int initc, c;
    char *s = buff;
    c = initc = (pend >= -1 ? pend : getchar()); pend = -2;
    if (c != EOF) {
       for (;;) {
          if (isalpha(c) && islower(c)) c = toupper(c);
          *s++ = c;
          c = getchar();
          if ((!isalpha(c) && !isdigit(c)) || (toktype[c] != toktype[initc])) break;
       }
       pend = c;
    }
    *s = '\0';
    return strdup(buff);
}

char *op[4];

int top = -1, nest = -1;

void operate(char *op)
{
  char *s;
  switch (*op) {
  case '+': s = "ADD"; break;
  case '-': s = "SUB"; break;
  case '*': s = "MUL"; break;
  case '/': s = "DIV"; break;
  case '^': s = "EXP"; break;
  default: fprintf(stderr, "Bad operator %s\n", op); exit(1);
  }
  fprintf(stdout, "        %s\n", s);
}

void operand(char *s) {
  if ((nest+1 > 0) && (top != nest)) {fprintf(stderr, "Missing operator before %s\n", s); exit(1);}
  nest += 1;
  fprintf(stdout, "        PUSH%s%s\n", (isdigit(*s) ? " #":" "), s);
}

void operator(char *s) {
  if (top+1 != nest) {
    if (top < 0) {
      fprintf(stderr, "Missing initial operand before %s\n", s);
    } else {
      fprintf(stderr, "Missing operand between %s and %s\n", op[top], s);
    }
    exit(1);
  }
  // RULE 2:  a * b + c => (a*b) + c ... do it before we push the next operand
  while ((top > 0) && (prec(op[top]) > prec(s))) {
    // stack is now just ... + a*b
    nest -= 1; /* pop 2 operands, push 1 */
    operate(op[top--]);
  }
  // RULE 1:  a + b + c => (a+b) + c ... do it before we push the next operand
  if ((top >= 0) && (prec(op[top]) == prec(s))) {
    // stack is now just a + b
    nest -= 1; /* pop 2 operands, push 1 */
    operate(op[top--]);
  }
  op[++top] = s;
}

void evaluate(void) {
  if (nest <0 && top < 0) return; /* nothing entered */
  if (nest == top) {fprintf(stderr, "Missing operand after final %s\n", op[top]); exit(1);}
  while (top >= 0) {
      operate(op[top--]);
  }
  fprintf(stdout, "        PRINT\n");
  nest = top = -1;
}

int prec(char *op) {
    return (strchr(OPERATORS, *op)-OPERATORS)/2; /* slightly hacky tweak for '+'='-' and '*'='/' */
}

int main(int argc, char **argv)
{
    char *tok, *s;
    int i;

    toktype[0] = TOK_EOF; toktype['\n'] = TOK_NEWLINE;
    toktype[' '] = TOK_WHITESPACE; toktype['\t'] = TOK_WHITESPACE; 
    for (i = 'A'; i <= 'Z'; i++) toktype[i] = TOK_VARIABLE;
    for (i = '0'; i <= '9'; i++) toktype[i] = TOK_NUMBER;
    for (s = OPERATORS; *s != '\0'; s++) toktype[*s] = TOK_OPERATOR;

    for (;;) {
	tok = get_tok();
	switch (toktype[*tok]) {
		case TOK_NUMBER:
                    operand(tok);
		    break;
		case TOK_VARIABLE:
                    operand(tok);
		    break;
		case TOK_OPERATOR:
                    operator(tok);
		    break;
		case TOK_WHITESPACE:
		    continue;
		case TOK_NEWLINE:
                    evaluate();
		    break;
		case TOK_EOF:
                    evaluate();
                    exit(0);
		default:
                    fprintf(stderr, "Bad character in input: %s\n", tok);
                    exit(1);
        }
    }
    exit(0);
    return(0);
}