/*	
 *	clipshya.c
 *
 *	操車場アルゴリズム
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2016 Naoyuki Sawa
 *
 *	* Wed May 14 22:25:54 JST 2014 Naoyuki Sawa
 *	- 1stリリース。
 *	* Wed Jun 22 22:49:18 JST 2016 Naoyuki Sawa
 *	- USE_SHUNTINGYARD_SEHシンボルを定義すると、clipshya.c内のDIE()を全て、SEH_throw(ShuntingYardException)に置き換えるようにしました。
 *	  ユーザーが入力した式のテキストを計算するために、他のモジュールから当モジュールのShuntingYard_Eval()を利用する事が有り、
 *	  もし式が間違っていた時にすぐに当モジュール内ですぐにエラー停止してしまうと、使いづらいケースが生じたからです。
 *	  上記のようなケースでは、今後はShuntingYardExceptionを捕捉する事で、実行を継続出来ます。
 *	  それ以外のケースでは、ShuntingYardExceptionを捕捉しなければ、これまで通りすぐにエラー停止します。
 *	- ゼロ除算チェックを追加しました。
 *	  これまではCPUのゼロ除算エラーが発生してしまっていましたが、今後はプログラムで検出してDIE(),又は,例外を投入します。
 *	* Fri Jun 24 21:38:01 JST 2016 Naoyuki Sawa
 *	- ShuntingYard()のバグに気付いたので、コメントを追記しました。
 *	  詳細は、ShuntingYard()内の「//{{2016/06/24コメント追記:〜」を参照して下さい。
 *	  いずれのバグも、'間違った式が入力された時にエラーを検出出来ない事が有る'というものであり、正しい式に対する処理は問題有りません。
 *	- clipexpr.cモジュールでは、上記のバグは修正済みです。
 *	  今後はclipshya.cを廃止してclipexpr.cへ切り替えて行く予定なので、clipshya.cは修正せずにこのままにしておく事にしました。
 *	  しかし、もしまだclipshya.cを使う事が有れば、その時に修正して検証して下さい。
 *	* Mon Sep 05 21:24:05 JST 2016 Naoyuki Sawa
 *	- 64ビット版では、例外コードをアドレスでなく、一意なFourCC識別子で表すようにしました。
 *	  setjmp()/longjmp()のパラメータは(int)であり、(void*)や(intptr_t)を使えないからです。
 *	  尚、32ビット版も64ビット版と共通に変更しても良いのですが、万一既存のコードに影響が生じる事を防ぐために、32ビット版はこれまで通りとしました。
 */
#include "clip.h"

//{{2016/06/22追加:USE_SHUNTINGYARD_SEHシンボルを定義すると、clipshya.c内のDIE()を全て、SEH_throw(ShuntingYardException)に置き換えるようにしました。
#ifdef  USE_SHUNTINGYARD_SEH
//USE_SHUNTINGYARD_SEHシンボルが定義されたら、clipshya.c内のDIE()を全て、SEH_throw(ShuntingYardException)に置き換えます。
#undef  DIE
#ifndef PIECE
  #define DIE() SEH_throw(ShuntingYardException)
#else //PIECE
  //P/ECEでも上のように定義しても良いのですが、メモリ節約のため下のように定義する事にしました。結果は同じになります。
  //以下の定義はclipseh.hのSEH_throw()の定義に依存しています。もし今後SEH_throw()を変更する時は以下も変更して下さい。
  #define DIE() do { ShuntingYard_throw(__FILE__, __LINE__); } while(0)
  static void __attribute__((noreturn)) ShuntingYard_throw(const char* file, int line) {
    SEH_info.file = file;
    SEH_info.line = line;
    SEH_info.msg  = NULL;
    SEH_longjmp((int)ShuntingYardException); }
#endif//PIECE
//{{2016/09/05変更:64ビット版では、例外コードをアドレスでなく、一意なFourCC識別子で表すようにしました。
//const char ShuntingYardException[1/*dummy*/];
//↓2016/09/05変更:64ビット版では、例外コードをアドレスでなく、一意なFourCC識別子で表すようにしました。
#ifndef _WIN64
const char ShuntingYardException[1/*dummy*/];	//32ビット版
#endif//_WIN64
//}}2016/09/05変更:64ビット版では、例外コードをアドレスでなく、一意なFourCC識別子で表すようにしました。
#endif//USE_SHUNTINGYARD_SEH
//}}2016/06/22追加:USE_SHUNTINGYARD_SEHシンボルを定義すると、clipshya.c内のDIE()を全て、SEH_throw(ShuntingYardException)に置き換えるようにしました。

