Overview
evaluate.c is a piece of documented example code showing an interesting and quick algorithim for evaluating algebraic strings, such as "2 + 4" and "a=5; b=10; c=b-a; b*c". It is released under the GNU General Public License version 2 or later.
Purpose
Mainly so I can write a new calculus.library for the Amiga, but to be honest, I'd like programmers who write evaluators to take a look at it and maybe learn something. I've used many evaluators, and often there are terrible mistakes. My pet peeves are:
- Using a full regexp scanner and LALR parser!
- No operator precedence!
- Only evaluating with integer arithmetic.
- Having fixed number of variables or fixed variable name lengths.
- Having some arbitrary limit on the evaluation depth or number of tokens.
Usage
Call this function: int evaluate(char *expr, struct val *result, struct vartable *vartable);. Its arguments are:
- expr is string representing an expression to evaluate, for example "1+a" or "pi/2".
- result is a pointer to a structure that will contain the result of the evaluation - it contains both real and integer values, and a 'type' flag to say which one contains the actual value. The structure must exist in advance - for example, you could declare struct val result; in the variables of your program then use &result as the parameter.
- vartable can be NULL - if so, evaluate uses its own private variable table, but if not then this should be a pointer to a variable table as created with create_vartable() and freed with free_vartable(). The table itself can be edited with get_var() and put_var().
- The value returned by evaluate is an error code of some sort, or RESULT_OK to indicate that everything went well.
Read about how the code works!
To compile the example eval.c, try one of these:
- gcc -o eval eval.c evaluate.c -lm
- cc -o eval eval.c evaluate.c -lm
- vc -o eval eval.c evaluate.c -lmieee
- vc -sc -cpu=68020 -fpu=68881 -o eval eval.c evaluate.c -lm881
Expressions
In the demo program you can type in expressions and press return to have them evaluated. The rules regarding expressions are as follows:
You can follow any expression with a semicolon and another expression. The expression is a mixture of values, variables and operators, in infix notation. You can use parentheses (round brackets) to force a particular order. The operators are as follows:
| + | addition | << | bitwise shift left |
| - | subtraction (or negation) | >> | bitwise shift right |
| * | multiplication | && | logical and |
| / | division | || | logical or |
| ** | raise to the power | ! | logical not |
| % | modulus | == | equality test |
| = | assignment | != | inequality test |
| & | bitwise AND | < | less than test |
| | | bitwise OR | > | greater than test |
| ~ | bitwise NOT | <= | less than or equal to test |
| ^ | bitwise XOR | >= | greater than or equal to test |
The precedence of the operators is as follows, from highest (most tightly binding) to lowest:
- implicit multiplication
- !, ~, unary -
- **
- *, /, %
- +, -
- <<, >>
- <, >, <=, >=
- ==, !=
- &
- |, ^
- &&, ||
- =
- functions
The available functions are acos, asin, atan, cos, cosh, exp, ln, log, sin, sinh, sqr, sqrt, tan and tanh. All functions take one argument. You do not need to have parentheses round the argument.
Any text other than function is considered to be a variable reference. All variables have to be assigned before use (for example, "a=5; b=a-3; a+b"), or set as operating system environment variables.
The behaviour of operators and functions, and the accuracy of results is entirely down to the C compiler which compiles evaluate.c.