/*
	64 bit integer arithmetic expression interpreter by Igor van den Hoven.

	No restrictions on use. 11/24/2008
*/

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

/*
         Operator        Priority     Function
         ------------------------------------------------
         !               0            logical not
         ~               0            bitwise not
         *               1            integer multiply
         /               1            integer divide
         %               1            integer modulo
         d               1            integer random dice roll
         +               2            integer addition
         -               2            integer subtraction
         <<              3            bitwise shift
         >>              3            bitwise shift
         >               4            logical greater than
         >=              4            logical greater than or equal
         <               4            logical less than
         <=              4            logical less than or equal
         ==              5            logical equal (can use wildcards)
         !=              5            logical not equal (can use wildcards)
          &              6            bitwise and
          ^              7            bitwise xor
          |              8            bitwise or
         &&              9            logical and
         ^^             10            logical xor
         ||             11            logical or

         Parentheses work as expected, strings must be enclosed in quotes and
         are evaluated with strcmp.

         Example: mathexp("(1+2) * 3 << 4"); would return "144".
*/

typedef struct math_data MATH_DATA;

struct math_data
{
	MATH_DATA   * next;
	MATH_DATA   * prev;
	int           lvl;
	int           prt;
	char        * str;
};

#define LINK(link, first, last, next, prev) \
{ \
	if (!(first)) \
	{ \
		(first) = (link); \
	} \
	else \
	{ \
		(last)->next = (link); \
	} \
	(link)->next = NULL; \
	(link)->prev = (last); \
	(last) = (link); \
}


#define UNLINK(link, first, last, next, prev) \
{ \
	if (!(link)->prev) \
	{ \
		(first) = (link)->next; \
	} \
	else \
	{ \
		(link)->prev->next = (link)->next; \
	} \
	if (!(link)->next) \
	{ \
		(last) = (link)->prev; \
	} \
	else \
	{ \
		(link)->next->prev = (link)->prev; \
	} \
	(link)->next = NULL; \
	(link)->prev = NULL; \
}

#define FALSE 0
#define TRUE  1

long long mathexp(char *str);
long long mathexp_tokenize(char *str);
void mathexp_level(MATH_DATA *node);
void mathexp_compute(MATH_DATA *node);
long long mathtoi(const char *str);
long long mathcmp(const char *left, const char *right);
long long mathdice(const char *left, const char *right);


#define EXP_VARIABLE         0
#define EXP_STRING           1
#define EXP_OPERATOR         2

#define EXP_PR_DICE          0
#define EXP_PR_INTMUL        1
#define EXP_PR_INTADD        2
#define EXP_PR_BITSHIFT      3
#define EXP_PR_LOGLTGT       4
#define EXP_PR_LOGCOMP       5
#define EXP_PR_BITAND        6
#define EXP_PR_BITXOR        7
#define EXP_PR_BITOR         8
#define EXP_PR_LOGAND        9
#define EXP_PR_LOGXOR       10
#define EXP_PR_LOGOR        11
#define EXP_PR_VAR          12
#define EXP_PR_LVL          13

MATH_DATA *mathnode_f;
MATH_DATA *mathnode_l;

MATH_DATA *mathnode_s;
MATH_DATA *mathnode_e;
MATH_DATA *mathnode_n;

int main(int argc, char **argv)
{
	srand48(time(NULL));

	if (argv[1])
	{
		printf("mathexp: %s = %lld\n", argv[1], mathexp(argv[1]));
	}
	else
	{
		printf("Syntax: %s 'expression'\n", argv[0]);
	}
	return 0;
}

long long mathexp(char *str)
{
	MATH_DATA *node;

	if (mathexp_tokenize(str) == FALSE)
	{
		if (mathnode_f == NULL)
		{
			/* invalid input error */
		}
		return 0;
	}

	node = mathnode_f;

	while (node->prev || node->next)
	{
		if (node->next == NULL || node->next->lvl < node->lvl)
		{
			mathexp_level(node);

			node = mathnode_f;
		}
		else
		{
			node = node->next;
		}
	}
	return mathtoi(node->str);
}


void add_mathnode(int lvl, int prt, char *buf)
{
	MATH_DATA *node;

	node = calloc(1, sizeof(MATH_DATA));

	node->lvl = lvl;
	node->prt = prt;
	node->str = strdup(buf);

	LINK(node, mathnode_f, mathnode_l, next, prev);

	return;
}

void del_mathnode(MATH_DATA *node)
{
	free(node->str);

	UNLINK(node, mathnode_f, mathnode_l, next, prev);

	free(node);

	return;
}

#define MATH_NODE(buffercheck, priority, newstatus)  \
{                                                    \
	if (buffercheck && pta == buf)               \
	{                                            \
		return FALSE;                        \
	}                                            \
	*pta = 0;                                    \
	add_mathnode(level, priority, buf);          \
	status = newstatus;                          \
	pta = buf;                                   \
}


