/********************************************************************
 * Parse.c (C) copyright 1987 John M. Olsen
 *
 * /|  |    /|||  /\|		|	John M. Olsen
 * \|()|\|\_ |||. \/|/)@|\_	|	1547 Jamestown Drive
 *  |				|	Salt Lake City, UT  84121-2051
 * u-jmolse@ug.utah.edu  or  ...!{seismo,ihnp4}!utah-cs!utah-ug!u-jmolse
 *
 * This program or any significant portion of it may not be used in a
 * commercial product without written permission of the author.  (My
 * permission is easy to get).
 *
 * Feel free to distribute this code as part of any public domain collection,
 * or hack on it to make it more user friendly, as long as you try to
 * document your changes as not being my code.
 *
 * This is a recursive descent exprsession parser, based very loosely on one
 * found in Herbert Schildt's book "Advanced C", published by McGraw-Hill.
 * It parses expressions by having each layer either recognize something that
 * it can do, or passing it on to the next function which does higher
 * precedence operators.
 *
 * It has very minimal error checking, and does not check for overflow or
 * underflow on calculations.  If it detects an error, it will give a message
 * and what it thinks the correct result was up to that time.
 *
 * It converts expressions to lower case so it only needs to look for math
 * function names spelled one way.
 *
 * It uses standard I/O, so it must be used from the CLI.  This makes it
 * very easy to port to other machines.
 *
 * Aztec instructions using fast floating point:
 *
 * cc parse.c
 * ln parse.o -lm -lc
 *
 * Aztec 4.30a using IEEE double precision floating point: (Big difference!)
 *
 * cc parse.c +fi
 * ln parse.o -lmx -lc
 *
 * It has also been (fairly) successfully compiled on a VAX1180, but it
 * complained at expressions on the argument list.  The only modification
 * required was to comment out the #include <functions.h> command.
 *
 *********************************************************************/

#include <stdio.h>
#include <ctype.h>
#include <functions.h>
#include <math.h>

#define PI ((double)3.14159265358979)
#define E  ((double)2.71828182845904)

#define TOK_SIZE 20	/* Tokens are no longer than this number. */
#define EXP_SIZE 80	/* Expressions no longer than this number. */

#define TRUE 1
#define FALSE 0

extern double atof(), binary(), fn_eval();
extern double parse(), parse2(), parse3(), parse4(), parse5();

/* Here is a simple calling program to test it. */

main (argc, argv)
int argc;
char *argv[];
{
	char exprs[EXP_SIZE];
	double ans;
	int loop;

	if(argc < 2)
	{
		ans = 0;
		printf("Type '?' for help.\n");
		printf("Enter exprsression: ");
		gets (exprs);
	}
	else
	{
		exprs[0] = NULL;
		for(loop = 1; loop < argc; loop++)
			strcat(exprs, argv[loop]);
	}
	for(loop = 0; loop < strlen(exprs); loop++) /* convert to lower case */
		if(isalpha(exprs[loop]))
			exprs[loop] = tolower(exprs[loop]);
	if(exprs[0] == '?' || exprs[0] == 'h')
	{	/* help menu */
		printf("Supported binary operators: + - / % ^\n");
		printf("Supported unary operators:  + -\n");
		printf("Supported unary functions:  sin, cos, tan,\n");
		printf("	asin, acos, atan, sinh, cosh, tahn,\n");
		printf("	log, logten, abs, sqrt, int.\n");
		printf("Defined constants:          pi, e.\n\n");
		printf("Usage: %s (expression)\n", argv[0]);
		printf("   or: %s ?\n", argv[0]);
		exit(0);
	}
	ans = parse (exprs);
	if(exprs[0])
		printf("Bad expression.\n");
	else
		printf ("%f\n", ans);
}

