/* *************************************************************** *
 *                                                                 *
 *                                                                 *
 *                                                                 *
 *                                                                 *
 *                                                                 *
 *                                                                 *
 *                                                                 *
 * *************************************************************** */

/*                                                                 */
/*                            */
#define BGN 256         /*    */
#define END 257         /*    */
#define NUM 258         /*    */
#define TERM_MAX 258
/*                            */
#define Expr 259

/*                                          *
 *                                          */
typedef double YYSTYPE;  /*                                              */
extern YYSTYPE yylval;
/*                                                                       *
 *                                                                       */

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

YYSTYPE yylval;

/* *************************************************************** *
 *                                                                 *
 * *************************************************************** */

struct _elem { /*                    */
  int token;   /*                                      */
  YYSTYPE val; /*       */
};

typedef struct _elem elem;

elem stack[64]; /*                                                           */

elem* sp = stack; /*                            */

void push(int tok, YYSTYPE attr) { /*                          */
  sp->token = tok;
  sp->val   = attr;
  sp++;  /*                                */
}

elem pop(void) { /*                        */
  if (sp == stack) {
    printf("Stack is empty.\n");
    return *sp;
  } else {
    sp--;
    return *sp;
  }
}

void clear_stack(void) {
  sp = stack;
}

elem* topmost_token_aux(elem* ptr) { /*                          */
  while(ptr->token > TERM_MAX) { /*                        */
    ptr--;
    if (ptr < stack) {
      printf("error: no terminal symbol in the stack.\n");
      return stack;
    }
  }
  /* ptr->token <= TERM_MAX */
  return ptr;
}

elem* topmost_token(void) { /*                          */
  return topmost_token_aux(sp-1);
}

void debug_token(int t, YYSTYPE v) {
    switch (t) {
    case BGN:  printf("BGN"); break;
    case END:  printf("END"); break;
    case NUM:  printf("NUM_(%.3f)", v); break;
    case Expr: printf("Expr_(%.3f)", v); break;
    default:
      printf("'%c'", t); break;
    }
}

void debug_stack(void) { /*                                      */
  elem* sp0;

  printf("stack bottom <<");
  for(sp0=stack; sp0<sp; sp0++) {
        int t =     sp0->token;
        YYSTYPE v = sp0->val;

        printf(" | ");
        debug_token(t, v);
  }
  printf(" >> top\n");
}

/* *************************************************************** *
 *                                                                 *
 * *************************************************************** */

int yylex(void) { /*                            */
  int c;

  do {
    c = getchar();
  } while (c == ' ' || c == '\t');  /*                  */

  if (isdigit(c) || c == '.') {
    ungetc(c, stdin);
    scanf("%lf", &yylval);
    /*                                          */
    return NUM;
    /*                          */
  } else if (c == '\n') {
    return END; /*            */
  } else if (c == EOF) {
    exit(0);  /*                  */
  }
  /*                                                   */
  return c;
}

/* *************************************************************** *
 *                                                                 *
 *                                                                 *
 *   Expr -> NUM                                                   *
 *         | '(' Expr ')'                                          *
 *         | Expr '+' Expr                                         *
 *         | Expr '*' Expr                                         *
 * *************************************************************** */

/* *************************************************************** *
 *                                                                 *
 * *************************************************************** */
#define LT 0    /* <, Less Than */
#define EQ 1    /* =, Equal */
#define GT 2    /* >, Greater Than */
#define ERR 3   /*         Error */

int op_index(elem* p) { /*                                         */
  switch (p->token) {
  case BGN:  return 0;
  case '+':  return 1;
  case '*':  return 2;
  case '(':  return 3;
  case ')':  return 4;
  case NUM:  return 5;
  case END:  return 6;
  default:   printf("op_index: invalid token (");
             debug_token(p->token, p->val);
             printf("). \n");
             exit(1);
             return 0;
  }
}

char prec_table[6][6] = { /*                  */
  /*                                                 */
          /* '+',  '*',  '(',  ')',  NUM,  END */
  /* BGN */ {LT,   LT,   LT,   ERR,  LT,   EQ   },
  /* '+' */ {GT,   LT,   LT,   GT,   LT,   GT   },
  /* '*' */ {GT,   GT,   LT,   GT,   LT,   GT   },
  /* '(' */ {LT,   LT,   LT,   EQ,   LT,   ERR  },
  /* ')' */ {GT,   GT,   ERR,  GT,   ERR,  GT   },
  /* NUM */ {GT,   GT,   ERR,  GT,   ERR,  GT   },
};


