/*
	expr --> ( expr ) | expr op expr | number | expr expr | x
  x --> [:alpha:][:word:]*
	op --> + | - | * | /
	number --> integer
	integer --> integer digit | digit
	digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

  built-in function: pow (pow a b = a^b), sin
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

#define SUCC 0
#define FAIL 1
#define YES 0
#define NO 1
#define EMPTY -1
#define STACK_LIMIT 80

struct ENV;
union data;
struct function {
  void (*code)(struct ENV*, union data);
  struct ENV* env;
};

typedef union data { char op; double value; struct function fun; } DATA;

typedef struct stack {
	int type;								/* 0: operator, 1: data, 2: function */
	DATA data;
	int priority; } STACK_DATA;

struct stack STACK[STACK_LIMIT];
int STACK_TOP = EMPTY;

char expr[80];
int i = 0;

void push( STACK_DATA data )

{
  if ( STACK_TOP < STACK_LIMIT - 1 )
    STACK[++STACK_TOP] = data;
  else
  {
    printf( "\nStack Overflow!!\n" );
    exit( 1 );
  }
}

STACK_DATA pop( void )

{
  if ( STACK_TOP != EMPTY )
    return( STACK[STACK_TOP--] );
  else
  {
    printf( "\nStack Underflow!!\n" );
    exit( 1 );
  }
}






struct ENV {
  char var[16];
  int type;
  DATA value;
  struct ENV *next;
};

struct ENV *top_env, env_mem[100];
int env_num;
struct ENV* alloc_env(void) {
  if (env_num == 100) {
    printf("not enough memory\n");
    exit(1);
  }
  struct ENV* env = env_mem+env_num;
  ++env_num;
  return env;
}

struct ENV* lookup_assume_exists(struct ENV* curr, const char* var) {
  while (curr) {
    if (strcmp(var, curr->var) == 0)
      return curr;
    curr = curr->next;
  }
  printf("Unbound variable %s\n", var);
  exit(1);
}

void variable(void) {
  char var[16];
  int k = 0;
  while (expr[i] && isalnum(expr[i])) {
    var[k] = expr[i];
    ++i;
    ++k;
  }
  var[k] = 0;

  struct ENV* entry = lookup_assume_exists(top_env, var);
  STACK_DATA data;
  data.type = entry->type;
  data.data = entry->value;
  data.priority = 0;
  push(data);
}

void apply() {
  DATA arg = pop().data;
  struct function f = pop().data.fun;
  f.code(f.env, arg);
}

void push_sin(struct ENV* env_unused, DATA arg) {
  STACK_DATA data;
  data.type = 1;
  data.data.value = sin(arg.value);
  data.priority = 0;
  push(data);
}

void push_pow_has_base(struct ENV* env, DATA arg) {
  STACK_DATA data;
  data.type = 1;
  data.data.value = pow(lookup_assume_exists(env, "base")->value.value, arg.value);
  data.priority = 0;
  push(data);
}

void push_pow(struct ENV* env, DATA arg) {
  struct ENV *cl = alloc_env();
  strcpy(cl->var, "base");
  cl->type = 1;
  cl->value.value = arg.value;
  cl->next = env;

  STACK_DATA data;
  data.type = 2;
  data.data.fun.code = push_pow_has_base;
  data.data.fun.env = cl;
  data.priority = 0;
  push(data);
}








int number( void )

{
	STACK_DATA data;
	int k = 0, mantissa = NO;
	char value[80];

	while ( expr[i] >= '0' && expr[i] <= '9' )		/* integer */
	{
		mantissa = YES;
		value[k++] = expr[i++];
	}

	value[k] = '\0';

	data.type = 1;
	data.data.value = atof( value );
	data.priority = 0;
	push( data );

	return( SUCC );
}

int evaluate( void )

{
	STACK_DATA data, data1, data2, opcode;

	if ( STACK_TOP == EMPTY )
		return( FAIL );
	data1 = pop();
	if ( data1.type != 1 )
		return( FAIL );				/* not an operand */

	if ( STACK_TOP == EMPTY )
		return( FAIL );
	opcode = pop();
	if ( opcode.type != 0 )
		return( FAIL );				/* not an operator */

	if ( STACK_TOP == EMPTY )
		return( FAIL );
	data2 = pop();
	if ( data2.type != 1 )
		return( FAIL );				/* not an operand */

	switch( opcode.data.op )
	{
		case '+' : data.data.value = data2.data.value + data1.data.value;
			break;
		case '-' : data.data.value = data2.data.value - data1.data.value;
			break;
		case '*' : data.data.value = data2.data.value * data1.data.value;
			break;
		case '/' : data.data.value = data2.data.value / data1.data.value;
			break;
		default: return( FAIL );
			break;
	}

	data.type = 1;
	data.priority = 0;
	push( data );

	return( SUCC );
}

