home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Troubleshooting Netware Systems
/
CSTRIAL0196.BIN
/
attach
/
pcc
/
v08n03
/
math.exe
/
PARSER21.ZIP
/
FORMULC.C
next >
Wrap
C/C++ Source or Header
|
1994-08-23
|
19KB
|
711 lines
/*FORMULC.C 2.1 as of 8\18\94 */
/*A fast interpreter of mathematical functions */
/*Copyright (c) 1994 by Harald Helfgott */
/* This program must be distributed with its corresponding README.DOC */
/* The full copyright and availability notice is in README.DOC */
/* This program is provided "as is", without any explicit or */
/* implicit warranty. */
/* Programmer's Address:
Harald Helfgott
MB 1807, Brandeis University
P.O. Box 9110
Waltham, MA 02254-9110
OR
(during the summer)
2606 Willett Apt. 427
Laramie, Wyoming 82070
seiere@uwyo.edu */
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <errno.h>
#include <ctype.h>
#include "formulc.h"
#undef FORMU_DEBUG_ON
/* Substitute #define for #undef to trace evaluation */
#ifdef FORMU_DEBUG_ON
#define DBG(anything) anything
#else
#define DBG(anything) /* nothing */
#endif
static double pi(void);
static double value(UCHAR *function);
static CHAR *i_error; /*pointer to the character in source[]
that causes an error */
static UCHAR *i_trans(UCHAR *function, CHAR *begin, CHAR *end);
static CHAR *my_strtok(CHAR *s);
static UCHAR *comp_time(UCHAR *function, UCHAR *fend, int npars);
static double param['z'-'a'+1];
struct formu_item {
CHAR *name;
void *f; /* pointer to function*/
int n_pars; /* number of parameters (0, 1, 2 or 3) */
};
#define TABLESIZE 256
#define STD_LIB_NUM 12
static struct formu_item ftable[TABLESIZE]=
{{"exp",(void *) exp,1},
{"ln", (void *) log,1},
{"sin",(void *) sin,1},
{"cos",(void *) cos,1},
{"tan",(void *) tan,1},
{"asin",(void *) asin,1},
{"acos",(void *) acos,1},
{"atan",(void *) atan,1},
{"atan2",(void *) atan2,2},
{"abs", (void *) fabs,1},
{"sqrt", (void *) sqrt,1},
{"pi", (void *) pi,0},
{NULL,NULL,0}};
int read_table(int i, CHAR *name, int *n_pars)
/* returns 1 if succesful */
/* returns 0 otherwise */
{
if(!ftable[i].f)
return 0;
else {
strcpy(name,ftable[i].name);
*n_pars=ftable[i].n_pars;
return 1;
}
}
int where_table(CHAR *name)
/* If the function exists, where_table() returns the index of its name
in the table. Otherwise, it returns -1. */
{
struct formu_item *table_p;
for(table_p=ftable; table_p->f != NULL &&
strcmp(name,table_p->name); table_p++)
;
if(table_p->f == NULL) /*The end of the table has been reached,
but name[] is not there. */
return -1;
else return table_p - ftable;
}
int fdel(CHAR *name)
/* If the function exists, it is deleted and a non-negative value
is returned. */
/* Otherwise, -1 is returned. */
/* Original library functions may not be deleted. */
{
int place;
struct formu_item *scan;
if((place=where_table(name)) == -1)
return -1;
if(place<STD_LIB_NUM)
return -1;
free(ftable[place].name);
for(scan = &ftable[place]; scan->f!=NULL; scan++) {
DBG(printf("%s %s \t",scan->name,scan->f));
scan->name = (scan+1)->name;
scan->f = (scan+1) -> f;
scan->n_pars = (scan+1) -> n_pars;
}
return scan-ftable;
} /*end of fdel */
int fnew(CHAR *name, void *f, int n_pars)
{
struct formu_item *where;
if(n_pars<0 || n_pars>3)
return 0;
for(where=ftable; where->f != NULL && strcmp(name,where->name); where++);
if(where->f != NULL) {
where->f=f;
where->n_pars = n_pars; /*old function is superseded */
return 1;
} else if((where-ftable) >= TABLESIZE-1)
return 0; /*table is full */
else {
where->name = (char *) calloc(strlen(name)+1, sizeof(CHAR));
if(where->name==NULL) return 0; /* no memory */
strcpy(where->name,name);
where->f=f;
where->n_pars = n_pars;
return 1;
}
} /* end of fnew */
double f_x_val(UCHAR *function, double x)
{
param['x'-'a']=x;
return value(function);
}
double fval(UCHAR *function, CHAR *args, ...)
{
va_list ap;
double result;
DBG(puts("Enter fval"));
va_start(ap, args);
while(*args)
param[(*args++)-'a'] = va_arg(ap, double);
va_end(ap);
result=value(function);
return result;
}
#define BUFSIZE 500
double value(register UCHAR *function)
{
double buffer[BUFSIZE];
register double *bufp = buffer;
/* points to the first free space in the buffer */
double x,y,z;
register double result;
if(!function) return 0; /* non-existent function; result of
an unsuccesful call to translate */
for(;;) {
switch(*function++) {
case '\0':goto finish; /* this function must be as fast as possible */
case 'D': *bufp++ = *((double *) function)++;
DBG(printf("%g ",*(bufp-1)));
break;
case 'V': *bufp++ = param[(*function++)-'a'];
DBG( printf("%c = %g ",*(function-1),*(bufp-1)) );
break;
case 'M':DBG(printf("Unary - "));
result = -(*--bufp);
*bufp++ = result;
break;
case '+':DBG(printf("+ "));
y = *(--bufp);
result = y + *(--bufp);
*bufp++ = result;
break;
case '-':DBG(printf("- "));
y = *--bufp;
result= *(--bufp) - y;
*bufp++ = result;
break;
case '*':DBG(printf("* "));
y = *(--bufp);
result = *(--bufp) * y;
*bufp++ = result;
break;
case '/':DBG(printf("/ "));
y = *--bufp;
result = *(--bufp) / y;
*bufp++ = result;
break;
case '^':DBG(printf("^ "));
y = *--bufp;
result = pow(*(--bufp),y);
*bufp++ = result;
break;
case 'F':DBG(printf("%s ",ftable[*function].name));
switch(ftable[*function].n_pars) {
case 0:*bufp++ = (*((double (*)(void))
ftable[*function++].f))();
break;
case 1:x = *--bufp;
*bufp++ = (*((double (*)(double))
ftable[*function++].f))(x);
break;
case 2:y = *--bufp;
x = *--bufp;
*bufp++ = (*((double (*)(double,double))
ftable[*function++].f))(x,y);
break;
case 3:z = *--bufp;
y = *--bufp;
x = *--bufp;
*bufp++ = (*((double (*)(double, double, double))
ftable[*function++].f))(x,y,z);
break;
default:printf("Bug! too many parameters\n");
return 0;
break;
}
break;
default:puts("Bug! Unrecognizable operator");
return 0;
break;
}
}
finish: if((bufp-buffer)!=1)
{
putchar('\n');
puts("Bug! Too many things in the buffer");
printf("Buffer: ");
while(bufp-- > buffer)
printf("%g ",*bufp);
putchar('\n');
}
else DBG(putchar('\n'));
return buffer[0];
} /* end of value */
static int isoper(CHAR c)
{
return ((c == '+') || (c == '-') || (c == '*') || (c == '/')
|| (c == '^'));
}
static int is_code_oper(UCHAR c)
{
return ((c == '+') || (c == '-') || (c == '*') || (c == '/')
|| (c == '^') || (c == 'M'));
}
static int isin_real(CHAR c)
/* + and - are not included */
{
return (isdigit(c) || c=='.' || c=='E');
}
size_t max_size(CHAR *source)
/* gives an upper estimate of the size required for
the coded form of source (including the final '\0') */
/* Take care when modifying: the upper estimate
returned by max_size must not also accomodate
*proper* output, but also *improper* output
which takes place before the translator detects an error. */
{
int numbers=0;
int functions=0;
int operators=0;
int variables=0;
const size_t func_size=2*sizeof(UCHAR);
const size_t var_size=2*sizeof(UCHAR);
const size_t num_size=sizeof(UCHAR)+sizeof(double);
const size_t op_size=sizeof(UCHAR);
const size_t end_size=sizeof('\0');
CHAR *scan;
for(scan=source; *scan; scan++)
if(isalpha(*scan) && (*scan != 'E'))
{
if(isalpha(*(scan+1))) ; /* it is a function name,
it will be counted later on */
else if(*(scan+1) == '(') functions++;
else variables++;
}
if(isoper(*source)) operators++;
if(*source != '\0')
for(scan = source+1; *scan; scan++)
if(isoper(*scan) && *(scan-1) != 'E') operators++;
/* counting numbers.. */
scan=source;
while(*scan)
if(isin_real(*scan) || ((*scan == '+' || *scan == '-') &&
scan>source && *(scan-1)=='E'))
{numbers++;
scan++;
while(isin_real(*scan) || ((*scan == '+' || *scan == '-') &&
scan>source && *(scan-1)=='E'))
scan++;
}
else scan++;
return(numbers*num_size + operators*op_size + functions*num_size
+ variables*var_size + end_size);
/*Do you wonder why "functions" is multiplied with "num_size"
and not with func_size? This function calculates an upper-bound
(i.e. pessimistic) estimate. It supposes that all functions are
converted into doubles by comp_time. For example, pi() actually
becomes a double. */
}
UCHAR *translate(CHAR *source, CHAR *args, int *leng, int *error)
/* source and args are not modified, but the keyword "const"
is ommitted to avoid complaints of hypersensitive compilers */
{
UCHAR *result;
CHAR *scan, *scarg;
UCHAR *function;
UCHAR *nfunc; /* used to free unused heap space */
size_t size_estim; /* upper bound for the size of the
coded function */
i_error=NULL;
/* search for undeclared parameters */
for(scan=source; *scan != '\0'; scan++) {
if(islower(*scan) && !isalpha(*(scan+1)) &&
(scan==source || !isalpha(*(scan-1))) ) {
for(scarg=args; *scarg != '\0' && *scarg != *scan; scarg++)
;
if(*scarg == '\0') /*parameter not found */
{
i_error = scan;
*leng = 0;
*error = i_error - source;
return NULL;
}
}
} /* end of search for undeclared... */
size_estim=max_size(source); /* upper estimate of the size
of the coded function,
which doesn't exist yet */
if(!(function = (UCHAR *) malloc(size_estim))) {
/* out of memory */
*leng = 0;
*error = -1;
return NULL;
}
result=i_trans(function,source,source+strlen(source));
if(!result) {
free(function);
*leng = 0;
if(i_error)
*error = i_error-source;
else *error = -1; /* out of memory */
return NULL;
}
else { /* OK */
*result = '\0';
*error = -1;
*leng = result-function;
/* free unused heap space.. */
if(((*leng)+1) * sizeof(UCHAR) > size_estim)
/* one must use (*leng)+1 instead of *leng because '\0'
has not been counted */
{
printf("Dangerous bug! The size estimate falls short by %d bytes",
((*leng)+1) * sizeof(UCHAR) - size_estim);
puts(" Please, tell the author about this error immediately! ");
puts("Don't forget to write down what mathematical function caused");
puts("the program to crash. This program's reliability depends on you!");
puts("Press c and ENTER to continue");
getchar();
}
else if(((*leng)+1) * sizeof(UCHAR) < size_estim) {
if(nfunc = (UCHAR *) malloc(((*leng)+1) * sizeof(UCHAR))) {
memcpy( nfunc, function, ((*leng)+1) * sizeof(UCHAR) );
free(function);
function=nfunc;
}
/* free unused space */
return function;
} /* end of if-else stairs */
} /* end of OK */
} /* end of translate */
static UCHAR *comp_time(UCHAR *function, UCHAR *fend, int npars)
/* calculates at "compile time" */
/* Postconditions: If the coded expression in *function..*(fend-1)
can be calculated, its value is stored in *function..*(fend-1) */
/* comp_time returns a pointer to the first character after the
end of the coded function; if this function cannot be evaluated
at compile time, comp_time returns fend, of course. */
/* Only memory positions from *function to *comp_time are touched. */
{
UCHAR *scan;
int ok;
UCHAR temp;
double tempd;
ok=1;
scan=function;
while(npars-- > 0) {
if(*scan++ != 'D') ok=0;
((double *)scan)++;
}
if(!ok ||
!( ( scan == fend - (sizeof((UCHAR) 'F')+sizeof(UCHAR))
&& *(fend-2) == 'F' ) ||
( scan == fend - sizeof(UCHAR)
&& is_code_oper(*(fend-1)) ) )
)
/* compile-time evaluation is done only
if everything but the ending function consists of doubles */
return fend;
temp = *fend;
*fend = '\0';
tempd = value(function);
*fend = temp;
*function++ = 'D';
*((double *)function)++ = tempd;
return function;
} /* end of comp_time */
static CHAR *my_strtok(CHAR *s)
/* a version of strtok that respects parentheses */
/* token delimiter = comma */
{
int pars;
static CHAR *token=NULL;
CHAR *next_token;
if(s!=NULL) token=s;
else if(token!=NULL) s=token;
else return NULL;
for(pars=0; *s != '\0' && (*s != ',' || pars!=0); s++) {
if(*s == '(') ++pars;
if(*s == ')') --pars;
}
if(*s=='\0') {
next_token=NULL;
s=token;
token=next_token;
DBG(printf("The token is: %s\n",s));
return s;
} else {
*s = '\0';
next_token=s+1;
s=token;
token=next_token;
DBG(printf("The token is: %s\n",s));
return s;
}
} /* end of my_strtok */
#define TWO_OP { \
if((tempu=i_trans(function,begin,scan)) && \
(temp3=i_trans(tempu,scan+1,end)) ) { \
*temp3++ = *scan; /* copies operator */ \
temp3=comp_time(function,temp3,2); /*tries to simplify expression*/ \
return temp3; /* expression has been translated */ \
} else return NULL; /* something is wrong with the operands */ \
}
#define ERROR_MEM { \
i_error=NULL; \
return NULL; \
/* out of memory */ \
}
static UCHAR *i_trans(UCHAR *function, CHAR *begin, CHAR *end)
/* the source is *begin .. *(end-1) */
/* returns NULL if an error occured; otherwise, returns a
pointer to the first character after the end of function[] */
/* i_trans() does not write a '\0' at the end of function[], */
/* but it MAY touch its end (i.e. *i_trans) without changing it.*/
{
int pars; /* parentheses */
CHAR *scan;
UCHAR *tempu, *temp3;
CHAR *temps;
CHAR tempch;
double tempd;
CHAR *endf; /* points to the opening
parenthesis of a function (e.g. of sin(x) ) */
int n_function;
int space;
int i;
CHAR *paramstr[MAXPAR];
CHAR *par_buf;
if(begin>=end) {
i_error = begin;
return NULL;
}
DBG(tempch = *end);
DBG(*end = '\0');
DBG(puts(begin));
DBG(*end = tempch);
/* test paired parentheses */
for(pars=0, scan=begin; scan<end && pars>=0; scan++) {
if(*scan == '(') pars++;
else if(*scan == ')') pars--;
}
if(pars<0 || pars>0) {
i_error = scan-1;
return NULL;
}
/* plus and binary minus */
for(pars=0, scan=end-1; scan>=begin; scan--) {
if(*scan == '(') pars++;
else if(*scan == ')') pars--;
else if(!pars && (*scan == '+' || ((*scan == '-') && scan!=begin))
/* recognizes unary
minuses */
&& (scan==begin || *(scan-1)!='E') )
/* be wary of misunderstanding exponential notation */
break;
}
if(scan >= begin) TWO_OP
/* multiply and divide */
for(pars=0, scan=end-1; scan>=begin; scan--) {
if(*scan == '(') pars++;
else if(*scan == ')') pars--;
else if(!pars && (*scan == '*' || *scan == '/' ))
break;
}
if(scan >= begin) TWO_OP
/* power */
for(pars=0, scan=end-1; scan>=begin; scan--) {
if(*scan == '(') pars++;
else if(*scan == ')') pars--;
else if(!pars && (*scan == '^'))
break;
}
if(scan >= begin) TWO_OP
/* unary minus */
if(*begin == '-') {
if(tempu=i_trans(function,begin+1,end)) {
*tempu++ = 'M';
tempu=comp_time(function,tempu,1); /*tries to simplify
expression*/
return tempu;
} else return NULL;
}
/* erase white space */
while(isspace(*begin))
begin++;
while(isspace(*(end-1)))
end--;
/* parentheses around the expression */
if(*begin == '(' && *(end-1) == ')')
return i_trans(function,begin+1,end-1);
/* variable */
if(end == begin+1 && islower(*begin)) {
*function++ = 'V';
*function++ = *begin;
return function;
}
/* number */
tempch = *end;
*end = '\0';
tempd=strtod(begin,(CHAR**) &tempu);
*end = tempch;
if((CHAR*) tempu == end) {
*function++ = 'D';
*((double *)function)++ = tempd;
return function;
}
/*function*/
if(!isalpha(*begin) && *begin != '_')
/* underscores are allowed */
{
i_error=begin;
return NULL;
}
for(endf = begin+1; endf<end && (isalnum(*endf) || *endf=='_');
endf++);
tempch = *endf;
*endf = '\0';
if((n_function=where_table(begin)) == -1) {
*endf = tempch;
i_error=begin;
return NULL;
}
*endf = tempch;
if(*endf != '(' || *(end-1) != ')') {
i_error=endf;
return NULL;
}
if(ftable[n_function].n_pars==0) {
/*function without parameters (e.g. pi() ) */
space=1;
for(scan=endf+1; scan<(end-1); scan++)
if(!isspace(*scan)) space=0;
if(space) {
*function++ = 'F';
*function++ = n_function;
function = comp_time(function-2,function,0);
return function;
} else {
i_error=endf+1;
return NULL;
}
} else { /*function with parameters*/
tempch = *(end-1);
*(end-1) = '\0';
par_buf = (CHAR *) malloc(strlen(endf+1)+1);
if(!par_buf)
ERROR_MEM;
strcpy(par_buf, endf+1);
*(end-1) = tempch;
/* look at the first parameter */
for(i=0; i<ftable[n_function].n_pars; i++) {
if( ( temps=my_strtok((i==0) ? par_buf : NULL) ) == NULL )
break; /* too few parameters */
paramstr[i]=temps;
}
if(temps==NULL) {
/* too few parameters */
free(par_buf);
i_error=end-2;
return NULL;
}
if((temps=my_strtok(NULL))!=NULL) {
/* too many parameters */
free(par_buf);
i_error=(temps-par_buf)+(endf+1); /* points to the first character
of the first superfluous
parameter */
return NULL;
}
tempu=function;
for(i=0; i<ftable[n_function].n_pars; i++)
if(!(tempu=i_trans( tempu, paramstr[i],
paramstr[i]+strlen(paramstr[i]) ) ) )
{
i_error=(i_error-par_buf)+(endf+1); /* moves i_error to
the permanent copy of the
parameter */
free(par_buf);
return NULL; /* error in one of the parameters */
}
/* OK */
free(par_buf);
*tempu++ = 'F';
*tempu++ = n_function;
tempu = comp_time(function,tempu,ftable[n_function].n_pars);
return tempu;
}
}
static double pi(void)
{
return 3.14159265358979323846264;
}