// ポーランド記法による実行
// LA : Lexical Analysis(語彙解析)
// SA : Syntax Analysis(構文解析：ここでは逆ポーランド記法を出力する）
#include "stdAfx.h"
#include <string.h>
#include <math.h>
#define NUMBER 0 // 数値
#define STRING 1 // 文字列
#define NAME   2 // 名前
#define DELM   3 // LAでは区切り記号、SAでは演算子
#define FUNC   4 // 関数呼び出し（LAでは名前として処理される）
typedef struct {    // LAでのToken
	int type;       // トークンタイプ
	char str[255];  // トークン文字列
}laToken;
typedef struct{     // SA用演算子スタック上での表現
	char op[6];     // 演算子の文字列
	int  priority;  // 演算子の優先順位
}operation;
typedef struct{     // 実行用スタックでの値表現
	int type;       // トークンタイプ
	char str[1024]; // 文字列(STRING, NAME, FUNCのとき有効)
	double val;     // 数値の時の値（NUMBERのとき有効）
}evalData;
typedef struct{     // 名前表の要素データ
	char name[255]; // 変数名
	evalData v;     // 変数の値
}variable;
char typeStr[][16]={"num","str","name","op","fun"}; // 型名を示す文字列
FILE *fp;laToken LA0DT[256],LAtoken[256],exToken[256]; int ptLa, ptToken;//LA用変数
char DT[4096];     // １文の文字列
// 演算子と優先順位
operation opTB[21]={	{"(" , 100}, {")" , 100}, {"," , 110}, {"=" , 120}, {"||", 200}, 
						{"&&", 210}, {"!=", 220}, {"==", 240}, {"!=", 240}, {">" , 240}, 
						{">=", 240}, {"<" , 240}, {"<=", 240}, {"+" , 260}, {"-" , 260}, 
						{"*" , 280}, {"/" , 280}, {"%" , 280}, {"+$", 300}, {"-$", 300}, 
						{"^" , 400}};
operation pStack[256]; int prtStack;	//　SA用スタック
laToken SAtoken[256];int prtPolish;		//  SA結果
evalData Estack[256]; int prtEval;		//  実行用スタック
evalData Arguments[25]; int numArg;		//  関数呼び出し用引数リスト（本来の引数の順序と逆）
variable NameTable[256]; int prtName;	//  名前表
int mode;								//  2項演算子のとき演算対象がくるモードのとき1
										//  演算子がくるモードのとき0。
										//  このモードで単項演算子か単項演算子かを判別する・
