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


/*	the interpreter state	*/

#define VARS_MAX	32
#define NAME_MAX	32
#define OPBUF_MAX	1024

typedef struct state_s
{
	int		varcount;
	char	varkeys[ VARS_MAX * NAME_MAX ];
	int		varvals[ VARS_MAX ];
	char	opbuf[ OPBUF_MAX ];
}
state_t;


/*	variables	*/
int state_var_find( state_t* S, const char* name )
{
	char* at = S->varkeys;
	int i = 0;

	while( *at )
	{
		char* atend = at;
		while( *atend && *atend != '=' )
			atend++;

		if( strncmp( at, name, atend - at ) == 0 )
			return i;

		if( !*atend )	break;
		else			at = atend + 1;
		i++;
	}

	return -1;
}

int state_var_add( state_t* S, const char* name )
{
	assert( S->varcount < VARS_MAX );
	assert( strlen( name ) < NAME_MAX );

	S->varcount++;
	strcat( S->varkeys, name );
	strcat( S->varkeys, "=" );
	return S->varcount - 1;
}

void state_var_set( state_t* S, const char* name, int val )
{
	int at = state_var_find( S, name );

	if( at < 0 )	S->varvals[ state_var_add( S, name ) ] = val;
	else			S->varvals[ at ] = val;
}

int state_var_get( state_t* S, const char* name )
{
	int at = state_var_find( S, name );

	if( at < 0 )	return 0;
	else			return S->varvals[ at ];
}


/*	operation buffer	*/
void state_opbuf_remove( state_t* S, int from, int to )
{
	int len = strlen( S->opbuf );

	memmove(
		S->opbuf + from,
		S->opbuf + to + 1,
		len - to );
}

void state_opbuf_replace( state_t* S, int from, int to, const char* str )
{
	int len 	= strlen( S->opbuf );
	int slen	= strlen( str );

	memmove(
		S->opbuf + from + slen,
		S->opbuf + to + 1,
		len - to );

	memcpy( S->opbuf + from, str, slen );
}

int state_opbuf_findbest( state_t* S )
{
	int op = -1;
	int weight = -1;
	int level = 0;

	char* ptr = S->opbuf;
	while( *ptr )
	{
		if( *ptr == '(' )		level++;
		else if( *ptr == ')' )	level--;
		else if( *ptr == '=' ||
			*ptr == '+' || *ptr == '-' ||
			*ptr == '*' || *ptr == '/' )
		{
			int wt;
			if( *ptr == '=' )	wt = 0;
			else if( *ptr == '+' || *ptr == '-' )	wt = 1;
			else if( *ptr == '*' || *ptr == '/' )	wt = 2;
			wt += level * 3;
			if( wt >= weight )
			{
				op = ptr - S->opbuf;
				weight = wt;
			}
		}

		ptr++;
	}

	return op;
}

void state_opbuf_cleanparens( state_t* S )
{
	int clean = 1;

	while( clean )
	{
		char* ptr = S->opbuf;
		int begin = -1;
		int ops = 0;
		clean = 0;

		while( *ptr )
		{
			if( *ptr == '(' )
			{
				begin = ptr - S->opbuf;
				ops = 0;
			}
			else if( *ptr == ')' )
			{
				if( !ops && begin >= 0 )
				{
					state_opbuf_remove( S, ptr - S->opbuf, ptr - S->opbuf );
					state_opbuf_remove( S, begin, begin );
					ptr -= 2;
					clean++;
				}
				begin = -1;
			}
			else if( strchr( "=+-*/", *ptr ) )
				ops++;

			ptr++;
		}
	}
}

void state_opbuf_getargs( state_t* S, int op, int* from, int* to )
{
	char* ptr = S->opbuf + op - 1;
	while( ptr >= S->opbuf && isalnum( *ptr ) ) ptr--;
	*from = ptr + 1 - S->opbuf;

	ptr = S->opbuf + op + 1;
	while( isalnum( *ptr ) ) ptr++;
	*to = ptr - 1 - S->opbuf;
}

