// eval3.cpp   7 February, 1997

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

#define MaxTokenLen		(10)
#define MaxStmtLen		(100)
#define MaxStackDepth	(10)
#define MaxSymbols		(2)

typedef enum {
	UnknownS_e,
		skip_e,		// Discard statement, but continue program.
		stop_e		// Terminate program.
} severity_t;
typedef char	token_t[MaxTokenLen+1];	// Leave one extra character for the terminating null.
typedef enum {
	UnknownTT_e, symbol_e, number_e
} TokenType_t;
typedef double	value_t;
typedef struct {
	token_t	name;
	value_t	value;
} symbol_t;

char		statement[MaxStmtLen];
int			StmtLen,
			StmtIndex;

token_t		token;
value_t		TokenValue;	// For storing the value of a literal numeric constant.
TokenType_t	TokenType;

value_t		stack[MaxStackDepth];
int			StackDepth;				// Indicates the first empty place on the stack.
symbol_t	symbols[MaxSymbols] = {
	{"e",		2.71828182845904523536},
	{"pi",		3.14159265358979323846},
};

// Support routines. -----------------------------------------------------------

bool equal (token_t a, token_t b) {
	if (!a && !b) return true;
	if (!a || !b) return false;
	return stricmp (a, b) == 0;
}

void error (severity_t severity, char *msg1, char *msg2 = 0) {
	if (msg2 != 0) {
		printf ("%s %s\n", msg1, msg2);
	} else {
		printf ("%s\n", msg1);
	}
	throw severity;	// Raise an exception which will be caught in main().
}

void push (value_t v) {
	if (StackDepth < MaxStackDepth) {
		stack[StackDepth] = v;
		++StackDepth;
	} else {
		error (skip_e, "stack overflow");
	}
}

// Using a temporary variable for the return value instead of returning it
// directly is slightly inefficient, especially since we know that we will not
// return from error(), but this way illustrates clearly what we want to do and
// the compiler doesn't winge about not returning anything from this routine if
// we put the error() call last.
value_t pop (void) {
	value_t	v;
	
	if (StackDepth > 0) {
		--StackDepth;
		v = stack[StackDepth];
	} else {
		error (skip_e, "stack underflow");
	}
	
	return v;
}

// Look up a symbol.
value_t GetValue (token_t name) {
	int	i;
	
	for (i = 0 ; i < MaxSymbols && !equal (name, symbols[i].name) ; ++i)
		/* Scan through the symbol table. */ ;
		if (i == MaxSymbols) error (skip_e, "symbol not found", name);
		return symbols[i].value;
}

// Lexical analysis. -----------------------------------------------------------

void GetNextToken (void) {
	int	TokenLen;
	
	// Skip leading whitespace.
	while ((StmtIndex < StmtLen) && (strchr (" \t", statement[StmtIndex]) != 0) ){
		++StmtIndex;
	}
	if (StmtIndex == StmtLen) {
		error (skip_e, "No more tokens to get");
	}
	token[0] = statement[StmtIndex];
	TokenLen = 1;
	++StmtIndex;
	
	TokenType = UnknownTT_e;
	if (isalpha (token[0])) {
		TokenType = symbol_e;
		// Token is an identifier.
		// Read in the remainder of the symbol name.
		while (	StmtIndex < StmtLen					// Are there any more characters?
				&& TokenLen < MaxTokenLen			// Have we room for more characters?
				&& isalnum (statement[StmtIndex])	// Do we want them?
		) {
			token[TokenLen] = statement[StmtIndex];
			++TokenLen;
			++StmtIndex;
		}
		if (StmtIndex < StmtLen						// Is another character available?
			&& TokenLen == MaxTokenLen				// Have we run out of room for it?
			&&	isalnum (statement[StmtIndex])		// Did we want it?
		) {
			token[TokenLen-1] = 0;	// Terminate the partial token so that we can print it,
			error (skip_e, "Identifier too long for token buffer", token);
		}
	} else if (isdigit (token[0])) {
		TokenType = number_e;
		--StmtIndex;	// Back up a character and read the whole number in.
		if (sscanf (&statement[StmtIndex], "%lf%n", &TokenValue, &TokenLen) == 1) {
			StmtIndex = StmtIndex + TokenLen;
		} else {
			// We know this started with a digit or we wouldn't have decided it was
			// a number, so we can't possibly be here.  It's just something else
			// that can be checked, so I checked it.
			error (skip_e, "program error - couldn't read number", &statement[StmtIndex-1]);
		}
	} else {
		// Hopefully an operator of some kind.
	}
	token[TokenLen] = 0;	// Terminate token string.
}

