/* *************************************************************** *
 * 演算子順位法による構文解析                                      *
 *                                                                 *
 * 1+2*3のような式を構文解析して、計算結果（この場合 7）を出力する *
 *                                                                 *
 * 表 (prec_tableと op_index)と構文規則 (reduce)を書き換えて       *
 * 使用してください。                                              *
 * *************************************************************** */

/* マクロの定義 --- 終端記号・非終端記号を表す定数を定義する */
/* ここからは終端記号、       */
#define BGN 256         /* 始 */
#define END 257         /* 終 */
#define NUM 258         /* 数値 */
#define TERM_MAX 258
/* ここからは非終端記号の定義 */
#define Expr 259

/* 字句解析部が返す ``属性'' (yylval)の型   *
 *  Yacc (Bison)と同じ形式にする。          */ 
typedef double YYSTYPE;  /* 使用するトークンの属性の型に応じて変更する。*/
extern YYSTYPE yylval;
/* 字句解析部に flexが生成する関数を用いる場合は、ここまでをヘッダーファ *
 * イルとして分離する。                                                  */

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

YYSTYPE yylval;

/* *************************************************************** *
 * スタックの実装                                                  *
 * *************************************************************** */  

struct _elem { /* スタックの要素の型 */
  int token;   /* トークンの種類、259以上は非終端記号 */
  YYSTYPE val; /* 属性値 */
};

typedef struct _elem elem;

elem stack[64]; /* トイプログラムなのでとりあえずスタックの大きさは 64で十分 */

elem* sp = stack; /* 大域変数: スタックポインタ */ 

void push(int tok, YYSTYPE attr) { /* スタックにプッシュする。 */
  sp->token = tok;
  sp->val   = attr;
  sp++;  /* スタックは下に伸びることに注意 */
}

elem pop(void) { /* スタックをポップする。 */
  if (sp == stack) {
    printf("スタックが空です。\n");
    return *sp;
  } else {
    sp--;
    return *sp;
  }
}

elem* topmost_token_aux(elem* ptr) { /* topmost_tokenの補助関数 */
  while(ptr->token > TERM_MAX) { /* ptrは非終端記号を指す */
    ptr--;
  }
  /* ptr->token <= TERM_MAX */
  return ptr;
}

elem* topmost_token(void) { /* スタックの先頭の終端記号 */
  return topmost_token_aux(sp-1);
}

/* *************************************************************** *
 * 字句解析部 （flexが生成する関数に置き換えても良い。）           *
 * *************************************************************** */

int yylex(void) { /* 次のトークンを返す。 */
  int c;

  do {
    c = getchar();
  } while (c == ' ' || c == '\t');  /* 空白を読みとばす */

  if (isdigit(c) || c == '.') {
    ungetc(c, stdin);
    scanf("%lf", &yylval);
    /* ``値''は yylvalという変数に代入して返す。*/
    return NUM;
    /* NUMというトークンを返す。*/
  }

  if (c == '\n') {
    return END; /* 終りの記号 */
  }

  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   /* エラー */

int op_index(int token) { /* 表を引きやすいように連続した数値に写す。*/
  switch (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("不正な構文要素 (%d)。\n", token);
            exit(1);
            return 0; 
  }
}

char prec_table[6][6] = { /* 演算子順位表本体 */
  /* 行に ENDがないこと、列に BGNがないことに注意。*/
          /* '+',  '*',  '(',  ')',  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(int left, int right) {
  /* leftと 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->token, cur->token) == LT) {
      return next+1; /* nextの手前が求める場所 */
    } else { /* EQ */
      cur = next;
    }
  }
}

/* *************************************************************** *
 * 構文規則の表現   必要に応じて変更する                           *
 * *************************************************************** */

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("Expr -> NUM\n"); */
      push(Expr, data.val);        /* ポップしてすぐプッシュ */
      break;
    } else {
      printf("エラー: 不正なオペランド (%d)。\n", data.token);
      exit(2);
    }
  }
  case 2: {
    elem data2 = pop(); elem data1 = pop();
    printf("エラー: 不正な式 (%d, %d)。\n", data1.token, data2.token);
    exit(3);
  }
  case 3: {
    elem data3 = pop(); elem data2 = pop(); elem data1 = pop();
    if (data1.token == '(' && data2.token == Expr && data3.token == ')') {
      /* Expr -> '(' Expr ')' */
      /* printf("Expr -> '(' Expr ')'\n"); */
      yylval = data2.val;
      push(Expr, yylval);
    } else if (data1.token == Expr && data2.token == '+' && data3.token == Expr) {
      /* Expr -> Expr + Expr */
      /* printf("Expr -> Expr '+' Expr\n"); */
      yylval = data1.val+data3.val;
      push(Expr, yylval);
    } else if (data1.token == Expr && data2.token == '*' && data3.token == Expr) {
      /* Expr -> Expr * Expr */
      /* printf("Expr -> Expr '*' Expr\n"); */
      yylval = data1.val*data3.val;
      push(Expr, yylval);
    } else {
      printf("エラー: 不正な式 (%d, %d, %d)。\n",
             data1.token, data2.token, data3.token);
      exit(4);
    }
    break;
  }
  default:
    printf("構文エラー\n");
    exit(5);
  }
  return 0;
}

/* *************************************************************** *
 * 構文解析関数本体                                                *
 * *************************************************************** */
int yyparse(void) {
  int tok; 
  elem* top; 
  char relation; /* 関係 */
  
  push(BGN, 0 /* ダミー */); /* 始記号をスタックに積んでおく */
  tok = yylex(); /* 最初のトークン */
  /* printf ("\ntoken=%d\n", tok); *//* デバッグ用 */
  while (1) {
    top = topmost_token();  /* スタックのトップの終端記号 */
    if (tok == END && top->token == BGN) {
      return 0; /* 成功で終了 */
    }
    relation = prec(top->token, tok);
    if (relation == LT || relation == EQ) {     /* シフト */
      /* printf("shift\n"); *//* デバッグ用 */
      push(tok, yylval);
      tok = yylex();    /* 次のトークンを読み込む */
      /* printf ("\ntoken=%d\n", tok); *//* デバッグ用 */
    } else if (relation == GT) {                /* 還元 */
      if (reduce()) { /* 0以外は構文エラー */
        return 1;
      }
    } else { /* 表の空欄部分 --- エラー */
      printf("不正な構文要素 (%d)。\n", tok);
      exit(6);
    }
  }
}

int main(void) {
  while (1) {
    if(yyparse()==0) { /* 0は正常終了 */
      printf("答: %g\n", yylval);
    }
  }
}