The routine that resulted from my efforts consists of two externally accessible functions and many static support functions. All these functions reside in a file entitled FUNCEVAL.C and is shown in Listing 1. The two externally accessible functions are called Convert and Evaluate. Convert transforms a string containing a mathematical equation in standard notation with two variables, X and Y, into another string that is in a notation that can be evaluated more quickly and efficiently. Evaluate accepts two double precision floating point numbers and returns the value of the equation upon substituting these two values for X and Y.
The function Convert is near the end of Listing 1. The parameter FunctionString is a pointer to a null-terminated string of unsigned characters. This string should contain a math equation in two variables, X and Y, and may contain any of several transcendental and other function calls such as SIN, LN, SQRT, etc. A complete list of acceptable function calls and mathematical operators is shown in Table 1. FunctionString should be in standard mathematical notation as the following equation illustrates.
-12.5 + SIN(X^2) / COS(LN(Y) + 2.2e-1)
FunctionString can contain any number of spaces and the alphabetic characters used for function and variable names can be in either upper or lower case. The first two support functions called by Convert, RemoveSpaces and strupr, remove all the spaces in the string and convert all lower case letters to upper case.
The next function called by Convert, CheckSyntax, examines the syntax of FunctionString. CheckSyntax can detect 12 different syntax errors such as illegal characters, misplaced operators, and missing parentheses. These errors are symbolically defined in the header file SYNTXERR.H shown in Listing 2. If an error is detected the externally accessible global variable SyntaxErr is equated with an appropriate error value and a pointer to the offending character in FunctionString is returned. If no error is found, SyntaxErr is set to FALSE and a zero is returned.
After FunctionString passes the syntax check, it is copied to another string, fstr. This allows the original form of the equation (with spaces removed and all alphabetic characters in upper case) to be preserved in FunctionString while modifications are made to the copy in fstr.
The first modification to fstr is performed by the support function ConvertConstants. This function initially scans fstr for unary pluses and minuses and places a zero in front of the sign. This action will make further processing of the string easier. Next, ConvertConstants scans fstr once again replacing all numeric constants with a one-byte symbol in the range 128 to 255 and placing the actual value of the constant in an array for future reference. The maximum number of constants allowed in the string is 128. If fstr contains more than 128 constants, SyntaxErr is set to TOOMANYCONSTS and FALSE is returned, otherwise TRUE is returned.
The next function called by Convert, ConvertFunctions, scans fstr and replaces all transcendental and other function names with a one-byte symbol in the range 1 to 13. These symbols are defined at the beginning of FUNCEVAL.C. No error checking is necessary in this function because illegal functions will have already been detected in CheckSyntax. Therefore, ConvertFunctions is a void function.
The last support function called by Convert, InfixToPostfix, converts fstr, which is still in standard mathematical notation (with constants and function names substituted with one-byte symbols), to a postfix or reverse polish notation. This is the notation used by the computer language Forth and by Hewlett-Packard calculators. InfixToPostfix is a relatively complex function that reads the string fstr character by character and, based upon the precedence of the operators, either places the character in the static global string NewExpr or places it on a stack for later processing. If during processing the stack underflows or overflows, SyntaxErr will be equated with STACKUNDERFLOW or STACKOVERFLOW and FALSE will be returned. When processing is complete, NewExpr will contain the mathematical equation in postfix notation and TRUE will be returned.
The Convert and ConvertConstants functions have several lines of code that will only be compiled if the symbol DEBUG is defined. These sections of code will print the equation at various points during its processing. Let's look at an example step by step. Suppose the function as it is originally entered by the user is as follows:
2.1E-1 + x*y - sin(-.8*X) / ln(+Y + 100)
The following steps will convert this function into symbolic form with postfix notation. The support function that accomplishes each step appears in parentheses.
STEP 1. Remove all spaces. (RemoveSpaces) 2.1E-1+x*y-sin(-.8*X)/ln(+Y+100) STEP 2. Convert lower case letters to upper case. (strupr) 2.1E-1+X*Y-SIN(-.8*X)/LN(+Y+100) STEP 3. Check syntax. If no errors are detected, processing will continue. No changes are made to the string. (CheckSyntax) STEP 4A. Put zeroes before unary pluses and minuses. (ConvertConstants) 2.1E-1+X*Y-SIN(0-.8*X)/LN(0+Y+100) STEP 4B. Replace constants with one-byte symbols in the range 128 to 255. Since these are non-printable characters, each character in the string will be printed below as a decimal value. The actual character or constant it represents appears beneath the decimal value. (ConvertConstants) 128 43 88 42 89 45 83 73 78 40 129 45 130 42 88 2.1E-1 + X * Y - S I N ( 0 - .8 * X 41 47 76 78 40 131 43 89 43 132 41 ) / L N ( 0 + Y + 100 ) STEP 5. Replace function names with one-byte symbols in the range 1 to 13. (ConvertFunctions) 128 43 88 42 89 45 1 40 129 45 130 42 88 41 2.1E-1 + X * Y - SIN ( 0 - .8 * X ) 47 12 40 131 43 89 43 132 41 / LN ( 0 + Y + 100 ) STEP 6. Convert the string to postfix notation. (InfixToPostfix) 128 88 89 42 43 129 130 88 42 45 1 131 89 43 2.1E-1 X Y * + 0 .8 X * - SIN 0 Y + 132 43 12 47 45 100 + LN / -
The final form of the equation in STEP 6 resides in the string NewExpr. A pointer to this string is returned by Convert.
The function Evaluate, at the end of Listing 1, can be used to evaluate the equation at different values of X and Y. Because the equation is now in postfix notation, Evaluate is a rather simple routine. It simply reads the characters in NewExpr sequentially; if a character represents X, Y, or a constant, its actual numerical value is pushed onto a stack. If a character represents a function, Evaluate will pass the number on the top of the stack along with the character symbol representing the function to the function Calculate. The result of applying this function to the number will be returned. For example, if the number equals 100 and the function is LOG, a value of 2 will be returned. This return value is then pushed onto the top of the stack.
If a character represents an operator (^, +, -, *, /), the top two numbers on the stack and the operator symbol are passed to Calculate. The result of performing the operation on the two numbers is returned. For example, if the number on top of the stack is 24, the next number on the stack is 12, and the operator is /, Calculate will return 12/24 or 0.5. Notice that the operation is always performed in the following order:
(Second number on stack) operator (Top number on stack)
The above procedure continues until no more characters remain to be read from NewExpr. At this point the value of the equation with the appropriate values of X and Y substituted will be on top of the stack. This value is returned by Evaluate. Please note that Evaluate does not check for illegal mathematical operations such as the square root of a negative number or a multiplication that causes an overflow. The method for handling these types of errors vary with different compilers. It is left up to the reader to add this form of error handling if it is needed.
A program entitled TESTFEVL.C is shown in Listing 3. This program tests the Convert and Evaluate functions. The user is allowed to input a mathematical equation (up to 255 characters long) along with values of X and Y; the program will print the result of evaluating the equation. Unfortunately, the scanf function (from the C library) does not allow spaces to be entered in a string (they are used for delimiters); therefore, you will not be able to see the RemoveSpaces function in action. (Note: If spaces are entered as part of the equation, the program will behave erratically as characters after the spaces are used as input for later scanf calls.) If you compile FUNCEVAL.C with DEBUG defined, each stage of the equation conversion will be printed to the standard output. You can play to your hearts content. Make sure you type in some equations that are syntactically incorrect to see how the error detection works. The equation will be printed, an up arrow will appear below the offending character, and an appropriate error message will be printed.
FUNCEVAL.C and TESTFEVL.C are written generically and have been successfully compiled, linked, and executed on an Amiga 1000 using Lattice C v4.01 and v5.02, on an IBM AT using Microsoft C v4.0, and on a Cray X-M/P supercomputer using the Cray C compiler (with one modification). If you are using an older C compiler some of the standard library functions used in this program may not be available.