May 1997 Programmer's Challenge

Equation Evaluator

Those of you with PowerPCs have probably experimented with the Graphing Calculator application installed by default into the Apple Menu Items folder. As one of the first native applications for PowerPC, the ability of the Graphing Calculator to display and even animate 2-dimensional and 3-dimensional equations demonstrated the computing power of the PowerPC chip using native code. Underlying the display capability is code to parse an equation and rapidly compute the equation value for a range of input values. In this month's Challenge, you will produce code to perform these parsing and computation functions.

The prototype for the code you should write is: typedef unsigned long ulong;

typedef struct Values {

float first; /* first equation input value */

float delta; /* first+delta is second input value */

ulong howMany; /* number of input values */

} Values;

typedef struct IntValues {

long first; /* first equation input value */

long delta; /* first+delta is second input value */

ulong howMany; /* number of input values */

} IntValues;

typedef struct Results {

float equationResult; /* result of equation given x,y,n */

float x; /* input value of x producing equationResult */

float y; /* input value of y producing equationResult */

long n; /* input value of n producing equationResult */

} Results;

void Evaluate(

char *equation, /* null-terminated equation to evaluate */

const Values *xP, /* equation input values for x */

const Values *yP, /* equation input values for y */

const IntValues *nP,/* equation input values for n */

Results w[] /* preallocated storage for equation values */

);

The input equation you are to evaluate will be provided as a null-terminated string in the 2-dimensional curve form (y=x+2x^2) or the 3-dimensional surface form (z=r cos(t) r sin(t)). You are to evaluate the equation for each of the values of x and n (in the case of a 2-dimensional equation) or x, y, and n (in the 3-dimensional case) provided and return the results in the preallocated array w. Each input is described as an initial value, a delta between each value and the next value, and the number howMany of values this input parameter is to assume. For example, if x is to take on the range of values [1.0, 1.1, 1.2, ... 2.0], then the x input could be described as:

In the event that the equation does not contain one of the input parameters, that parameter should be ignored. There is no guarantee, for example, that nP->howMany will be zero when the input equation is not a function of n. Similarly, for a 2-dimensional equation, yP should be ignored.

The input equation might be written as a function of r and [theta], which should be calculated from x and y just as the Graphing Calculator does.

Because the Graphing Calculator displays equations in ways that cannot be directly represented in a character string, the following symbols will be used in the equation to represent the operator or value indicated:

Standard algebraic operator precedence should be used: exponentiation and square roots, then multiplication and division, then addition and subtraction, with left-to-right evaluation order for operators of equal precedence, and with parentheses used to override normal precedence. Arguments to trigonometric functions will always be surrounded by parentheses. Where the Graphing Calculator would use superscripts to indicate an extended exponent, parentheses will be used to make the meaning clear (e.g., e^(x+y)).

Store the equation result for the i-th combination of input values in w[i]->equationResult, and store the corresponding input values in w[i]->x, w[i]->y, and w[i]->n. The results may be stored in any order, but each input combination should appear exactly once. Results should be calculated with a minimum relative accuracy of .00001.

Even though the Graphing Calculator handles inequalities, multiple equations, differentiation, simplification, and expansion, your code does not need to deal with these cases. With these exceptions, your code should handle any equation that the Graphing Calculator can handle.

You may allocate any amount of dynamic storage up to 20MB, provided you deallocate the storage before returning. This will be a native PowerPC Challenge, using the CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. Limited use of assembly language is also permitted, for anyone who might need it to access any dynamically generated code as part of their solution. The solution computing the correct results in the least amount of time will be the winner.