/*                                */
int prec(elem* left, elem* right) {
  /*                                              */
  return prec_table[op_index(left)][op_index(right)-1];
}

elem* handle_left(void) { /*                                      */
  elem* next;
  elem* cur = topmost_token(); /*                                  */

  while (1) {
    next = topmost_token_aux(cur-1); /*                    */
    if (prec(next, cur) == LT) {
      return next+1; /*                         */
    } else { /* EQ */
      cur = next;
    }
  }
}

/* *************************************************************** *
 *                                                                 *
 * *************************************************************** */

int binary_op(YYSTYPE left, int op, YYSTYPE right) {
   printf("  reduce: Expr -> Expr ");  debug_token(op, 0);  printf(" Expr\n");
   switch (op) {
   case '+':
     return left+right;
   case '*':
     return left*right;
   default:
     printf("unknown binary operator: "); debug_token(op, 0); printf("\n");
     exit(7);
     return 0;
   }
}

int reduce(void) {  /*          */
  elem* left = handle_left();   /*                              */
  int num = sp - left;          /*                      */
  /* printf("reduce:\t"); */

  switch (num) {                /*                       */
  case 1: {
    elem data = pop();
    if (data.token == NUM) {
      /* Expr -> NUM */
      printf("   reduce: Expr -> NUM_(%.3f)\n", data.val);
      push(Expr, data.val);        /*                        */
      break;
    } else {
      printf("reduce: invalid operand (");
      debug_token(data.token, data.val);
      printf("). \n");
      exit(2);
    }
  }
  case 2: {
    elem data2 = pop(); elem data1 = pop();
    printf("reduce: invalid expression (");
    debug_token(data1.token, data1.val);
    printf(",");
    debug_token(data2.token, data2.val);
    printf("). \n");
    exit(3);
  }
  case 3: {
    elem data3 = pop(); elem data2 = pop(); elem data1 = pop();
    if (data1.token == '(' && data2.token == Expr && data3.token == ')') {
      /* Expr -> '(' Expr ')' */
      printf("   reduce: Expr -> ( Expr )\n");
      yylval = data2.val;
      push(Expr, yylval);
    } else if (data1.token == Expr && data3.token == Expr) {
      /*            */
      yylval = binary_op(data1.val, data2.token, data3.val);
      push(Expr, yylval);
    } else {
      printf("reduce: invalid expression (");
      debug_token(data1.token, data1.val);
      printf(",");
      debug_token(data2.token, data2.val);
      printf(",");
      debug_token(data3.token, data3.val);
      printf("). \n");
      exit(4);
    }
    break;
  }
  default:
    printf("reduce: syntax error\n");
    exit(5);
  }
  debug_stack();
  return 0;
}

/* *************************************************************** *
 *                                                                 *
 * *************************************************************** */
int yyparse(void) {
  elem* top;
  elem next;
  char relation; /*      */

  push(BGN, 0 /*            */); /*                              */
  next.token = yylex(); /*                      */
  next.val   = yylval;
  debug_stack();
  while (1) {
    top = topmost_token();  /*                            */

    printf("   comparing ");
    debug_token(top->token, top->val);
    printf(" and ");
    debug_token(next.token, next.val);
    printf(": ");

    if (next.token == END && top->token == BGN) {
      printf("   shift\n"); /*            */
      push(next.token, 0 /*        */);
      debug_stack();
      printf("   finish\n"); /*            */
      clear_stack();
      return 0; /*            */
    }

    relation = prec(top, &next);
    if (relation == LT || relation == EQ) {     /*        */
      printf("   shift\n"); /*            */
      push(next.token, next.val);
      debug_stack();
      next.token = yylex();    /*                        */
      next.val   = yylval;
      /* printf ("\ntoken=%d\n", next.token); *//*            */
    } else if (relation == GT) {                /*      */
      if (reduce()) { /*                    */
        return 1;
      }
    } else { /*                         */
      printf("yyparse: invalid look-ahead (");
      debug_token(next.token, next.val);
      printf("). \n");
      exit(6);
    }
  }
}

int main(void) {
  while (1) {
    if(yyparse()==0) { /* 0            */
      printf("   result: %g\n", yylval);
    }
  }

  return 0;
}