void init (FILE *input) {
	// Initialise lexical bits.
	if (!fgets (statement, sizeof (statement), input)) {
		if (feof (input)) {
			error (stop_e, "Done");	// Not really an error, but we need to stop.
		}
		statement[0] = 0;
	}
	StmtLen = strlen (statement);
	StmtIndex = 0;
	
	GetNextToken ();
	
	// Initialise parser/evaluation bits.
	StackDepth = 0;
}

// Syntax analysis. ------------------------------------------------------------

void ParseExpression (void);	// Forward declaration.

void ParsePrimary (void) {
	switch (TokenType) {
		case number_e:
			push (TokenValue);
			break;

		case symbol_e:
			push (GetValue (token));
			break;

		default:
			if (equal ("\n", token)) {
				return;			// All done.
			} else {
				error (skip_e, "unexpected token", token);
			}
			break;
	}
	GetNextToken ();
}

void ParseFactor (void) {
	bool	unary_minus = false;
	
	// Handle optional sign
	if (equal ("+", token)) {
		// Just ignore unary pluses and they'll go away.
		GetNextToken ();
	} else if (equal ("-", token)) {
		// We have to do something about unary minuses, but not right now.
		unary_minus = true;	// Remember that we had it so we can do something
		GetNextToken ();	// before leaving ParseFactor().
	}
	
	// Have we found a bracketed expression or a primary expression?
	if (equal ("(", token)) {
		GetNextToken ();
		ParseExpression ();
		GetNextToken ();	// Discard ")"
	} else {
		ParsePrimary ();
	}
	
	if (unary_minus) {		// If the expression was preceeded by a unary minus,
		push (-pop());		// we negate the top value on the stack.
	}
}

void ParseTerm (void) {
	ParseFactor ();
	while (equal ("*", token) || equal ("/", token)) {
		token_t	op;
		value_t	a, b;
		
		strcpy (op, token);
		GetNextToken ();
		ParseFactor ();
		
		b = pop ();
		a = pop ();
		if (equal ("*", op)) {
			push (a * b);
		} else {
			push (a / b);
		}
	}
}

void ParseExpression (void) {
	ParseTerm ();
	while (equal ("+", token) || equal ("-", token)) {
		token_t	op;
		value_t	a, b;
		
		strcpy (op, token);
		GetNextToken ();
		ParseTerm ();
		
		b = pop ();
		a = pop ();
		if (equal ("+", op)) {
			push (a + b);
		} else {
			push (a - b);
		}
	}
}

// Top level of program. -------------------------------------------------------

int main (int argc, char *argv[]) {
	char	*filename = "eval3.dat";
	FILE	*input;
	bool	done = false;
	
	if (argc > 1) {
		filename = argv[1];
	}
	if (equal ("-", filename)) {
		input = stdin;
	} else {
		input = fopen (filename, "r");
	}
	
	if (input == 0) {
		printf ("Couldn't open '%s'.\n", filename);
		exit (1);
	}
	
	do {
		try {
			init (input);
			
			ParseExpression ();
			// Token should now be a newline.
			
			if (StackDepth > 1) error (skip_e, "Final stack too deep");
			if (StackDepth < 1) error (skip_e, "No final value on stack");
			printf ("    %g\n", pop ());
		}
		catch (severity_t severity) {
			switch (severity) {
				case skip_e:					break;
				case stop_e:	done = true;	break;
				default:						break;
			}
		};
	} while (!done);
	fclose (input);
	
	return 0;
}