/*

VenusScript 式解析ルーチン Version 1.00b
Copyleft 1994,95 Delmonta

このソースプログラムに関する著作権の行使を留保します。

コンパイル方法:
	・コンパイルオプションでマクロ「STANDALONE」を定義してください。
	・小数対応にするには、コンパイルオプションでマクロ「USE_FLOAT」を
	　定義してください。

*/

#include<stdio.h>
#include<stdlib.h>
#include<errno.h>		/* errno */
#include<ctype.h>
#include<string.h>
#include<signal.h>		/* signal() */
#include<float.h>		/* FPE_INTDIV0など */

#ifndef	STANDALONE
	#include"venus.h"
#else
	#ifdef	USE_FLOAT
		typedef	double	CONST_T;
	#else
		typedef	long	CONST_T;
	#endif

	#define	STRCMP			stricmp	/* これをstrcmpに変えれば   */
						/* 変数名の大文字・小文字を */
						/* 厳密に区別する           */
	#define	ISALPHA(c)		(isalpha(c) || (c)=='_')
	#define	ISALNUM(c)		(isalnum(c) || (c)=='_')
	#define	MEMBERSOF(array)	(sizeof(array)/sizeof((array)[0]))

	void	errexit(char *,...);
#endif
/*

演算子番号は、次のビット構成を持つ。

Bit15   : 1ならば右結合
Bit14   : 1ならば単項演算子
Bit11-4 : 優先順位
Bit3-0  : 演算子個別の識別番号

*/

#define	OP_ENDOFSTACK	0xffff	/* 演算子スタックの終了を示す特別な値 */
#define	OP_LPARE	0xfffe	/* 左括弧      ( */
#define	OP_RPARE	0xfffd	/* 右括弧      ) */

#define	OP_LNOT		0xc0f0	/* 論理否定    ! */
#define	OP_NOT		0xc0f1	/* ビット反転  ~ */

#define	OP_POW		0x80e0	/* 累乗       ** */

#define	OP_SMINUS	0xc0d0	/* 負の符号    - */
#define	OP_SPLUS	0xc0d1	/* 正の符号    + */

#define	OP_MULT		0x00c0	/* 乗算        * */
#define	OP_DIV		0x00c1	/* 除算        / */
#define	OP_MOD		0x00c2	/* 剰余        % */

#define	OP_LSHIFT	0x00b0	/* 左シフト   << */
#define	OP_RSHIFT	0x00b1	/* 右シフト   >> */

#define	OP_PLUS		0x00a0	/* 加算        + */
#define	OP_MINUS	0x00a1	/* 減算        - */

#define	OP_AND		0x0090	/* ビットAND   & */
#define	OP_XOR		0x0091	/* ビットXOR   ^ */
#define	OP_OR		0x0092	/* ビットOR    | */

#define	OP_LESS		0x0080	/* 比較       <  */
#define	OP_ELESS	0x0081	/*            <= */
#define	OP_GREAT	0x0082	/*            >  */
#define	OP_EGREAT	0x0083	/*            >= */
#define	OP_EQUAL	0x0084	/*            == */
#define	OP_NEQUAL	0x0085	/*            != */

#define	OP_LET		0x8070	/* 代入        = */

#define	OP_LAND		0x0060	/* 論理AND    && */
#define	OP_LOR		0x0061	/* 論理OR     || */

#define	OPLEVEL(op)	((op) & 0x0ff0)
#define	ISRIGHT(op)	((op) & 0x8000)
#define	ISSINGLE(op)	((op) & 0x4000)
/*-----------------------------------型--------------------------------------*/
typedef	int	OPERATOR_T;	/* 演算子   */
typedef	int	VARNO_T;	/* 変数番号 */
typedef	struct
{
	enum {CONSTANT,VARIABLE,OPERATOR,ENDOFSTRING} type;
	union
	{	CONST_T		constant;	/* 定数   */
		int		varno;		/* 変数   */
		OPERATOR_T	op;		/* 演算子 */
	} data;
} TOKEN_T;

static	TOKEN_T	Token;

static	struct	VAR_T
{
	CONST_T	value;
	char	*name;
} Variable[256];

static	struct	VSTACK
{
	union	{CONST_T constant; VARNO_T varno;}	value;
	enum	{VSTK_VAR,VSTK_CONST}			type;
} Vstack[256];

static	OPERATOR_T	Ostack[256];

static	int	Vstackp;
static	int	Ostackp;