/****************************************************************************
 *	操車場アルゴリズム
 ****************************************************************************/
void ShuntingYard(const ST_ShuntingYard* pShuntingYard, const int* aInput, int* aOutput, void* pParam) {
	/* 参考資料:「http://ja.wikipedia.org/wiki/操車場アルゴリズム」 */
	int aStack[32/*調整可*/];
	int iStackTop = -1;
	int iToken;
	/* トークンを1つ読み込む。 */
	while((iToken = *aInput++)) {
		/* トークンの種類によって… */
		switch((*pShuntingYard->fnGetTokenType)(iToken, pParam)) {
		/* 数値 */
		case ShuntingYard_TokenType_Number:
			/* 数値を、出力キューに追加する。 */
			*aOutput++ = iToken;
			break;
		/* 関数,又は,左括弧 */
		case ShuntingYard_TokenType_Function:
		case ShuntingYard_TokenType_LeftParenthesis:
			/* 関数,又は,左括弧を、スタックにプッシュする。 */
			if(++iStackTop >= ARRAY_SIZE(aStack)) { DIE(); }
			aStack[iStackTop] = iToken;
			break;
		/* 関数の引数セパレータ(カンマなど) */
		case ShuntingYard_TokenType_FunctionArgumentSeparator:
			/* スタックのトップにあるトークンが左括弧となるまで、スタックから演算子(又は,関数)をポップして出力キューに追加する動作を繰り返す。	//{{2016/06/24コメント追記:「(又は,関数)」という部分は自分で判断してそうしていたのだが、間違いである。詳細は下記のコメントを参照せよ。}}
			 * 左括弧が出てこない場合、引数セパレータの位置がおかしいか、左右の括弧が不一致となっている(エラー)。 */
			for(;;) {
				if(iStackTop < 0) { DIE(); }
				if((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) == ShuntingYard_TokenType_LeftParenthesis) { break; }
				if(((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) != ShuntingYard_TokenType_Function) &&				//{{2016/06/24コメント追記:左記の実装では関数トークンを許容しているが、それは間違いである事に気付いた。例えば「function(1,2)」と書くべき所「function 1,2」と書いた場合、左記の実装ではエラーを検出出来ない。clipexpr.cモジュールでは修正した。今後はclipshya.cを廃止してclipexpr.cへ切り替えて行く予定なので、clipshya.cは修正せずにこのままにしておくが、もしまだclipshya.cを使う事が有れば修正せよ。(※TODO:)}}
				   ((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) != ShuntingYard_TokenType_Operator)) { DIE(); }
				*aOutput++ = aStack[iStackTop--];
			}
			break;
		/* 演算子 */
		case ShuntingYard_TokenType_Operator:
			/* スタックのトップに演算子トークンo2があり、o1が左結合性で,かつ,優先順位がo2と等しいか低い場合、あるいは、o1の優先順位がo2より低い場合、以下を繰り返す。
			 * - o2をスタックからポップし、出力キューに追加する。
			 * o1をスタックにプッシュする。 */
			while((iStackTop >= 0) &&								//スタックのトップに演算子トークンo2があり、
			     (((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) == ShuntingYard_TokenType_Operator) &&
			     (((*pShuntingYard->fnIsOpLeftAssoc)(iToken, pParam) &&				//o1が左結合性で,かつ,優先順位がo2と等しいか低い場合、
			     ((*pShuntingYard->fnCompareOpPrec)(iToken, aStack[iStackTop], pParam) <= 0)) ||
			     ((*pShuntingYard->fnCompareOpPrec)(iToken, aStack[iStackTop], pParam) < 0)))) {	//あるいは、o1の優先順位がo2より低い場合、
				*aOutput++ = aStack[iStackTop--];
			}
			if(++iStackTop >= ARRAY_SIZE(aStack)) { DIE(); }
			aStack[iStackTop] = iToken;
			break;
		/* 右括弧 */
		case ShuntingYard_TokenType_RightParenthesis:
			/* スタックのトップにあるトークンが左括弧になるまで、スタックからポップした演算子(又は,関数)を出力キューに追加する動作を繰り返す。	//{{2016/06/24コメント追記:「(又は,関数)」という部分は自分で判断してそうしていたのだが、間違いである。詳細は下記のコメントを参照せよ。}}
			 * 左括弧をスタックからポップするが、出力には追加せずに捨てる。
			 * スタックのトップにあるトークンが関数トークンなら、それをポップして出力キューに追加する。
			 * 左括弧がスタック上に見つからなかった場合、左右の括弧の不一致がある(エラー)。 */
			for(;;) {
				if(iStackTop < 0) { DIE(); }
				if((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) == ShuntingYard_TokenType_LeftParenthesis) { break; }
				if(((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) != ShuntingYard_TokenType_Function) &&				//{{2016/06/24コメント追記:左記の実装では関数トークンを許容しているが、それは間違いである事に気付いた。例えば「function(1,2)」と書くべき所「function 1,2)」と書いた場合、左記の実装ではエラーを検出出来ない。clipexpr.cモジュールでは修正した。今後はclipshya.cを廃止してclipexpr.cへ切り替えて行く予定なので、clipshya.cは修正せずにこのままにしておくが、もしまだclipshya.cを使う事が有れば修正せよ。(※TODO:)}}
				   ((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) != ShuntingYard_TokenType_Operator)) { DIE(); }
				*aOutput++ = aStack[iStackTop--];
			}
			iStackTop--;		//左括弧をスタックからポップするが、出力には追加せずに捨てる。
			if((iStackTop >= 0) &&	//スタックのトップにあるトークンが関数トークンなら、それをポップして出力キューに追加する。
			  ((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) == ShuntingYard_TokenType_Function)) {
				*aOutput++ = aStack[iStackTop--];
			}
			break;
		default:
			DIE();
		}
	}
	/* スタック上に演算子トークンがある間、以下を繰り返す。
	 * - スタックのトップにある演算子トークンが括弧なら、括弧の不一致がある(エラー)。
	 * - 演算子をスタックからポップして出力キューに追加する。 */
	while(iStackTop >= 0) {
		if(((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) == ShuntingYard_TokenType_LeftParenthesis ) ||
		   ((*pShuntingYard->fnGetTokenType)(aStack[iStackTop], pParam) == ShuntingYard_TokenType_RightParenthesis)) { DIE(); }
		*aOutput++ = aStack[iStackTop--];														//{{2016/06/24コメント追記:左記の実装では関数トークンを許容しているが、それは間違いである事に気付いた。例えば「function()」と書くべき所「function」と書いた場合、左記の実装ではエラーを検出出来ない。clipexpr.cモジュールでは修正した。今後はclipshya.cを廃止してclipexpr.cへ切り替えて行く予定なので、clipshya.cは修正せずにこのままにしておくが、もしまだclipshya.cを使う事が有れば修正せよ。(※TODO:)}}
	}
	*aOutput = 0;	//出力キューを終端する
}