//---------逆ポーランド記法の実行--------------------------------------------------
evalData searchTable(char name[]){		 //  名前表の探索。ないとき追加される。
	strcpy(NameTable[prtName].name,name);
	NameTable[prtName].v.type=STRING;
	NameTable[prtName].v.str[0]=0; NameTable[prtName].v.val=0;
	int i=0;
	while(strcmp(NameTable[i].name, name)!=0) i++;
	if(i==prtName) prtName++;
	return NameTable[i].v;
}
int pushOpe(char DT[]){					// 関数引数の先頭を表す左括弧("(")をプッシュする
	if(prtEval>=255) return -1;
	Estack[prtEval].type=DELM;Estack[prtEval].val=0;
    strcpy(Estack[prtEval].str,DT);	prtEval++;
	return prtEval;
}
evalData evalNumber(laToken DT){		// SA結果表現からスタック上の値表現に変換
	evalData E;	E.type=DT.type;	E.str[0]=0; E.val=0;
	if(DT.type==NUMBER) sscanf(DT.str,"%lf",&E.val); else strcpy(E.str, DT.str);
	return E;
}
evalData evDT(int type, char str[], double val){// 評価用データ設定（コンストラクタ相当）
	evalData E; E.type=type; E.val=val;	strcpy(E.str,str);
	return E;
}
int pushEval(evalData DT){// 評価用スタックにプッシュ
	if(prtEval>=255) return -1;
	Estack[prtEval++]=DT; return prtEval;
}
evalData popEval(){ // 評価用スタックからポップ
	if(prtEval<=0) return evDT(-1,"",0); else return Estack[--prtEval];
}
evalData popEvalEval(){ // ポップして変数名であれば、その値を求める。
	evalData E=popEval();
	if(E.type==NAME) return searchTable(E.str);
	return E;
}
evalData minus(evalData E){	return evDT(NUMBER, "", -E.val);}	// 符号逆転
evalData add(evalData E2, evalData E1 )//加算。文字列のとき連結とみなす
{						
	char s2[1024], s1[1024];double v1=0, v2=0;
	if(E1.type==STRING) {
		strcpy(s1,E1.str); 
		if(E2.type==STRING) strcat(s1,E2.str);
		else{ sprintf(s2,"%lf",E2.val); strcat(s1,s2);}
		return evDT(STRING, s1, 0);
	}
	else if(E1.type==STRING) {
		sprintf(s1,"%lf",E1.val); strcat(s1,E2.str);
		return evDT(STRING, s1, 0);
	}
	return evDT(NUMBER, "", E1.val+E2.val);
}
// 減算、乗算、除算はすべて数値データとみなす（文字列は0とみなす）
evalData sub(evalData E2, evalData E1 ){return evDT(NUMBER, "", E1.val-E2.val);}// 減算
evalData mlt(evalData E2, evalData E1 ){return evDT(NUMBER, "", E1.val*E2.val);}// 乗算
evalData div(evalData E2, evalData E1 ){return evDT(NUMBER, "", E1.val/E2.val);}// 除算
evalData ast(evalData E2, evalData E1 ){//代入
	if(E1.type!=NAME) printf("\n 代入できません");
	else{
		strcpy(NameTable[prtName].name,E1.str);
		int i=0; while(strcmp(NameTable[i].name, E1.str)!=0) i++;
		NameTable[i].v.type=E2.type; NameTable[i].v.val=E2.val;
	    strcpy(NameTable[i].v.str, E2.str);
	    if(i==prtName) prtName++;
	}
	return E2;
}
void EvalOpe(char Ope[]){//　演算子実行
	int ptr;
	if(Ope[0]=='(') { ptr=pushOpe(Ope);	if(ptr<0) printf("\n stack overflow");return;}
	evalData E2=popEvalEval();
	if (Ope[0]=='+' && Ope[1]=='$') pushEval(E2);
	else if (Ope[0]=='-' && Ope[1]=='$') pushEval(E2);
	else if (Ope[0]=='+' && Ope[1]== 0 ) pushEval(add(E2,popEvalEval()));
	else if (Ope[0]=='-' && Ope[1]== 0 ) pushEval(sub(E2,popEvalEval()));
	else if (Ope[0]=='*' && Ope[1]== 0 ) pushEval(mlt(E2,popEvalEval()));
	else if (Ope[0]=='/' && Ope[1]== 0 ) pushEval(div(E2,popEvalEval()));
	else if (Ope[0]=='=' && Ope[1]== 0 ) pushEval(ast(E2,popEval()));
	else printf("\n 演算子がありません");
}
// 関数群
evalData absP(evalData E){return evDT(NUMBER, "", fabs(E.val));}
evalData sinP(evalData E){return evDT(NUMBER, "", sin(E.val));}
evalData toString(evalData E2, evalData E1){
	char str[1024];
	sprintf(str,(E1.str[0]==0)?"%lf":E1.str, E2.val);
	return evDT(STRING, str, 0);
}
void EvalFunc(char fname[]){// 関数実行
	numArg=0;
	while(prtEval>0 && Estack[prtEval-1].str[0]!='(') {Arguments[numArg++]=popEvalEval();}
	if(prtEval>0 )prtEval--;
	if(strcmp(fname,"toString")==0) pushEval(toString(Arguments[1],Arguments[0]));
	else if(strcmp(fname,"abs")==0) pushEval(absP(Arguments[0]));
	else if(strcmp(fname,"sin")==0) pushEval(sinP(Arguments[0]));
	else printf("\n 関数が見つかりません");
}
void EvalPolish(){// 実行メイン
	prtEval=0;
	for(int i=0;i<prtPolish;i++){
		if(SAtoken[i].type==DELM) EvalOpe(SAtoken[i].str);
		else if(SAtoken[i].type==FUNC) EvalFunc(SAtoken[i].str);
		else pushEval(evalNumber(SAtoken[i]));
	}
}
//--------以下SA------------------------------------------
int chkOper(laToken DT)
{	if(DT.type==DELM)
	for(int i=0;i<21;i++) if(strcmp(DT.str,opTB[i].op)==0) return i;
	return -1;
}
void operandProc(int type, char X[]){// 演算対象処理（変換結果に移す）
	strcpy(SAtoken[prtPolish].str, X); SAtoken[prtPolish].type=type;
	prtPolish++;
}
void operationProc(int priority, char X[]){// 演算子処理（優先順位の考慮）
	if(X[0]==')'){// 右カッコのとき左カッコまでを変換結果に移す
		while(prtStack>0 && pStack[prtStack-1].op[0]!='('){
		    operandProc(DELM, pStack[--prtStack].op);
		}
		if(prtStack>0 && pStack[prtStack-1].op[0]=='(') prtStack--;
		if(prtStack>0 && pStack[prtStack-1].priority==0){//関数表現として解釈
			 operandProc(FUNC, pStack[--prtStack].op);
		}
	}
	else if(X[0]==','){//　コンマの処理
		while(prtStack>0 && pStack[prtStack-1].op[0]!='('){
		    operandProc(DELM, pStack[--prtStack].op);
		}
	}
	else if(X[0]=='('){// 左カッコのときプッシュ
		strcpy(pStack[prtStack].op,X);
		pStack[prtStack++].priority=priority;
	}
	else{//優先順位が同じか高いものがあったら変換結果に演算子を移す
		while(prtStack>0 && pStack[prtStack-1].priority>=priority){
			operandProc(DELM, pStack[--prtStack].op);
		}
		strcpy(pStack[prtStack].op,X);//演算子のプッシュ
		pStack[prtStack++].priority=priority;
	}
}
void funCallObj(){//演算対象直後に左カッコがあったら関数呼び出しとみなす
	strcpy(pStack[prtStack].op,SAtoken[--prtPolish].str);
	pStack[prtStack++].priority=0;//優先順位 0 は関数呼び出しの関数名
    strcpy(pStack[prtStack].op,"(");//引数の最初
	pStack[prtStack++].priority=100;
	operandProc(DELM, "(");mode=1;//引数リストの先頭を示す左括弧
}
void SAexp(){//SAメイン処理
	mode=1;int i=0;int s;prtStack=0; prtPolish=0;
	while(i<ptToken){
		if(mode){ // 演算対象
			if(exToken[i].type!=DELM){//演算対象の後ろは演算子
				operandProc(exToken[i].type,exToken[i].str);
				mode=0;
			}     // 2項演算子のとき演算対象がくるはずなのに
			else {// 演算子がきたら単項演算子とみなす。
				s=chkOper(exToken[i]);
				if(s ==0 )operationProc(opTB[s].priority, exToken[i].str);
				else if(s ==13 || s==14){  // 単項演算子としての+と-
					exToken[i].str[1]='$'; // +$, -$として区別する
					exToken[i].str[2]=0;
					operationProc(opTB[s].priority, exToken[i].str);
				}
				else if(s ==1){// 右カッコがきたら次は演算子
					operationProc(opTB[s].priority, exToken[i].str);
					mode=0;
				}
				else printf("*** 演算子の例外 %s", exToken[i].str);
			}
		}
		else{// 右カッコ以外のとき演算子の後は演算対象、右カッコのとき演算子のまま
			if(exToken[i].type!=DELM) printf("*** 演算子でなければなりません %s", exToken[i].str);
			else if(exToken[i].str[0]=='(') funCallObj();
			else{
				s=chkOper(exToken[i]); operationProc(opTB[s].priority, exToken[i].str);
				if(s!=1)mode=1;
			}
		}
		i++;
	}
	prtStack--;
	while(prtStack>=0){//スタック上の結果を変換結果に移す
		operandProc(DELM, pStack[prtStack].op);prtStack--;
	}
}
int getStatement(char str[], int mx){//１文読み込み
	char ch=fgetc(fp);char ch2; int i=0;
	while(ch!=EOF){
		if(ch=='\n') break;			// 行エンドで１文終わり
		if(ch==':') break;			// １行に２文以上ある場合の区切り
		if(ch=='\"'){				// 2重引用符は文字列開始
			if(i>=(mx-1))break;		//行エンドで終わり（エラー）
		    str[i++]=ch; ch=fgetc(fp);
			while(ch!=EOF){			// EOFで終わり（エラー）
				if(ch=='\"'){		// 2個続けての2重引用符は
					ch2=fgetc(fp);	// 文字列の終わりではない
					if(ch2=='\"'){
						if(i>=(mx-2))break;
						str[i++]=ch; str[i++]=ch2; ch=fgetc(fp);
					}
					else{			//　1個の2重引用符のとき文字列終わり
						str[i++]=ch; ch=ch2;break;
					}
				}
				else if(i>=(mx-1))break;
				else{				//　文字列内の文字
		           str[i++]=ch; ch=fgetc(fp);
				}
			}
		}
		else if(ch=='\''){	// シングル引用符の後ろはコメントとして無視
			ch=fgetc(fp);
			while(ch!=EOF && ch!='\n') ch=fgetc(fp);
		}					// 空白、下線の組み合わせは継続行とする
		else if(ch=='_' && i>0 && str[i-1]==' '){
			ch=fgetc(fp); while(ch!=EOF && ch!='\n') ch=fgetc(fp);
			if(ch!=EOF)ch=fgetc(fp);
		}
		else if(ch!='\r'){ // [CR］コードを無視
		  if(i>=(mx-1))break;
		  str[i++]=ch; ch=fgetc(fp);
		}
		else ch=fgetc(fp);
	}
	str[i++]=0;// 文字列の最後
	return ch;
}
//-----------以下、単純LA-----------------------------
int LA0str(int i){//文字列スキャン
	int j=0;i++;
	LA0DT[ptLa].type=STRING;
	while(DT[i]!=0){
		if(DT[i]=='"' && DT[i+1]=='"' ) {LA0DT[ptLa].str[j++]='"'; i++;}
		else if(DT[i]=='"') {LA0DT[ptLa].str[j++]=0; ptLa++; return i;}
		else LA0DT[ptLa].str[j++]=DT[i];
		i++;
	}
	LA0DT[ptLa].str[j++]=0;ptLa++;return i-1;
}
int LA0num(int i){//数値スキャン
	int j=0;
	LA0DT[ptLa].type=NUMBER;
	while(DT[i]!=0 && DT[i]>='0' && DT[i]<='9' )
		LA0DT[ptLa].str[j++]=DT[i++]; 
	if(DT[i]=='.'){
		LA0DT[ptLa].str[j++]='.'; i++;
		while(DT[i]!=0 && DT[i]>='0' && DT[i]<='9' )
		   LA0DT[ptLa].str[j++]=DT[i++]; 
	}
	if(j==1 && LA0DT[ptLa].str[0]=='.' ){// ドット(.)のみのとき区切り記号
		LA0DT[ptLa].str[1]=0; LA0DT[ptLa].type=DELM;
	}
	else if(DT[i]=='E' || DT[i]=='e'){//指数表現
	      if(DT[i+1]=='+'||DT[i+1]=='-'){// 数値E±整数
			  LA0DT[ptLa].str[j++]='E'; LA0DT[ptLa].str[j++]=DT[i+1];
			  i+=2;
			  while(DT[i]!=0 && DT[i]>='0' && DT[i]<='9' )
		                LA0DT[ptLa].str[j++]=DT[i++]; 
		  }// 数値Eの直後に数字列がきたら 数値E+整数とみなす。
		  else if (DT[i+1]!=0 && DT[i+1]>='0' && DT[i+1]<='9'){
			  LA0DT[ptLa].str[j++]='E'; LA0DT[ptLa].str[j++]='+';
			  i++;
			  while(DT[i]!=0 && DT[i]>='0' && DT[i]<='9' )
				LA0DT[ptLa].str[j++]=DT[i++]; 
		  }
	} 
	LA0DT[ptLa].str[j++]=0;//文字列の最後
	ptLa++;return i-1;
}
int LA0name(int i){//名前スキャン（先頭以外は英数字または下線が続く）
	int j=0; LA0DT[ptLa].type=NAME;
	while((DT[i]>='0' && DT[i]<='9')||(DT[i]>='A' && DT[i]<='Z')||
		  (DT[i]>='a' && DT[i]<='z')|| DT[i]=='_') 
		LA0DT[ptLa].str[j++]=DT[i++]; 
	LA0DT[ptLa].str[j++]=0;ptLa++;return i-1;
}
int LA0delm(int i){//区切り記号（単純LAでは１文字のみとする）
	LA0DT[ptLa].type=DELM; LA0DT[ptLa].str[0]=DT[i]; LA0DT[ptLa].str[1]=0;
	ptLa++;	return i;
}
void LA0(){//単純LAメイン
	ptLa=0;int i=0;
	while(DT[i]!=0){
		if(DT[i]>' ' && DT[i]!='　'  && DT[i]!='\t' ){//空白を無視
			if(DT[i]=='"') i=LA0str(i);
			else if((DT[i]>='0' && DT[i]<='9')|| DT[i]=='.')i= LA0num(i);//数値
			else if((DT[i]>='A' && DT[i]<='Z')||(DT[i]>='a' && DT[i]<='z')||DT[i]=='_')
			  		i=LA0name(i);	//名前
			else	i=LA0delm(i);	//区切り記号
		}
		i++;
	}
	for(int i=0;i<5;i++){//判定を容易にするために無効トークンを詰める
		LA0DT[ptLa+i].type=9999; LA0DT[ptLa+i].str[0]=0;
	}
}
//----------以下LA(単純LA結果を組み合わせる）--------------------------
int chkDelm(laToken X, char ch){//区切り記号のチェック
	if(X.type==DELM && X.str[0]==ch && X.str[1]==0) return 1;
	else return 0;
}
void setDelm(char X[]){//区切り記号のセット
	LAtoken[ptToken].type=DELM;	strcpy(LAtoken[ptToken++].str, X);
}
void copyToken(laToken X){//トークンのコピー
	LAtoken[ptToken].type=X.type;strcpy(LAtoken[ptToken++].str, X.str);
}
void LA(){//LAのメイン
	ptToken=0;int i=0;
	while(i<ptLa){
		if     (chkDelm(LA0DT[i], '!') && chkDelm(LA0DT[i+1], '=')) {setDelm("!=");i++;}
		else if(chkDelm(LA0DT[i], '=') && chkDelm(LA0DT[i+1], '=')) {setDelm("==");i++;}
		else if(chkDelm(LA0DT[i], '>') && chkDelm(LA0DT[i+1], '=')) {setDelm(">=");i++;}
		else if(chkDelm(LA0DT[i], '<') && chkDelm(LA0DT[i+1], '=')) {setDelm("<=");i++;}
        else if(chkDelm(LA0DT[i], '<') && chkDelm(LA0DT[i+1], '=')) {setDelm("<=");i++;}
		else if(chkDelm(LA0DT[i], '|') && chkDelm(LA0DT[i+1], '|')) {setDelm("||");i++;}
		else if(chkDelm(LA0DT[i], '&') && chkDelm(LA0DT[i+1], '&')) {setDelm("&&");i++;}
		else copyToken(LA0DT[i]);
		i++;
	}
}
void dspNameTable(){//名前表の表示
	printf("\n\n Name Table");
	for(int i=0;i<prtName;i++){
		printf("\n %d %s  ",i,NameTable[i].name);
		printf("型名 = %s  値=",typeStr[NameTable[i].v.type]);
		if(NameTable[i].v.type==NUMBER)	printf("%lf",NameTable[i].v.val);
		else							printf("\"%s\"",NameTable[i].v.str);
	}
	printf("\n");
}
void dspLAresult(){//逆ポーランド記法へ変換前の表示
	printf("\n【元のデータ】\n");
	for(int i=0;i<ptToken;i++)
		printf(" %s(%s)", exToken[i].str,typeStr[exToken[i].type]);
}
void dspPolish(){//逆ポーランド記法の表示
	printf("\n【変換後】\n");
	for(int i=0;i<prtPolish;i++)
	printf(" %s(%s)", SAtoken[i].str,typeStr[SAtoken[i].type]);
}
void dspExec(){//実行結果表示（最終実行結果はスタック0に残されている）
	if(Estack[0].type==NUMBER) printf("\n *Eval NUMBER %lf ", Estack[0].val);
	else if (Estack[0].type==STRING) printf("\n *Eval STRING \"%s\" ", Estack[0].str);
	else printf("\n Eval Error");
}
//　実行メイン
int main(int argc, char* argv[]){
	int ch;prtName=0;
	if((fp=fopen("test.txt","rt"))!=NULL)
	{
		do{ // １文ごとの繰り返し
			ch=getStatement(DT,4096);
			LA0(); LA();
			for(int i=0;i<ptToken;i++)exToken[i]=LAtoken[i];
			if(ptToken>0){
				dspLAresult(); SAexp();//構文解析
				if(prtPolish>0){
					dspLAresult();	dspPolish();
					EvalPolish(); //逆ポーランド記法の実行
					dspExec(); dspNameTable(); getchar();
				}
			}
		}
		while(ch!=EOF);
		fclose(fp);
	}
}