static	char	*Expr;
/*-----------------------------初期化とエラー処理----------------------------*/
static	void	initexpr(char *s)
{
	Token.type = ENDOFSTRING;
	Vstackp = Ostackp = 0;

	Expr = s;
}

void	fperr(int a,int b)
{
	switch	(b)
	{
	case FPE_INTDIV0:
	case FPE_ZERODIVIDE:
		errexit("0で割りました");
	case FPE_OVERFLOW:
		errexit("オーバーフローしました");
	case FPE_UNDERFLOW:
		errexit("アンダーフローしました");
	case FPE_INVALID:
		errexit("不正な演算を実行しました");
	}
	signal(SIGFPE,fperr);		/* デノーマル数などは問題にしない */
}
/*---------------------------スタックフレームの管理--------------------------*/
static	OPERATOR_T	popop(void)
{
	if	(Ostackp==0)
		return OP_ENDOFSTACK;
	else
		return Ostack[--Ostackp];
}

static	void	pushop(OPERATOR_T op)
{
	if	(op==OP_ENDOFSTACK)
		return;
	else if	(Ostackp==MEMBERSOF(Ostack))
		errexit("演算子スタックオーバーフロー.");
	else
		Ostack[Ostackp++] = op;
}

static	char	Vstack_overflow[] = "オペランドスタックオーバーフロー.";

static	void	pushconst(CONST_T val)
{
	if	(Vstackp==MEMBERSOF(Vstack))
		errexit(Vstack_overflow);
	else
	{
		Vstack[Vstackp].type = VSTK_CONST;
		Vstack[Vstackp++].value.constant = val;
	}
}

static	void	pushvar(VARNO_T varno)
{
	if	(Vstackp==MEMBERSOF(Vstack))
		errexit(Vstack_overflow);
	else
	{
		Vstack[Vstackp].type = VSTK_VAR;
		Vstack[Vstackp++].value.varno = varno;
	}
}

static	char	Vstack_underflow[] = "オペランドが足りません.";

static	CONST_T	popconst(void)
{
	if	(Vstackp==0)
		errexit(Vstack_underflow);
	else if	(Vstack[--Vstackp].type==VSTK_CONST)
		return Vstack[Vstackp].value.constant;
	else
		return Variable[Vstack[Vstackp].value.varno].value;
}

static	VARNO_T	popvar(void)
{
	if	(Vstackp==0)
		errexit(Vstack_underflow);
	else if	(Vstack[--Vstackp].type==VSTK_CONST)
		errexit("変数が要求されるところに右辺式があります.");
	else
		return Vstack[Vstackp].value.varno;
}
/*-----------------------------------計算------------------------------------*/
#ifdef	USE_FLOAT
	#include<math.h>
	static	CONST_T	POW(CONST_T x,CONST_T y)
	{
		if	(x==0)		/* y<=0でも0**y==1 */
			return 1;
		else if	(x<0 && y!=ceil(y))
			errexit("負の数に対する指数が整数になっていません");
		else
			return pow(x,y);
	}
#else
	static	CONST_T	POW(CONST_T x,CONST_T y)
	{
		if	(y==0)		/* y<=0でも0**y==1 */
			return 1;
		else if	(y<0)
			return 0;	/* 切り捨てられて結果は0 */
		else
		{
			CONST_T	z = x;

			while	(--y)
				z *= x;

			return z;
		}
	}