/****************************************************************************
 *	サンプル
 ****************************************************************************/
/* - 操車場アルゴリズムを利用して、式テキストの計算を行うサンプルです。
 *   サンプルではありますが、これはこれで利用価値があると思うので、アプリケーションからも利用可能にしました。
 * - このサンプルでは、単純化のため、値をそのままトークン値としました。
 *   実際には、個々のトークン情報を保持するメモリを確保して、それを(int)にキャストして、トークン値とすべきです。
 */
/*---------------------------------------------------------------------------*/
/* このサンプルが対応している式の要素 */
enum {
	op_umi=INT_MIN,	//演算子:-(単項)
	op_pow,		//演算子:^
	op_add,		//演算子:+
	op_sub,		//演算子:-(二項)
	op_mul,		//演算子:*
	op_div,		//演算子:/
	fn_abs,		//関数:abs
	fn_mod,		//関数:mod
	fn_sep,		//関数の引数セパレータ(カンマなど):,
	lf_par,		//左括弧:(
	ri_par,		//右括弧:)
	nu_min,		//数値							//数値(0)⇒トークン(nu_min)にエンコードする
};
/*---------------------------------------------------------------------------*/
/* テキストを中置記法のトークン並びに変換する */
static void ShuntingYard_PreProcess(const char* pText, int* aInput) {
	int c, n, i = 0;
	while((c = *pText)) {
		if(isspace(c)) {
			pText++;
		} else if(isdigit(c)) {
			n = strtol(pText, (char**)&pText, 0);
			if(n <= nu_min) { DIE(); }
			aInput[i++] = n ? n : nu_min;				//数値(0)⇒トークン(nu_min)にエンコードする
		} else if(!strncmp(pText, "abs", 3)) {
			pText += 3;
			aInput[i++] = fn_abs;
			continue;
		} else if(!strncmp(pText, "mod", 3)) {
			pText += 3;
			aInput[i++] = fn_mod;
			continue;
		} else {
			switch(c) {
			case '^': pText++; aInput[i++] = op_pow; break;
			case '+': pText++; aInput[i++] = op_add; break;
			case '-': if(i && (aInput[i-1] >= ri_par)) {
				  pText++; aInput[i++] = op_sub; } else {
				  pText++; aInput[i++] = op_umi; } break;
			case '*': pText++; aInput[i++] = op_mul; break;
			case '/': pText++; aInput[i++] = op_div; break;
			case ',': pText++; aInput[i++] = fn_sep; break;
			case '(': pText++; aInput[i++] = lf_par; break;
			case ')': pText++; aInput[i++] = ri_par; break;
			default: DIE();
			}
		}
	}
	aInput[i] = 0;
}
/*---------------------------------------------------------------------------*/
/* 逆ポーランド記法のトークン並びを計算する */
static int ShuntingYard_PostProcess(const int* aOutput) {
	int aStack[32/*調整可*/];
	int iStackTop = -1;
	int iToken;
	while((iToken = *aOutput++)) {
		switch(iToken) {
		case op_umi:	//演算子:-(単項)
			if(iStackTop < 0) { DIE(); }
			aStack[iStackTop] = -aStack[iStackTop];
			break;
		case op_pow:	//演算子:^
			if(iStackTop < 1) { DIE(); }
			aStack[iStackTop - 1] = (int)pow(aStack[iStackTop - 1], aStack[iStackTop]);
			iStackTop--;
			break;
		case op_add:	//演算子:+
			if(iStackTop < 1) { DIE(); }
			aStack[iStackTop - 1] = aStack[iStackTop - 1] + aStack[iStackTop];
			iStackTop--;
			break;
		case op_sub:	//演算子:-(二項)
			if(iStackTop < 1) { DIE(); }
			aStack[iStackTop - 1] = aStack[iStackTop - 1] - aStack[iStackTop];
			iStackTop--;
			break;
		case op_mul:	//演算子:*
			if(iStackTop < 1) { DIE(); }
			aStack[iStackTop - 1] = aStack[iStackTop - 1] * aStack[iStackTop];
			iStackTop--;
			break;
		case op_div:	//演算子:/
			if(iStackTop < 1) { DIE(); }
//{{2016/06/22追加:ゼロ除算チェックを追加しました。これまではCPUのゼロ除算エラーが発生してしまっていましたが、今後はプログラムで検出してDIE(),又は,例外を投入します。
			if(!aStack[iStackTop]) { DIE(); }
//}}2016/06/22追加:ゼロ除算チェックを追加しました。これまではCPUのゼロ除算エラーが発生してしまっていましたが、今後はプログラムで検出してDIE(),又は,例外を投入します。
			aStack[iStackTop - 1] = aStack[iStackTop - 1] / aStack[iStackTop];
			iStackTop--;
			break;
		case fn_abs:	//関数:abs
			if(iStackTop < 0) { DIE(); }
			aStack[iStackTop] = abs(aStack[iStackTop]);
			break;
		case fn_mod:	//関数:mod
			if((iStackTop < 1) || (aStack[iStackTop] < nu_min) || (aStack[iStackTop - 1] < nu_min)) { DIE(); }
//{{2016/06/22追加:ゼロ除算チェックを追加しました。これまではCPUのゼロ除算エラーが発生してしまっていましたが、今後はプログラムで検出してDIE(),又は,例外を投入します。
			if(!aStack[iStackTop]) { DIE(); }
//}}2016/06/22追加:ゼロ除算チェックを追加しました。これまではCPUのゼロ除算エラーが発生してしまっていましたが、今後はプログラムで検出してDIE(),又は,例外を投入します。
			aStack[iStackTop - 1] = aStack[iStackTop - 1] % aStack[iStackTop];
			iStackTop--;
			break;
		case fn_sep:	//関数の引数セパレータ(カンマなど):,
		case lf_par:	//左括弧:(
		case ri_par:	//右括弧:)
			DIE();
		//case nu_min:	//数値
		default:
			if(++iStackTop >= ARRAY_SIZE(aStack)) { DIE(); }
			aStack[iStackTop] = (iToken == nu_min) ? 0 : iToken;	//トークン(nu_min)⇒数値(0)にデコードする
			break;
		}
	}
	if((iStackTop != 0) || (aStack[iStackTop] < nu_min)) { DIE(); }
	return aStack[iStackTop];
}
/*---------------------------------------------------------------------------*/
/* アプリケーション定義の関数:トークンの種類を返す */
static int ShuntingYard_GetTokenType(int iToken, void* pParam) {
	switch(iToken) {
	case op_umi:	//演算子:-(単項)
	case op_pow:	//演算子:^
	case op_add:	//演算子:+
	case op_sub:	//演算子:-(二項)
	case op_mul:	//演算子:*
	case op_div:	//演算子:/
		return ShuntingYard_TokenType_Operator;
	case fn_abs:	//関数:abs
	case fn_mod:	//関数:mod
		return ShuntingYard_TokenType_Function;
	case fn_sep:	//関数の引数セパレータ(カンマなど)
		return ShuntingYard_TokenType_FunctionArgumentSeparator;
	case lf_par:	//左括弧
		return ShuntingYard_TokenType_LeftParenthesis;
	case ri_par:	//右括弧
		return ShuntingYard_TokenType_RightParenthesis;
	//case nu_min:	//数値
	default:
		return ShuntingYard_TokenType_Number;
	}
}
/*---------------------------------------------------------------------------*/
/* アプリケーション定義の関数:演算子が左結合かを返す */
static int ShuntingYard_IsOpLeftAssoc(int iOpTok, void* pParam) {
	switch(iOpTok) {
	case op_umi:	//演算子:-(単項)
	case op_pow:	//演算子:^
		return 0;
	case op_add:	//演算子:+
	case op_sub:	//演算子:-(二項)
	case op_mul:	//演算子:*
	case op_div:	//演算子:/
		return 1;
	default: DIE();
	}
}
/*---------------------------------------------------------------------------*/
/* アプリケーション定義の関数:演算子の優先順位を較べる */
static int ShuntingYard_CompareOpPrec(int iOpTok1, int iOpTok2, void* pParam) {
	switch(iOpTok1) {
	case op_umi:	//演算子:-(単項)
		iOpTok1 = 2; break;
	case op_pow:	//演算子:^
		iOpTok1 = 3; break;
	case op_add:	//演算子:+
	case op_sub:	//演算子:-(二項)
		iOpTok1 = 0; break;
	case op_mul:	//演算子:*
	case op_div:	//演算子:/
		iOpTok1 = 1; break;
	default: DIE();
	}
	switch(iOpTok2) {
	case op_umi:	//演算子:-(単項)
		iOpTok2 = 2; break;
	case op_pow:	//演算子:^
		iOpTok2 = 3; break;
	case op_add:	//演算子:+
	case op_sub:	//演算子:-(二項)
		iOpTok2 = 0; break;
	case op_mul:	//演算子:*
	case op_div:	//演算子:/
		iOpTok2 = 1; break;
	default: DIE();
	}
	return iOpTok1 - iOpTok2;
}
/*---------------------------------------------------------------------------*/
/* 操車場アルゴリズムを利用して、式テキストの計算を行う */
int ShuntingYard_Eval(const char* pText) {
	static const ST_ShuntingYard stShuntingYard = {
		ShuntingYard_GetTokenType ,
		ShuntingYard_IsOpLeftAssoc,
		ShuntingYard_CompareOpPrec,
	};
	int aInput[64/*調整可*/], aOutput[64/*調整可*/];
	ShuntingYard_PreProcess(pText, aInput);				//テキスト⇒中置記法のトークン並び
	ShuntingYard(&stShuntingYard, aInput, aOutput, NULL);		//中置記法のトークン並び⇒逆ポーランド記法のトークン並び
	return ShuntingYard_PostProcess(aOutput);			//逆ポーランド記法のトークン並び⇒計算結果
}
#if 0
void TestSuite() { //使用例
	printf("%d\n", ShuntingYard_Eval("-10 + mod(-9,-abs(-10+5))^2")); //⇒6		※残念ながらP/ECEで実行すると、結果は6ではなく5になります。演算の途中で、pow()の演算誤差のために、5^2=24.999...⇒切り捨てて24になるからです。framdbl1.sの演算誤差の問題であり、当モジュール内では解決出来ません。全体を実数で扱う計算ならば多少の誤差は許容できるのですが、この例のように整数化前提の計算では影響が大きくなります。
}
#endif