void state_opbuf_parse( state_t* S )
{
	int op;

printf( "[opbuf_parse] input: %s\n", S->opbuf );

	state_opbuf_cleanparens( S );
	op = state_opbuf_findbest( S );

	while( op >= 0 )
	{
		char optype = S->opbuf[ op ];
		char operand1[ NAME_MAX ];
		char operand2[ NAME_MAX ];
		char outbuf[ NAME_MAX ];
		int from, to, opval1, opval2, value;

		state_opbuf_getargs( S, op, &from, &to );
		assert( op != from && op != to );

printf( "[opbuf_parse] " );
fwrite( S->opbuf + from, 1, to - from + 1, stdout );

		memcpy( operand1, S->opbuf + from, op - from );
		operand1[ op - from ] = 0;
		memcpy( operand2, S->opbuf + op + 1, to - op );
		operand2[ to - op ] = 0;

		if( isdigit( *operand1 ) )
		{
			assert( optype != '=' );
			opval1 = atoi( operand1 );
		}
		else if( optype != '=' )
			opval1 = state_var_get( S, operand1 );

		if( isdigit( *operand2 ) )
			opval2 = atoi( operand2 );
		else
			opval2 = state_var_get( S, operand2 );

		switch( optype )
		{
		case '=':
			state_var_set( S, operand1, opval2 );
printf( "\t=> set( %s, %d )", operand1, opval2 );
			state_opbuf_remove( S, op, to );
			break;
		case '+': case '-': case '*': case '/':
			if( optype == '+' )			value = opval1 + opval2;
			else if( optype == '-' )	value = opval1 - opval2;
			else if( optype == '*' )	value = opval1 * opval2;
			else if( optype == '/' )	value = opval1 / opval2;

printf( "\t=> %d %c %d = %d", opval1, optype, opval2, value );
			sprintf( outbuf, "%d", value );
			state_opbuf_replace( S, from, to, outbuf );
			break;
		default:
			state_opbuf_replace( S, from, to, "0" );
		}

putchar( '\n' );

		state_opbuf_cleanparens( S );
		op = state_opbuf_findbest( S );
	}

	S->opbuf[ 0 ] = 0;
}


/*	high-level functions	*/
void state_init( state_t* S )
{
	S->varcount 	= 0;
	S->varkeys[ 0 ]	= 0;
	S->opbuf[ 0 ] 	= 0;
}

void state_dump( state_t* S )
{
	int i = 0;
	char* ptr = S->varkeys;

	printf( "-- state dump --\n" );
	printf( "number of variables: %d\n", S->varcount );

	while( *ptr )
	{
		char* pbeg = ptr;
		while( *ptr && *ptr != '=' )
			ptr++;

		fwrite( pbeg, 1, ptr - pbeg, stdout );
		putchar( '=' );
		printf( "%d\n", S->varvals[ i++ ] );

		if( *ptr == '=' ) ptr++;
	}
}

void state_interpret( state_t* S, const char* str )
{
	const char* ptr = str;

	S->opbuf[ 0 ] = 0;
	while( *ptr )
	{
		if( *ptr == ';' )
		{
			state_opbuf_parse( S );
		}
		else if( isalnum( *ptr ) || strchr( "=+-*/()", *ptr ) )
		{
			strncat( S->opbuf, ptr, 1 );
		}
		ptr++;
	}
}



const char* sample_program =
"a = 5;\t"
"b = 3;\t"
"c = a;\n"
"d = b + c * a + b;\n"
"e = a + b * ( c + d );\n"
"g = f = d;";

int main()
{
	printf( "DumbScript 3: a primitive interpreter\n-----\nCode:\n" );
	printf( sample_program );
	printf( "\n-----\nOutput:\n" );

	state_t state;
	state_init( &state );
	state_interpret( &state, sample_program );
	state_dump( &state );

	printf( "\n-----\n" );
	return 0;
}