#endif
/*-------------------------------演算子の処理--------------------------------*/
static	void	getoperator(void)
{
	int	flag = Token.type==ENDOFSTRING ||
			(Token.type==OPERATOR && Token.data.op!=OP_RPARE);
			/* 直前のトークンは2項演算子の前に来ないものか */

	switch	(*Expr)
	{
	case '(':	Token.data.op = OP_LPARE;	break;
	case ')':	Token.data.op = OP_RPARE;	break;
	case '!':
		if	(*(Expr+1)=='=')
			Expr++,Token.data.op = OP_NEQUAL;
		else
			Token.data.op = OP_LNOT;
		break;
	case '~':	Token.data.op = OP_NOT;	break;
	case '*':
		if	(*(Expr+1)=='*')
			Expr++,Token.data.op = OP_POW;
		else
			Token.data.op = OP_MULT;
		break;
	case '+':
		if	(flag)
			Token.data.op = OP_SPLUS;
		else
			Token.data.op = OP_PLUS;
		break;
	case '-':
		if	(flag)
			Token.data.op = OP_SMINUS;
		else
			Token.data.op = OP_MINUS;
		break;
	case '/':	Token.data.op = OP_DIV;	break;
	case '%':	Token.data.op = OP_MOD;	break;
	case '<':
		if	(*(Expr+1)=='<')
			Expr++,Token.data.op = OP_LSHIFT;
		else if	(*(Expr+1)=='=')
			Expr++,Token.data.op = OP_ELESS;
		else
			Token.data.op = OP_LESS;
		break;
	case '>':
		if	(*(Expr+1)=='>')
			Expr++,Token.data.op = OP_RSHIFT;
		else if	(*(Expr+1)=='=')
			Expr++,Token.data.op = OP_EGREAT;
		else
			Token.data.op = OP_GREAT;
		break;
	case '&':
		if	(*(Expr+1)=='&')
			Expr++,Token.data.op = OP_LAND;
		else
			Token.data.op = OP_AND;
		break;
	case '|':
		if	(*(Expr+1)=='|')
			Expr++,Token.data.op = OP_LOR;
		else
			Token.data.op = OP_OR;
		break;
	case '^':	Token.data.op = OP_XOR;
	case '=':
		if	(*(Expr+1)=='=')
			Expr++,Token.data.op = OP_EQUAL;
		else
			Token.data.op = OP_LET;
		break;
	default:
		errexit("不正な演算子です:%c",*Expr);
	};

	if	(flag && !ISSINGLE(Token.data.op))
		errexit("2つの演算子が連続しています");

	Expr++;
	Token.type = OPERATOR;
}

static	void	evalop(OPERATOR_T op)
{
	CONST_T	a;

	switch	(op)
	{
	case OP_LPARE:
		errexit("'('に対応する')'がありません");

	case OP_LNOT:	a = !popconst();			break;
	case OP_NOT:	a = ~(long)popconst();			break;
	case OP_POW:	a = popconst();	a = POW(popconst(),a);	break;
	case OP_SPLUS:	a = popconst();				break;
	case OP_SMINUS:	a = -popconst();			break;
	case OP_MULT:	a = popconst() * popconst();		break;
	case OP_DIV:	a = popconst();	a = popconst()/a;	break;
	case OP_MOD:
		a = popconst();
		#ifndef	USE_FLOAT
			a = popconst() % a;
		#else
			a = fmod(popconst(),a);
		#endif
		break;
	case OP_PLUS:	a = popconst() + popconst();		break;
	case OP_MINUS:	a = popconst();	a = popconst() - a;	break;
	case OP_LSHIFT:
		a = popconst();
		#ifndef	USE_FLOAT
			a = popconst() << a;
		#else
			a = ldexp(popconst(),a);
		#endif
		break;
	case OP_RSHIFT:
		a = popconst();
		#ifndef	USE_FLOAT
			a = popconst() >> a;
		#else
			a = ldexp(popconst(),-a);
		#endif
		break;
			/* OP_LANDとOP_LORで一度aに値を設定しているのは */
			/* Cの&&あるいは||では第1項だけで値が確定すれば */
			/* 第2項は評価しないため                        */
	case OP_AND:	a =(long)popconst() & (long)popconst();	break;
	case OP_XOR:	a =(long)popconst() ^ (long)popconst();	break;
	case OP_OR:	a =(long)popconst() | (long)popconst();	break;
	case OP_LAND:	a = popconst(); a = popconst() && a;	break;
	case OP_LOR:	a = popconst(); a = popconst() || a;	break;
	case OP_LESS:	a = popconst();	a = popconst() <  a;	break;
	case OP_ELESS:	a = popconst();	a = popconst() <= a;	break;
	case OP_GREAT:	a = popconst();	a = popconst() >  a;	break;
	case OP_EGREAT:	a = popconst();	a = popconst() >= a;	break;
	case OP_EQUAL:	a = popconst() == popconst();		break;
	case OP_NEQUAL:	a = popconst() != popconst();		break;
	case OP_LET:
		{
			VARNO_T	b;

			a = popconst();
			b = popvar();
			Variable[b].value = a;
		}
		break;
	default:
		errexit("不正な演算子です:演算子ID 0x%04X",op);
	}
	pushconst(a);
}
/*----------------------------トークンの切り出し-----------------------------*/
static	char	Couple_values[] = "2つの定数/変数が連続して表記されています";

