/********************************************************************
  情報科学実験1　構文木表示プログラム tree.c (コンパイラ実験)


    作成者 : 掛下 哲郎
    作成日 : 平成7年3月7日

    本プログラムは、8ビット文字からなる文字列(長さ100文字以内)を入力し
    て、その構文解析を行い、構文解析木を出力するプログラムである。

    本プログラムは、入力終了をもって終了する。                        
**********************************************************************/

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

/* 定数の定義 */

#define  MAXLINELENGTH  102        /* 入力行の最大長+改行文字+NULL文字 */
#define  TRUE           1
#define  FALSE          0
#define  NUMBER         '0'        /* 数字を示す仮想トークン */
#define  END            '$'        /* 終端を示す仮想トークン */

/* 型の定義 */

typedef int Boolean;
typedef struct node {          /* 構文解析木の節点           */
    char        attribute;     /*   種類 数字:NUMBER その他:+,-,*,/,(,) */
    int         value;         /*   数字tokenの値            */
    struct node *left, *right; /*   左右の部分木へのポインタ */
} node;

/* 関数のプロトタイプ宣言 */

int  CharToInt(char ch);
Boolean validChar(char ch);
void gettoken(void);
node *factor(void);
node *term(void);
node *expression(void);
void PrintTree(node *ptr, int indent);
void deleteTree(node *ptr);

/* 大域変数の定義 */

char  line[MAXLINELENGTH];   /* 現在処理中の行       */
char  *lptr;                 /* 行 line 中の処理位置 */
struct {                     /* 現在処理中のtoken    */
    char  attribute;         /*   種類 数字:NUMBER 終端:END その他:+,-,*,/,(,) */
    int   value;             /*   数字tokenの値      */
} token; 
node      *root;             /* 構文解析木の根       */
Boolean   error;             /* エラーフラグ         */

/*************************
      関数の定義
**************************/

/*
 * 主プログラム
 */
int main(void)
{
    /* 初期設定を行う。 */
    error = FALSE; 
    printf("式 = ");

    /* 式が入力されている限り、以下の処理を繰り返す。*/
    while(fgets(line, MAXLINELENGTH, stdin) != NULL){

        /* 最初のtokenを切り出す。*/
	lptr = line;
	gettoken();

	/* 構文解析木を生成する。*/
	root = expression();

	/* エラーがなければ構文解析木を表示する。*/
        if(error == FALSE){
            printf("\n");
	    printf("◆式の木構造表現◆\n");
            printf("\n");
            PrintTree(root, 6);
        }

	/* 構文解析木を消去する。 */
	deleteTree(root);

	/* 次の行を入力する。 */
	error = FALSE;
	printf("\n");
	printf("式 = ");
    }

    /* 改行してプログラムを終了する。 */
    printf("\n");
    return 0;
}

/*
 * アスキー文字を数字に変換する。
 */
int CharToInt(char ch)
{
    return (int)ch-(int)'0';
}

/*
 * 正しい文字か確認する。
 */
Boolean validChar(char ch)         
{
    if((ch=='+') ||(ch=='-') ||(ch=='*') ||
       (ch=='/') ||(ch=='(') ||(ch==')') )
        return TRUE;
    else
        return FALSE;
}

/*
 * 次のtokenを切り出す。
 */
void gettoken(void)
{
    /* 空白を読み飛ばす。 */
    while(isspace(*lptr))
        lptr++;

    /* 入力行の終端ならば、関数を終了する。 */
    if(*lptr == NULL){
	token.attribute = END;
        return;
    }

    /* 数字tokenならば値を計算する。 */
    if(isdigit(*lptr)){
        token.attribute = NUMBER;
	token.value     = 0;
        while (isdigit(*lptr)){
            token.value = token.value*10 + CharToInt(*lptr);
	    lptr++;
	}
    }

    /* '+','-','*','/','(',')' のいずれかならば、そのまま格納する。*/
    else if(validChar(*lptr)){
        token.attribute = *lptr;
	lptr++;
    }

    /* その他の文字ならばエラーとする。*/
    else{
        fprintf(stderr, "不正な文字 '%c' が検出されました。\n", *lptr);
	exit(1);
    }
}

/*
 * 因子の構文解析木を生成する。
 */