/*******************************************************************
The main parser function. It parses + and -.
*******************************************************************/
double parse (exprs)
char exprs[];
{
	char tok[TOK_SIZE];	/* this should only be a + or - character. */
	double a;

	a = parse2 (exprs);
	while (exprs[0])
	{
		get_token (tok, exprs);
		if (tok[0] == '+' || tok[0] == '-')
			a = binary (a, parse2 (exprs), tok);
		else
			return (a);
	}
	return (a);
}

/*******************************************************************
The secondary parser, which parses * and /.
*******************************************************************/
double parse2 (exprs)
char *exprs;
{
	char tok[TOK_SIZE];
	double a;

	a = parse3 (exprs);
	while (exprs[0])
	{
		get_token (tok, exprs);
		if (tok[0] == '*' || tok[0] == '/' || tok[0] == 'm'
					 || tok[0] == 'd')
			a = binary (a, parse3 (exprs), tok);
		else
		{
			unget_tok (tok, exprs);
			return (a);
		}	
	}
	return (a);
}

/*******************************************************************
The third parser, which parses ^.
*******************************************************************/
double parse3 (exprs)
char *exprs;
{
	char tok[TOK_SIZE];
	double a;

	a = parse4 (exprs);
	while (exprs[0])
	{
		get_token (tok, exprs);
		if (tok[0]=='^')
			a = (binary (a, parse4 (exprs), tok));
		else
		{
			unget_tok (tok, exprs);
			return (a);
		}	
	}
	return (a);
}

/*******************************************************************
The fourth parser, which parses unary minus and plus.
*******************************************************************/
double parse4 (exprs)
char *exprs;
{
	char tok[TOK_SIZE];

	get_token (tok, exprs);
	if (tok[0] == '-')
		return (-(parse4 (exprs)));
	else if(tok[0] == '+')
		return(parse4(exprs));
	unget_tok (tok, exprs);
	return (parse5 (exprs));
}

/*******************************************************************
The fifth parser, which parses functions and parentheses.
*******************************************************************/
double parse5 (exprs)
char *exprs;
{
	char tok[TOK_SIZE], buff[EXP_SIZE];
	double a;

	get_fn (tok, exprs);
	if (tok[0])	/* a function call. */
		return (fn_eval (tok, exprs));
	get_numb (tok, exprs);
	if (tok[0])	/* A number. */
		return (atof (tok));
	if (exprs[0] == '(')	/* a parenthesized exprsression. */
	{	/*strip open paren, call parse, strip close paren. */
		strcpy (buff, exprs + 1);
		strcpy (exprs, buff);
		a = parse (exprs);
		if (exprs[0] == ')')
		{
			strcpy (buff, exprs + 1);
			strcpy (exprs, buff);
		}
		else
		{	/* Error if here. */
			printf("Bad parentheses.\n");
		}
		return (a);
	}
	printf("Bad parentheses.\n");
}

/*******************************************************************
Return a pointer to a string with the token in it.  A token may be
at most TOK_SIZE characters.  All after that are tossed into the
bit bucket.
*******************************************************************/
get_token (tok, exprs)
char *tok, *exprs;
{
	char temp[EXP_SIZE];

	tok[0] = 0;
	while (iswhite (exprs[0]))	/* move from exprs[1] to exprs[0] */
	{
		strcpy (temp, exprs + 1);
		strcpy (exprs, temp);
	}
	sscanf (exprs, "%1[+-*/^]", tok);
	strcpy (temp, exprs + strlen (tok));
	strcpy (exprs, temp);
}