int right_parenthesis( void )

{
	STACK_DATA data;

	while ( STACK_TOP != EMPTY )
	{
		if ( STACK_TOP-1 != EMPTY && STACK[STACK_TOP-1].data.op == '(' )
		{
			i++;
			data = pop();
			pop();								/* remove left parenthesis */
			push( data );
			return( SUCC );
		}
		else if ( evaluate() == FAIL )
			return( FAIL );
	}

	return( FAIL );
}

int parenthesis( void )
{
	STACK_DATA data;

	data.type = 0;
	data.data.op = expr[i++];
	data.priority = 0;						/* left_parenthesis */
	push( data );

	return( SUCC );
}

int op( void )
{
	STACK_DATA data;

	switch ( expr[i] )
	{
		case '+' :
		case '-' : data.priority = 1;
			break;
		case '*' :
		case '/' : data.priority = 2;
			break;
		default :
			return( FAIL );
	}

	while ( STACK_TOP > 0 && data.priority <= STACK[STACK_TOP-1].priority )
	{
		if ( evaluate() == FAIL )
			return( FAIL );
	}

	data.type = 0;
	data.data.op = expr[i++];
	push( data );

	return( SUCC );
}

int expression( void )
{
	while ( expr[i] == ' ' )				/* skip the leading spaces */
		i++;

  if ( expr[i] == '(' )
 		return( parenthesis() );			/* ( expr) */

  if ( expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/' )
		return( op() );						/* expr op expr */

	if ( expr[i] >= '0' && expr[i] <= '9'	)
		return( number() );					/* number */

	if ( expr[i] == ')')					/* end of parenthesis */
		return( right_parenthesis() );

  if (isalpha(expr[i])) {
    variable();
    return SUCC;
  }

	if ( expr[i] == '\0')					/* end of expression */
		return( SUCC );
	else
		return( FAIL );
}

int result( void )

{
	while ( STACK_TOP > 0 )
	{
		if ( evaluate() == FAIL )
			return( FAIL );
	}

	return( SUCC );
}

void calculate( void )
{
	STACK_DATA data;

	while ( expr[i] != '\0' )
	{
		if ( expression() == FAIL )		/* parse the exspression */
			break;
    if (STACK_TOP >= 1 && STACK[STACK_TOP-1].type == 2 && (STACK[STACK_TOP].type == 1 || STACK[STACK_TOP].type == 2))
      apply();
	}

	if ( expr[i] == '\0' )	/* end of expression */
    {
		if ( result() == SUCC && STACK_TOP == 0 )
		{
			data = pop();
			if ( data.type == 1 )
				printf( "The result is %g\n", data.data.value );
			else
				printf( "Error : Illegal expression\n" );
 		}
		else
			printf( "Error : Illegal expression\n" );
    }
	else
		printf( "Error : Illegal expression\n" );
}

void init( void )
{
	STACK_TOP = EMPTY;   /* clear stack */
	i = 0;





  env_num = 0;

  top_env = NULL;
  struct ENV* env_sin = alloc_env();
  strcpy(env_sin->var, "sin");
  env_sin->type = 2;
  env_sin->value.fun.code = push_sin;
  env_sin->next = NULL;

  struct ENV* env_pow = alloc_env();
  strcpy(env_pow->var, "pow");
  env_pow->type = 2;
  env_pow->value.fun.code = push_pow;
  env_pow->next = env_sin;

  top_env = env_pow;
  env_sin->value.fun.env = top_env;
  env_pow->value.fun.env = top_env;
}

int main( void )
{
	char ch;

	do
	{
		init();				/* initialize */

		printf( "Please keyin expression to be evaluated \n" );
		gets( expr );

		calculate();

		printf( "Continue (y/n) ? " );
		ch = getchar();
	} while( !( ch == 'n' || ch == 'N' ) );

	return( 0 );
}