long long mathexp_tokenize(char *str)
{
	char buf[2000], *pti, *pta;
	int level, status;

	level  = 0;
	status = EXP_VARIABLE;

	pta = (char *) buf;
	pti = (char *) str;

	while (mathnode_f)
	{
		del_mathnode(mathnode_f);
	}

	mathnode_f = mathnode_l = NULL;

	while (*pti)
	{
		switch (status)
		{
			case EXP_VARIABLE:
				switch (*pti)
				{
					case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
						*pta++ = *pti++;
						break;

					case '!':
					case '~':
					case '+':
					case '-':
						if (pta != buf)
						{
							MATH_NODE(FALSE, EXP_PR_VAR, EXP_OPERATOR);
						}
						else
						{
							*pta++ = *pti++;
						}
						break;

					case '"':
						if (pta != buf)
						{
							/* string character found inside an integer */

							return FALSE;
						}
						*pta++ = *pti++;
						status = EXP_STRING;
						break;

					case '(':
						if (pta != buf)
						{
							/* parenthesis found inside an integer */

							return FALSE;
						}
						*pta++ = *pti++;
						MATH_NODE(TRUE, EXP_PR_LVL, EXP_VARIABLE);
						level++;
						break;

					case ' ':
						pti++;
						break;

					default:
						MATH_NODE(TRUE, EXP_PR_VAR, EXP_OPERATOR);
						break;
				}
				break;

			case EXP_STRING:
				switch (*pti)
				{
					case '"':
						*pta++ = *pti++;
						MATH_NODE(FALSE, EXP_PR_VAR, EXP_OPERATOR);
						break;

					default:
						*pta++ = *pti++;
						break;
				}
				break;

			case EXP_OPERATOR:
				switch (*pti)
				{
					case ' ':
						pti++;
						break;

					case ')':
						*pta++ = *pti++;
						level--;
						MATH_NODE(TRUE, EXP_PR_LVL, EXP_OPERATOR);
						break;

					case 'd':
						*pta++ = *pti++;
						MATH_NODE(FALSE, EXP_PR_DICE, EXP_VARIABLE);
						break;

					case '*':
					case '/':
					case '%':
						*pta++ = *pti++;
						MATH_NODE(FALSE, EXP_PR_INTMUL, EXP_VARIABLE);
						break;

					case '+':
					case '-':
						*pta++ = *pti++;
						MATH_NODE(FALSE, EXP_PR_INTADD, EXP_VARIABLE);
						break;

					case '<':
						*pta++ = *pti++;

						switch (*pti)
						{
							case '<':
								*pta++ = *pti++;
								MATH_NODE(FALSE, EXP_PR_BITSHIFT, EXP_VARIABLE);
								break;

							case '=':
								*pta++ = *pti++;
								MATH_NODE(FALSE, EXP_PR_LOGLTGT, EXP_VARIABLE);
								break;

							default:
								MATH_NODE(FALSE, EXP_PR_LOGLTGT, EXP_VARIABLE);
								break;
						}
						break;

					case '>':
						*pta++ = *pti++;

						switch (*pti)
						{
							case '>':
								*pta++ = *pti++;
								MATH_NODE(FALSE, EXP_PR_BITSHIFT, EXP_VARIABLE);
								break;

							case '=':
								*pta++ = *pti++;
								MATH_NODE(FALSE, EXP_PR_LOGLTGT, EXP_VARIABLE);
								break;

							default:
								MATH_NODE(FALSE, EXP_PR_LOGLTGT, EXP_VARIABLE);
								break;
						}
						break;

					case '&':
						*pta++ = *pti++;

						switch (*pti)
						{
							case '&':
								*pta++ = *pti++;
								MATH_NODE(FALSE, EXP_PR_LOGAND, EXP_VARIABLE);
								break;

							default:
								MATH_NODE(FALSE, EXP_PR_BITAND, EXP_VARIABLE);
								break;
						}
						break;

					case '^':
						*pta++ = *pti++;

						switch (*pti)
						{
							case '^':
								*pta++ = *pti++;
								MATH_NODE(FALSE, EXP_PR_LOGXOR, EXP_VARIABLE);
								break;

							default:
								MATH_NODE(FALSE, EXP_PR_BITXOR, EXP_VARIABLE);
								break;
						}
						break;

					case '|':
						*pta++ = *pti++;

						switch (*pti)
						{
							case '|':
								*pta++ = *pti++;
								MATH_NODE(FALSE, 7, EXP_VARIABLE);
								break;

							default:
								*pta++ = *pti++;
								MATH_NODE(FALSE, 5, EXP_VARIABLE);
								break;
						}
						break;

					case '=':
					case '!':
						*pta++ = *pti++;
						switch (*pti)
						{
							case '=':
								*pta++ = *pti++;
								MATH_NODE(FALSE, EXP_PR_LOGCOMP, EXP_VARIABLE);
								break;

							default:
								/* unknown operator */

								return FALSE;
						}
						break;

					default:
						/* unknown operator */

						return FALSE;
				}
				break;
		}
	}

	if (level != 0)
	{
		/* unmatched parenthesis */

		return FALSE;
	}

	if (status != EXP_OPERATOR)
	{
		MATH_NODE(TRUE, EXP_PR_VAR, EXP_OPERATOR);
	}
	return TRUE;
}

