/* Solve
This file contains the code to parse a string into an expression tree and
for evaluating an expression tree.
Copyright (C) 1990 Marty White
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#include <stdio.h>
#include <math.h>
#include "compiler.h"
#ifdef __STDHEADERS__
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#endif
#include "physcalc.h"
#include "physdecl.h"
#ifdef __PROTOTYPES__
LOCAL NODEP parse_number(char const **s),
parse_paren(char const **s),
parse_alpha(char const **s),
parse_val(char const **s),
eval_var(char const *v),
eval_func(NODEP n),
eval_op(NODEP n);
LOCAL int parse_op(char const **s),
prefixop(char const *s),
digitvalue(char c);
LOCAL void replace_var(char const *old, NODEP new, NODEP n);
#endif
#define MAXSTACK 8 /* used only in parse() */
/* ----- Functions for parsing an expression ----- */
EXPORT int defaultbase=10;
LOCAL int digitvalue(c)
char c;
{ /* returns the numeric value of a digit. Works for any base from
1 through 36. Returns -1 if not a digit in base 36. */
c = toupper(c);
if (c >= '0' && c <= '9')
return c - '0';
if (c >= 'A' && c <= 'Z')
return c - 'A' + 10;
return 'Z'+1;
}
/* This procedure returns a node, 4 possible types */
LOCAL NODEP parse_number(s)
char const **s; /* evaluate number, advance ptr to end of number */
{ /* number may be one of the following:
decimal integer 0d123
decimal float 0d456.789e10
decimal fraction 0d1\3
hex integer 0x4F
hex float 0x4F.B6E3 (e notation unavailable in hex)
hex fraction 0x3\F6
binary integer 0b10110
binary float 0b1010.1011e1001
binary fraction 0b1011\11111
e notation is always optional.
The prefix 0<n> is required if the number is not in the
defualt base.
*/
NODEP n;
DNUM dm;
int p, sign, i, type, numerator, denominator, base=defaultbase;
double x,y;
char const *c;
#define isvaliddigit(c) (digitvalue(c) < base)
type = INODE; /* Start by assuming it's an integer */
/* any type may have a unit specifier, which forces a double */
c=*s;
x = 0.0; /* x is our working number */
sign = 1;
if (*c == '+') /* evaluate leading sign if any */
c++;
else
if (*c == '-') {
sign = (-1);
c++;
}
while (isspace(*c))
c++;
/* check for non-decimal bases */
if (*c=='0') {
c++;
switch (toupper(*c)) {
case 'X':
base = 16;
c++;
break;
case 'B':
base = 2;
c++;
break;
case 'D':
base = 10;
c++;
break;
}
}
/* Use a double for this part in case we have too many digits */
while (isvaliddigit(*c)) { /* evaluate integer part (if any) */
x = x * base + digitvalue(*c);
c++;
}
if (*c == '\\') { /* Evaluate a fraction */
/* the backslash is used to indicate fractional division */
type = FNODE;
numerator = (int) x;
c++;
denominator = 0;
while (isvaliddigit(*c)) {
denominator = denominator * base + digitvalue(*c);
c++;
}
if (*c=='\\') { /* handle improper fractions */
c++;
i = 0;
while (isvaliddigit(*c)) {
i = i * base + digitvalue(*c);
c++;
}
/* Switch from numerator\denominator\i to numerator\denominator */
/* Bug was: numerator += denominator * i; */
numerator = numerator * i + denominator;
denominator = i;
}
if (!denominator) { /* Can't have 0 for denominator!! */
error = MTHERR;
return NULL;
}
x = (double) numerator / (double) denominator;
} else { /* not a fraction */
if (*c == '.') { /* Evaluate decimal part (if any) */
type = DNODE;
y = 0.1;
while (isvaliddigit(*++c)) {
x += y * digitvalue(*c);
y /= (double) base;
}
}
if (toupper(*c)=='E') { /* evaluate scientific notation, if any */
type = DNODE;
i = 0;
p = 1;
if (*++c=='+')
c++;
else
if (*c=='-') {
p = -1;
c++;
}
while (isvaliddigit(*c)) {
i = i * base + digitvalue(*c);
c++;
}
x *= pow((double) base, (double)(i * p));
}
}
x *= sign;
numerator *= sign;
skipspc(c);
*s = c; /* update pointer */
erasednum(&dm);
dm.num = x;
evaldim(s,1,&dm); /* evaluate unit specifiers if any */
if (*s != c) { /* units were evaluated */
n = allocnnode();
copydnum((DNUM *)(n->data), &dm);
} else
switch (type) {
case DNODE:
n = allocdnode(x);
break;
case INODE:
n = allocinode((long) x);
break;
case FNODE:
n = allocfnode(numerator,denominator);
simplify_frt(n);
break;
}
#ifdef TRACE
if (trace) {
printf("Number parsed: ");
printexpr(n);
printf("\n");
}
#endif
return n; /* return value */
}
LOCAL NODEP parse_paren(s)
/* use recursion to parse parenthetic sub-expressions */
char const **s;
{
NODEP n;
(*s)++;
n = parse(s);
if (**s!=')')
error = PARERR;
else
(*s)++;
return n;
}
LOCAL NODEP parse_alpha(s) /* parse a symbolic value (var or function) */
char const **s;
{
NODEP n,n2;
char buf[NAMELEN];
scan_symbol(s,buf);
strupr(buf);
skipspc(*s);
if (**s!='(') /* if not followed by a paren, */
return allocsnode(buf); /* return a variable node */
#ifdef TRACE
if (trace)
printf("Parsing function: '%s'\n",buf); /* Parse a function call */
#endif
n = alloclnode(LNODE); /* allocate a function-list node */
n2 = allocsnode(buf); /* first sub-node is the function name */
linknode(n,n2);
do { /* Succeding nodes are parameters */
(*s)++;
n2 = parse(s);
if (error) {
deallocnode(n);
deallocnode(n2);
return NULL;
}
linknode(n,n2);
skipspc(*s);
#ifdef TRACE
if (trace) {
printf("Parameter parsed: ");
printexpr(n2);
printf("\n");
}
#endif
} while (**s==',');
if (**s != ')') {
error = PARERR;
deallocnode(n);
return NULL;
}
(*s)++;
return n;
}
LOCAL NODEP parse_val(s) /* parse a value (as opposed to an operator) */
char const **s;
{
skipspc(*s);
if ( isalpha(**s) )
return parse_alpha(s);
if (**s == '(')
return parse_paren(s);
return parse_number(s);
}
LOCAL int parse_op(s) /* Return index of operator if there is one (0=NULL) */
char const **s;
{
int i,len;
skipspc(*s);
for (i=1; i < OPS; i++) { /* scan list for op */
len = strlen( operator[i] );
if ( !strncmp(*s,operator[i],len) ) {
*s += len;
return (i);
}
}
return 0; /* unrecognized op (could be ')') */
}
LOCAL int prefixop(s) /* Return index op prefix-operator if there is one */
char const *s;
{
int i;
for (i=1; i<OPS; i++)
if (optype[i]==2 && !strncmp(s,operator[i],strlen(operator[i])))
return i;
return 0;
}
EXPORT NODEP parse(s) /* Parse a string-expression into a node-expression */
char const **s; /* Handle to string being parsed */
{
int op_stack[MAXSTACK],*opstack,op; /* Stack for operands */
NODEP num_stack[MAXSTACK],*numstack,n,n2; /* Stack for expressions */
#ifdef TRACE
if (trace) printf("Parsing: '%s'\n",*s);
#endif
opstack = op_stack;
numstack = num_stack;
*numstack = NULL;
*opstack = 0;
error = 0;
while (TRUE) {
skipspc(*s);
if (op = prefixop(*s)) {
*++opstack = op;
(*s) += strlen(operator[op]);
continue;
}
n = parse_val(s); /* evaluate operand */
if (error)
return n;
while (TRUE){
op = parse_op(s); /* evaluate operator (if any) */
while ( priority[op] <= priority[*opstack] ) {
if ( (priority[op] == priority[*opstack]) && (priority[op]==0) )
return n;
/* Create an operator node */
if (optype[*opstack]==2) { /* It's a prefix operator */
n2 = alloclnode(LNODE + *opstack);
linknode(n2,n);
if (number(n)) {
n = evaluate(n2);
deallocnode(n2);
if (error)
return n;
} else
n = n2;
} else { /* It's a binary operator */
n2 = alloclnode(LNODE + *opstack);
linknode(n2,*numstack);
linknode(n2,n);
if (number(n) && number(*numstack)) {
n = evaluate(n2);
deallocnode(n2);
if (error)
return n;
} else
n = n2;
numstack--;
}
opstack--; /* pull number and operand off stack */
}
if (optype[op]==3) { /* It's a postfix operator */
n2 = alloclnode(LNODE + op);
linknode(n2,n);
if (number(n)) {
n = evaluate(n2);
deallocnode(n2);
if (error)
return n;
} else
n = n2;
} else { /* It's a binary infix, so save for later */
*++opstack = op; /* Push number & operand on stack */
*++numstack = n;
break;
}
} /* outer loops are infinite */
}
return n; /* Code never reached, but some compilers insist */
}
/*------- These are the node-evaluating procedures -------*/
LOCAL NODEP eval_var(v) /* Perform variable substitution */
char const *v;
{
NODEP n;
struct varstruct *vp;
#ifdef TRACE
if (trace) printf("Evaluating variable '%s'.\n",v);
#endif
vp = var;
do { /* Search list for a matching available var */
if (!strcmp(v,vp->name) && !vp->rflag) {
error = 0;
vp->rflag = TRUE; /* set flag to prevent infinite recursion */
n = evaluate(vp->value); /* evaluate the associated expression */
vp->rflag = FALSE;
if (!error)
return n;
deallocnode(n);
}
} while (vp = vp->next);
/* if (!error)
error = UVRERR; */
return allocsnode(v);
}
LOCAL void replace_var(old,new,n)
/* used only by eval_func(), but is generic */
char const *old;
NODEP new,n;
{ /* Replace every occurence of (old) in (n) with a copy of (new) */
int i=0;
switch (n->type) {
case SNODE: /* Compare string with (old) */
if (!strcmp(old,n->data->str)) { /* Replace with (new) */
reallocnode(n,new->type,i=nodesize(new));
if (new->type < LNODE) {
bytecopy(n->data,new->data,i);
} else { /* Replace with sub nodes */
i = 0;
while (new->data->list[i]) {
n->data->list[i] = copynode(new->data->list[i]);
i++;
}
}
}
case 0 /*NULL*/: /* fall thru to break */
case INODE:
case FNODE:
case DNODE:
case NNODE:
break;
case LNODE: /* function node */
i++;
default: /* list (operator) node */
while (n->data->list[i])
replace_var(old,new,n->data->list[i++]);
}
}
LOCAL NODEP eval_func(n)
NODEP n;
{
NODEP n2,n3;
int i,j,flag;
double x;
char *t;
struct ufstruct *u;
struct dimstruct *d;
/* Find matching function name & evaluate given parameter. Make a copy of the
function expression. Replace each occurence of the dummy var with a copy of
the evaluated parameter, then evaluate the whole expression & return it. */
t = n->data->list[0]->data->str; /* t points to func name */
#ifdef TRACE
if (trace) printf("Evaluating function '%s'.\n",t);
#endif
u = userfunc;
while (u) { /* Scan user-defined functions */
if (!strcmp(t,u->name)) {
n3 = copynode(u->value);
j = 1;
do {
n2 = evaluate(n->data->list[j]);
#ifdef TRACE
if (trace) {
printf("Parameter %d evaluated to: ",j);
printexpr(n2);
printf("\n");
}
#endif
replace_var(u->dummy->data->list[j-1]->data->str,n2,n3);
deallocnode(n2);
j++;
} while (n->data->list[j]);
n2 = evaluate(n3); /* evaluate function */
deallocnode(n3);
return n2;
}
u = u->next;
}
/* A user function was not found, so use a built in function */
for (i=0; i<FUNCS2; i++)
if (!strcmp(t,functions2[i])) {
if (!n->data->list[1])
return NULL;
n2 = (*do_funct2[i])(n->data->list[1],n->data->list[2],n->data->list[3],n->data->list[4]);
/* not all of the above parameters neccessarily exist */
return n2;
}
/* This section assumes that the default unit of ANGLE is RADIAN,
the same measure as is used by the C trig functions */
for (i=0; i<FUNCS; i++) /* Scan built in functions */
if ( !strcmp(t,functions[i]) ) { /* if matches, call function */
n2 = evaluate(n->data->list[1]); /* evaluate parameter */
switch (n2->type) {
case INODE:
x = (double) n2->data->lng;
break;
case FNODE:
x = (double) n2->data->frt.numer / (double) n2->data->frt.denom;
break;
case DNODE:
x = n2->data->dbl;
break;
case NNODE:
if (!strcmp(t,"SQRT")) { /* special handling for sqrt */
n3 = allocnnode();
n3->data->dmn.num = sqrt(n2->data->dmn.num);
flag = FALSE;
for (j=0; j<MAXDIM; j++) {
n3->data->dmn.di[j] = n2->data->dmn.di[j] / 2;
if (n3->data->dmn.di[j] * 2 != n2->data->dmn.di[j]) {
// Unable to take square root of this dimensioned quantity.
flag = TRUE;
}
}
if (flag)
printf("Performing %s on dimensioned number: Dimension invalid.\n",t);
deallocnode(n2);
return n3;
}
x = n2->data->dmn.num;
if (i>=3 && i<=5) { /* if trig function, accept angle unit */
flag = TRUE;
d = dimension_list;
do {
if (strcmp(d->name,"ANGLE") == 0) {
for (j=0; j<MAXDIM; ++j)
if (n2->data->dmn.di[j] != d->dimension[j]) {
flag = FALSE; /* Not an angle unit */
break;
}
break;
}
} while (d = d->next);
if (flag) { /* if an angle, set x & exit switch */
x = n2->data->dmn.num;
break;
}
} /* Otherwise, fall thru and notify user of loss of units */
printf("Performing %s on dimensioned number: Dimension lost.\n",t);
break;
default: /* not a constant */
deallocnode(n2);
return copynode(n);
}
if (i>=6 && i<=8) { /* if arc-trig funct, return an angle */
n3 = allocnnode();
erasednum((DNUM *)(n3->data));
d = dimension_list;
j = 0;
do {
if (!strcmp(d->name,"ANGLE")) {
n3->data->dmn.di[j] = 1;
break;
}
j++;
} while (d = d->next);
n3->data->dmn.num = (*do_funct[i])(x);
} else
n3 = allocdnode( (*do_funct[i])(x) );
deallocnode(n2);
if (error)
error = MTHERR;
return n3;
}
error = UFNERR;
return NULL;
}
LOCAL NODEP eval_op(n) /* Carry out an operator */
NODEP n;
{
NODEP n2,n3,n4;
n2 = evaluate(n->data->list[0]);
if (error) {
deallocnode(n2);
return NULL;
}
if (optype[n->type - LNODE]==1) { /* Do binary op */
n3 = evaluate(n->data->list[1]);
if (error) {
deallocnode(n2);
deallocnode(n3);
return NULL;
}
if (!number(n2) || !number(n3)) {
n4 = alloclnode(n->type);
linknode(n4,n2);
linknode(n4,n3);
return n4;
}
if (n->type - LNODE != 5) /* operands must be same type, */
force_same_type(n2,n3); /* except for power (op #5) */
if (error) {
deallocnode(n2);
deallocnode(n3);
error = TYPERR;
return NULL;
}
n4 = (*do_op[n->type - LNODE])(n2,n3);
deallocnode(n2);
deallocnode(n3);
return n4;
} else { /* Do pre- or post- fix operator */
if (!number(n2)) {
n3 = alloclnode(n->type);
linknode(n3,n2);
return n3;
}
n3 = (*do_op[n->type - LNODE])(n2);
deallocnode(n2);
return n3;
}
}
EXPORT NODEP evaluate(n) /* Evaluate expression tree in node n */
NODEP n;
{ /* Return a node containing the resulting value. Unknown variables
are left in symbolic form */
NODEP n2;
#ifdef TRACE
if (trace && !number(n)) {
printf("Evaluating: ");
printexpr(n);
printf("\n");
}
#endif
switch (n->type) {
case 0 /*NULL*/:
n2 = NULL;
break;
case SNODE:
n2 = eval_var(n->data->str);
break;
case INODE:
case DNODE:
case FNODE:
case NNODE:
n2 = copynode(n);
break;
case LNODE:
n2 = eval_func(n);
break;
default: /* Is a list node */
n2 = eval_op(n);
#ifdef TRACE
if (trace) {
printf("Result: ");
printexpr(n2);
printf("\n");
}
#endif
break;
}
if (n2 && n2->type==FNODE)
simplify_frt(n2);
return n2;
}
LOCAL int frt_format = FALSE; /* FALSE = improper, TRUE = mixed */
EXPORT void fprintexpr(fp,n) /* print contents of node n */
FILE *fp;
NODEP n;
{
char buf[SMALLBUF];
int i=1;
if (!n) {
fprintf(fp,"<NULL> ");
return;
}
switch (n->type) {
case SNODE:
fprintf(fp,"%s",n->data->str);
break;
case INODE:
/* fprintf(fp,"%ld",n->data->lng); */
/*ltoa(n->data->lng, buf, defaultbase);
*/
sprintf(buf, "%ld", n->data->lng);
switch (defaultbase) {
case 2:
fprintf(fp, "0b");
case 10:
break;
case 16:
fprintf(fp, "0x");
break;
default:
fprintf(fp, "(base %d) ", defaultbase);
break;
}
fprintf(fp, "%s", buf);
break;
case FNODE:
if (frt_format)
fprintf(fp,"%d\\%d\\%d",n->data->frt.numer / n->data->frt.denom,
n->data->frt.numer % n->data->frt.denom,
n->data->frt.denom);
else
fprintf(fp,"%d\\%d",n->data->frt.numer,n->data->frt.denom);
break;
case DNODE:
fprintf(fp,"%lg",n->data->dbl);
break;
case NNODE:
generate_unit(&n->data->dmn,buf);
fprintf(fp,"%lg %s",n->data->dmn.num,buf);
break;
case LNODE: /* function */
fprintf(fp,"%s(",n->data->list[0]->data->str);
while (n->data->list[i]) {
fprintexpr(fp,n->data->list[i]);
i++;
if (n->data->list[i])
fprintf(fp,",");
}
fprintf(fp,")");
break;
default: /* Operator */
fprintf(fp,"(");
switch (optype[n->type - LNODE]) {
case 1: /* Binary */
fprintexpr(fp,n->data->list[0]);
fprintf(fp," %s ",operator[n->type - LNODE]);
fprintexpr(fp,n->data->list[1]);
break;
case 2: /* Prefix */
fprintf(fp,"%s ",operator[n->type - LNODE]);
fprintexpr(fp,n->data->list[0]);
break;
case 3: /* Postfix */
fprintexpr(fp,n->data->list[1]);
fprintf(fp," %s",operator[n->type - LNODE]);
break;
}
fprintf(fp,")");
}
}
EXPORT void printexpr(n)
NODEP n;
{
fprintexpr(stdout,n);
}
EXPORT void fraction_cmd(s) /* set fraction output mode */
const char *s;
{
int f= -1;
if (!strcmp(s,"IMPROPER"))
f = 0;
if (!strcmp(s,"MIXED"))
f = 1;
if (f>=0) {
printf("Fractions will be displayed in %s format.\n",
f ? "mixed" : "improper" );
frt_format = f;
} else
printf("Usage: FRACTION IMPROPER or FRACTION MIXED\n");
}
syntax highlighted by Code2HTML, v. 0.9.1