node *factor(void)
{
    node *ptr;

    /* 数字tokenからなる因子ならば以下の処理を実行する。*/
    if(token.attribute==NUMBER){

        /* 当該因子を格納する節点を生成する。*/
        ptr = malloc(sizeof(node));
	ptr->attribute = NUMBER;
        ptr->value     = token.value;
        ptr->left      = NULL;
	ptr->right     = NULL;

	/* 次のtokenを読み、因子の構文解析木へのポインタを返す */
        gettoken();
	return ptr;
    }

    /* ( 式 ) の文法と一致した場合には以下の処理を実行する。*/
    else if(token.attribute=='('){

        /* 次のtokenを読み、式の構文解析木を生成する。 */
        gettoken(); 
	ptr = expression();

        /* ) で終らなければエラーとする。*/
        if(token.attribute != ')'){
            fprintf(stderr, ") が必要です。\n");
	    error = TRUE;
	    return NULL;
	}

	/* 次のtokenを読み、因子の構文解析木へのポインタを返す */
        gettoken();
        return ptr;
    }

    /* それ以外はエラーとする。 */
    else{
      fprintf(stderr, "数字 か ( が必要です。\n");
      error = TRUE;
      return NULL;
    }
}

/*
 * 項の構文解析木を生成する。
 */
node *term(void)
{
    node *OPptr;
    node *ptr;

    /* 最初の因子に対応する構文解析木を生成する。 */
    ptr = factor();

    /* * または / がある限り以下の処理を繰り返す。*/
    while((token.attribute=='*') || (token.attribute=='/')){

        /* 演算子を格納する節点を生成する。*/
        OPptr = malloc(sizeof(node));
        OPptr->attribute = token.attribute;
        OPptr->left      = ptr;
	OPptr->right     = NULL;

	/* 引き続く因子に対応する構文解析木を生成する。*/
	ptr = OPptr;
        gettoken();
	OPptr->right = factor();
    }

    /* 項の構文解析木へのポインタを返す */
    return ptr;
}

/*
 * 式の構文解析木を生成する。
 */
node *expression(void)
{
    node *minusPtr;
    node *OPptr;
    node *ptr;

    /* 単項マイナスがあれば、以下の処理を実行する。 */
    if(token.attribute=='-'){

        /* 最初の項に対応する構文解析木を生成する。 */
        gettoken();
	ptr = term();

	/* 単項マイナスの節点を挿入する。 */
        minusPtr = malloc(sizeof(node));
        minusPtr->attribute = '-';
        minusPtr->right     = NULL;
	minusPtr->left      = ptr;

	ptr = minusPtr;
    }

    /* そうでなければ最初の項に対応する構文解析木を生成する。 */
    else
        ptr = term();

    /* + または - がある限り以下の処理を繰り返す。*/
    while((token.attribute=='+') || (token.attribute=='-')){

        /* 二項演算子に対応する節点を生成する。 */
        OPptr = malloc(sizeof(node));
        OPptr->attribute = token.attribute;
        OPptr->left      = ptr;
	OPptr->right     = NULL;

	/* 引き続く項に対応する構文解析木を生成する。 */
	ptr = OPptr;
        gettoken();
	OPptr->right = term();
    }

    /* 式の構文解析木へのポインタを返す */
    return ptr;
}

/*
 * 構文解析木を木構造表示する。
 */
void PrintTree(node *ptr, int indent)
{
    int i;

    /* 構文解析木が空でないならば、以下の処理を実行する。 */
    if(ptr != NULL){

        /* 右の部分木の木構造を表示する。 */
        PrintTree(ptr->right, indent+6);

	/* 中央の演算子を表示する。 */
	for(i=0; i<indent-6; i++) putchar(' ');
        if(ptr->attribute==NUMBER)
	    printf("%6d\n", ptr->value);
        else
	    printf("%6c\n", ptr->attribute);

        /* 左の部分木の木構造を表示する。 */
        PrintTree(ptr->left , indent+6);
    }
}

/*
 * 構文解析木を消去する。
 */
void deleteTree(node *ptr)
{
    /* 空の構文解析木には何もしない */
    if(ptr == NULL) return;

    /* 左右の部分木を消去する。 */
    deleteTree(ptr->right);
    deleteTree(ptr->left);

    /* 中央の節点を消去する。 */
    free(ptr);
}