void mathexp_level(MATH_DATA *node)
{
	int priority;

	mathnode_e = node;

	while (node->prev)
	{
		if (node->prev->lvl < node->lvl)
		{
			break;
		}
		node = node->prev;
	}

	mathnode_s = node;

	for (priority = 0 ; priority < EXP_PR_VAR ; priority++)
	{
		for (node = mathnode_s ; node ; node = node->next)
		{
			if (node->prt == priority)
			{
				mathexp_compute(node);
			}
			if (node == mathnode_e)
			{
				break;
			}
		}
	}

	node = mathnode_s;

	while (node->prev && node->next)
	{
		if (node->prev->prt == EXP_PR_LVL && node->next->prt == EXP_PR_LVL)
		{
			node->lvl = node->next->lvl;

			del_mathnode(node->next);
			del_mathnode(node->prev);
		}
		else
		{
			break;
		}
	}
	return;
}

void mathexp_compute(MATH_DATA *node)
{
	char temp[2000];
	long long value;

	switch (node->str[0])
	{
		case 'd':
			if (mathtoi(node->next->str) <= 0)
			{
				/* invalid dice */
				value = 0;
			}
			else
			{
				value = mathdice(node->prev->str, node->next->str);
			}
			break;
		case '*':
			value = mathtoi(node->prev->str) * mathtoi(node->next->str);
			break;
		case '/':
			if (mathtoi(node->next->str) == 0)
			{
				/* division zero */
				value = mathtoi(node->prev->str) / 1;
			}
			else
			{
				value = mathtoi(node->prev->str) / mathtoi(node->next->str);
			}
			break;
		case '%':
			if (mathtoi(node->next->str) == 0)
			{
				/* division zero */
				value = mathtoi(node->prev->str) / 1;
			}
			else
			{
				value = mathtoi(node->prev->str) % mathtoi(node->next->str);
			}
			break;
		case '+':
			value = mathtoi(node->prev->str) + mathtoi(node->next->str);
			break;
		case '-':
			value = mathtoi(node->prev->str) - mathtoi(node->next->str);
			break;
		case '<':
			switch (node->str[1])
			{
				case '=':
					value = mathcmp(node->prev->str, node->next->str) <= 0;
					break;
				case '<':
					value = mathtoi(node->prev->str) << mathtoi(node->next->str);
					break;
				default:
					value = mathcmp(node->prev->str, node->next->str) < 0;
					break;
			}
			break;
		case '>':
			switch (node->str[1])
			{
				case '=':
					value = mathcmp(node->prev->str, node->next->str) >= 0;
					break;
				case '>':
					value = mathtoi(node->prev->str) >> mathtoi(node->next->str);
					break;
				default:
					value = mathcmp(node->prev->str, node->next->str) > 0;
					break;
			}
			break;

		case '&':
			switch (node->str[1])
			{
				case '&':
					value = mathtoi(node->prev->str) && mathtoi(node->next->str);
					break;
				default:
					value = mathtoi(node->prev->str) & mathtoi(node->next->str);
					break;
			}
			break;
		case '^':
			switch (node->str[1])
			{
				case '^':
					value = ((mathtoi(node->prev->str) || mathtoi(node->next->str)) && (!mathtoi(node->prev->str) != !mathtoi(node->next->str)));
					break;

				default:
					value = mathtoi(node->prev->str) ^ mathtoi(node->next->str);
					break;
			}
			break;
		case '|':
			switch (node->str[1])
			{
				case '|':
					value = mathtoi(node->prev->str) || mathtoi(node->next->str);
					break;
				default:
					value = mathtoi(node->prev->str) | mathtoi(node->next->str);
					break;
			}
			break;
		case '=':
			value = (mathcmp(node->next->str, node->prev->str) == 0);
			break;
		case '!':
			value = (mathcmp(node->next->str, node->prev->str) != 0);
			break;
		default:
			value = 0;
			break;
	}

	if (node->prev == mathnode_s)
	{
		mathnode_s = node;
	}

	if (node->next == mathnode_e)
	{
		mathnode_e = node;
	}

	del_mathnode(node->next);
	del_mathnode(node->prev);

	node->prt = EXP_PR_VAR;

	sprintf(temp, "%lld", value);
	free(node->str);
	node->str = strdup(temp);
}

long long mathtoi(const char *str)
{
	switch (str[0])
	{
		case '!':
			return !atoll(&str[1]);

		case '~':
			return ~atoll(&str[1]);

		case '+':
			return +atoll(&str[1]);

		case '-':
			return -atoll(&str[1]);

		default:
			return atoll(str);
	}
}

long long mathcmp(const char *left, const char *right)
{
	switch (left[0])
	{
		case '"':
			return strcmp(left, right);

		default:
			return mathtoi(left) - mathtoi(right);
	}
}

long long mathdice(const char *left, const char *right)
{
	long long cnt, numdice, sizedice, sum;

	numdice  = mathtoi(left);
	sizedice = mathtoi(right);

	for (cnt = sum = 0 ; cnt < numdice ; cnt++)
	{
		sum += lrand48() % sizedice + 1;
	}
	return sum;
}