/*******************************************************************
Get a number from the front of the exprsression.
*******************************************************************/
get_numb (tok, exprs)
char *tok, *exprs;
{
	char temp[EXP_SIZE];

	tok[0] = 0;
	while (iswhite (exprs[0]))	/* move from exprs[1] to exprs[0] */
	{
		strcpy (temp, exprs + 1);
		strcpy (exprs, temp);
	}
	sscanf (exprs, "%[0123456789.]", tok);
	strcpy (temp, exprs + strlen (tok));
	strcpy (exprs, temp);
}
/*******************************************************************
Get a function name from the front of the exprsression.
*******************************************************************/
get_fn (tok, exprs)
char *tok, *exprs;
{
	char temp[EXP_SIZE];

	tok[0] = 0;
	while (iswhite (exprs[0]))	/* move from exprs[1] to exprs[0] */
	{
		strcpy (temp, exprs + 1);
		strcpy (exprs, temp);
	}
	sscanf (exprs, "%[abcdefghijklmnopqrstuvwxyz]", tok);
	strcpy (temp, exprs + strlen (tok));
	strcpy (exprs, temp);
}

/*******************************************************************
Replace a token at the front of the exprsression.
*******************************************************************/
unget_tok (tok, exprs)
char *tok, *exprs;
{
	char buff[EXP_SIZE];

	strcpy (buff, exprs);
	strcpy (exprs, tok);
	strcat (exprs, buff);
}

/*******************************************************************
This fn returns true if the key given to it is white space.
*******************************************************************/
iswhite (key)
char key;
{
	if (key == ' ' || key == 9 || key == 13)
		return (1);
	return (0);
}
/*******************************************************************
This fn returns (a operator b), or just a if an error occurs.
*******************************************************************/
double binary (a, b, tok)
double a, b;
char *tok;
{
	int loop;
	double c;

	switch (tok[0])
	{
		case '+':
			return (a + b);
		case '-':
			return (a - b);
		case '*':
			return (a * b);
		case '/':
			if (!near_zero (b))	/* if b != 0 */
				return (a / b);
			else
			{	/* division by zero error message. */
				printf("Division by zero error.\n");
			}
			return (a);
		case '^':	/* a to the b power. */
		{
			c = a;
			if (near_zero (b))	
				return (a);
			return(pow(a,b));
			/* non-function if you don't like the pow function */
			for (loop = (int) b - 1;loop > 0; --loop)
				a = a * c;
			return (a);
		}
		default:
			printf("No such token as %c\n", tok[0]);
	}
}

/*******************************************************************
Evaluates the function on the front of exprs.
*******************************************************************/
double fn_eval (tok, exprs)
char *exprs, *tok;
{
	if (tok[0])
	{
		if (!strcmp(tok, "abs"))
			return(fabs (parse5(exprs)));
		if (!strcmp(tok, "sqrt"))
			return(sqrt (parse5(exprs)));
		if (!strcmp(tok, "tan"))
			return(tan (parse5(exprs)));
		if (!strcmp(tok, "sin"))
			return(sin (parse5(exprs)));
		if (!strcmp(tok, "cos"))
			return(cos (parse5(exprs)));
		if (!strcmp(tok, "atan"))
			return(atan (parse5(exprs)));
		if (!strcmp(tok, "asin"))
			return(asin (parse5(exprs)));
		if (!strcmp(tok, "acos"))
			return(acos (parse5(exprs)));
		if (!strcmp(tok, "tanh"))
			return(tanh (parse5(exprs)));
		if (!strcmp(tok, "sinh"))
			return(sinh (parse5(exprs)));
		if (!strcmp(tok, "cosh"))
			return(cosh (parse5(exprs)));
		if (!strcmp(tok, "pi"))
			return(PI);
		if (!strcmp(tok, "e"))
			return(E);
		if (!strcmp(tok, "log"))
			return(log(parse5(exprs)));
		if (!strcmp(tok, "logten"))
			return(log10(parse5(exprs)));
		if (!strcmp(tok, "int"))
			return((double)((long)(parse5(exprs))));
	}
	printf("Could not find expression %s\n",tok);
	unget_tok(tok, exprs);
}

/*******************************************************************
Returns true if num is near zero. It's used in division checks.
*******************************************************************/
near_zero (num)
double num;
{
	if (fabs (num) < .000000001)
		return (1);
	return (0);
}