/*
	expr --> ( expr ) | expr op expr | number
	op --> + | - | * | /
	number --> integer
	integer --> integer digit | digit
	digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

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

typedef union data { char op; double value; } DATA;

typedef struct stack {
	int type;								/* 0: operator, 1: data */
	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 );
  }
}

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 ( 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 ( 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;
}

int main( void )
{
	char ch;

	do
	{
		init();				/* initialize */
		
		printf( "Please keyin expression to be evaluated \n" );
		fflush( stdin );
		gets( expr );

		calculate();

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