static	void	getvariable(void)
{
static	VARNO_T	varnum = 0;	/* 変数の総数 */
	char	*p = Expr;
	char	c;
	VARNO_T	i;

	if	(Token.type==CONSTANT || Token.type==VARIABLE)
		errexit(Couple_values);

	while	(ISALNUM(*p))
		p++;

	c  = *p;
	*p = '\0';

	for	(i=0 ; i<varnum ; i++)
	{
		if	(STRCMP(Expr,Variable[i].name)==0)
			goto end;
	}

	varnum++;

	if	(i==MEMBERSOF(Variable))
		errexit("変数は最大で%d個までです",i);

	if	((Variable[i].name=strdup(Expr))==NULL)
		errexit("メモリ不足です");

	Variable[i].value = 0;
end:
	Token.type = VARIABLE;
	Token.data.varno = i;

	Expr = p;
	*p = c;
}

static	int	expr_gettoken(void)
{
	while	(isspace(*Expr))
		Expr++;

	if	(*Expr=='\0')	/* 文字列の終わり */
		return 0;
				/* 定数か? */
	if	(isdigit(*Expr) || *Expr=='.')
	{		/* ピリオドとの比較は整数に限定する場合は意味がない */
		CONST_T	val;

		if	(Token.type==CONSTANT || Token.type==VARIABLE)
			errexit(Couple_values);

		errno = 0;
		if	(*Expr=='0' && (Expr[1]=='x' || Expr[1]=='X'))
			val = (long)strtoul(Expr+2,&Expr,16);
		else
		{
			#ifdef	USE_FLOAT
				val = strtod(Expr,&Expr);
			#else
				val = strtoul(Expr,&Expr,10);
			#endif
		}

		if	(errno==ERANGE && val!=0)
			errexit("定数の値が大きすぎます.");

		Token.data.constant = val;
		Token.type = CONSTANT;
	}
	else if	(ISALPHA(*Expr))
		getvariable();
	else
		getoperator();

	return 1;
}
/*------------------------------メインルーチン-------------------------------*/
extern	CONST_T	evalexpr(char *s)
{
	OPERATOR_T	op;
	int		lev1,lev2;

	initexpr(s);
	while	(expr_gettoken())
	{
		switch	(Token.type)
		{
		case CONSTANT:
			pushconst(Token.data.constant);
			break;
		case VARIABLE:
			pushvar(Token.data.varno);
			break;
		case OPERATOR:
			if	(Token.data.op==OP_LPARE)
			{
				pushop(OP_LPARE);
				break;
			}
			if	(Token.data.op==OP_RPARE)
			{
				while	((op=popop())!=OP_LPARE)
				{
					if	(op==OP_ENDOFSTACK)
						errexit("')'に対応する'('がありません.");
					evalop(op);
				}
				break;
			}

			lev2 = OPLEVEL(Token.data.op);
			do
			{
				lev1 = OPLEVEL(op = popop());
				if	(op==OP_LPARE || op==OP_ENDOFSTACK ||
					 ISSINGLE(Token.data.op) || lev1<lev2
					 || (lev1==lev2&&ISRIGHT(op)) )
				{
					pushop(op);
					pushop(Token.data.op);
					break;
				}

				evalop(op);
			} while(1);
		}
	}
	while	((op=popop())!=OP_ENDOFSTACK)
		evalop(op);

	if	(Vstackp!=1)
		printf("Vstackp==%d\n",Vstackp);

	return popconst();
}

/*---------------スタンドアローンの計算ツールとして使用する場合--------------*/
#ifdef	STANDALONE
	#include<setjmp.h>
	#include<stdarg.h>

	jmp_buf	Jmp_buf;

	void	errexit(char *s,...)
	{
		va_list	ap;

		va_start(ap,s);
		vprintf(s,ap);
		va_end(ap);

		putchar('\a');
		putchar('\n');
		longjmp(Jmp_buf,1);
	}

	int	main(int argc,char **argv)
	{
		char	buf[256];

		#ifdef	USE_FLOAT
			#define	VER	"(小数対応バージョン)"
		#else
			#define	VER	"(整数限定バージョン)"
		#endif

		printf(	"式計算ユーティリティ" VER " Version 1.00b\n"
			"Copyleft 1994,95 Delmonta\n");

		#undef	VER

		setjmp(Jmp_buf);
		signal(SIGFPE,fperr);

		while	(printf(">"),fgets(buf,sizeof(buf),stdin)&&*buf!='\n')
		{
			#ifdef	USE_FLOAT
				printf("%.*g\n",DBL_DIG+1,evalexpr(buf));
					/* i80x87のdoubleの精度は10進で15.95 */
					/* 桁だがDBL_DIG＝15と定義されている */
			#else
				printf("%ld\n",evalexpr(buf));
			#endif
		}
	}
#endif