/* expressions.c
	This program is a recursive implementation of a
	simple context-free grammar describing arithmetic
	expressions involving integers, addition (+),
	multiplication (*), and parentheses.
	
	<expression> = <term> or <term> + <expression>
	<term> = <factor> or <factor> * <term>
	<factor> = (<expression>) or <integer>
	<integer> = any string of digits
	
	This program assumes there is no white space in
	the string.
*/
 
#include <stdio.h>

enum{
	FALSE=0,
	TRUE
};

int expression();
int term();
int factor();
int integer();
void getLine( char * );
 
int	error, index;
char	string[100];
 
main()
{
	int	value;
 
    /* Get the expression,... */
	printf( "Enter an expression: " );
	getLine( string );
	index = 0;
	error = FALSE;
	
    /* ...compute its value,... */
	value = expression();

    /* ...and report the results. */
	if( error == TRUE )
		printf( "Error\n" );
	else
		printf( "%s = %d\n", string, value );
}
 
 
int expression()
{
	int		value;

	value = term();
	if( string[index] == '+' ){
		index++;
		value = value + expression();
	}
	
	return( value );
}
 
int term()
{
	int	value;
	
	value = factor();
	if( string[index] == '*' ){
		index++;
		value = value * term();
	}

	return( value );
}
 
int factor()
{
	int	value;
	
	if( string[index] == '(' ){
		index++;
		value = expression();
		if( string[index] == ')' )
			index++;
		else
			error = TRUE;
	} else
		value = integer();
	
	return( value );
}

/* Runs through a sequence of digits starting at
   string[index], and returns the integer they
   represent.  If string[index] is not a digit,
   integer() sets error equal to TRUE and returns
   0. */
int integer()
{
	int	value;
	char	d;

	value = 0;
	d = string[index];

	if( d < '0' || d > '9' )
		error = TRUE;
		
	while( d >= '0'  &&  d <= '9' ){
		value = value*10 + d - '0';
		index++;
		d = string[index];
	}

	return( value );
}


/* Gets a line of text from the keyboard.  The
   newline character is not put into s. */
void getLine( char *s )
{
	*s = getchar();
	while( *s != '\n' ){
		s++;
		*s = getchar();
	}
	*s = '\0';
}