 |
Formula Translation |  |
 |
This article has been rewritten.
Also, the full Delphi project with source code and
an excerciser program are made available.
Click here
Introduction
This article describes the translation of a mathematical formula into a sequence of basic operations.
The method was developed for Graphics-Explorer, a versatile program to investigate
various types of functions and equations.
(Click here to see specifications or to download Graphics-Explorer)
Graphics-Explorer may handle up to 9 different equations of 4 different types simultaniously:
| type | example | |
| 1 | function | y = 3sin(2x) |
| 2 | inverse function | x = 5cos(y) - 2sin(3y) |
| 3 | parametric function | y = 3sin(2v) ; x = 5cos(7v) |
| 4 | implicit function | x^2 + y^2 = 81 |
The same translation proces is used for all types of equations.
The final result of the translation is the 'director-table', a list of
basic calculations in the order of their priority.
In the following description, the formula y = 3.2 + 1.6(x-0.5) + 0.22x^2
will be translated.
Multiply operator insertion
Before the translation starts, the multiply operator '*' is inserted where needed.
This changes the formula to y = 3.2 + 1.6*(x-0.5) + 0.22*x^2
Also, any blank characters are removed.
Priority
Because of different priorities of the operators + * ^, the value of y cannot be
calculated simply in the 'left to right' sequence.
The priority of an operation is the sum of two values:
1. the biaspriority:
-
initially, this value is 0. Occurrence of '(' in the formula string increases the
biaspriority by 10, where occurrence of ')' decreases this priority by 10.
| 7 | function (sin, cos, tan, root, etc.) |
| 6 | ^ power |
| 5 | unairy - as in -17.5 or -sin(2x) |
| 4 | * / , multiplication and division |
| 3 | + - , addition and subtraction |
| 2 | = |
| 1 | ; the separator of parametric functions |
| 0 | end of table |
Constants and variables
In the formula above, constants 3.2 , 1.6 , 0.5 and 0.22 are noticed as well as variables x and y.
These values are stored in an array called Freg[1..250] (floating point registers) as follows:
| Freg | contains |
|---|---|
| [1..19] | intermediate results |
| [20..39] | constants formula 1 |
| [40..59] | constants formula 2 |
| [60..199] | constants formulas 3..9 |
| [200] | x |
| [201] | y |
| [202] | v | [203] | A | [204] | B | [205] | C | [206] | pi 3.14159... | [207] | e 2.71828... | [210..212] | formula 1: A,B,C after substitution | [213..215] | formula 2: same as above | [216..236] | formulas 3..9: same as above |
After scanning above formula (as number 1), Freg will look like:
| Freg | value |
|---|---|
| 20 | 3.2 |
| 21 | 1.6 |
| 22 | 0.5 |
| 23 | 0.22 |
| 24 | 2 |
The constants are stored in the sequence of their occurrence.
The Director table
This table is the final result of the translation.
Each row describes a basic arithmetic operation or function and has the form:
-
operation....destination....source1....source2
| operation | destination | source1 | source2 | |
|---|---|---|---|---|
| 1 | - | 1 | x | 22 |
| 2 | ^ | 2 | x | 24 |
| 3 | * | 1 | 21 | 1 |
| 4 | * | 2 | 23 | 2 |
| 5 | + | 1 | 20 | 1 |
| 6 | + | 1 | 1 | 2 |
| 7 | = | y | none | 1 |
For clarity, x and y are printed instead of 200 and 201.
Also, operators +,-,*,^ are printed instead of the numeric code, indicating that operator.
The meaning of row 1 is:
-
subtract contents of Freg[22] from x (Freg[200]) and place this difference in Freg[1].
of the director table from top to bottom.
After executing row 7, the final result is hold by Freg[201] (y).
The Priority Table
This table is an intermediate during formula-string to Director Table translation.
A row of the priority table has the form:
-
constant or variable ....operation or function.....priority
| constant or variable | operation | priority | |
|---|---|---|---|
| 1 | y | = | 2 |
| 2 | 20 | + | 3 |
| 3 | 21 | * | 4 |
| 4 | x | - | 13 |
| 5 | 22 | + | 3 |
| 6 | 23 | * | 4 |
| 7 | x | ^ | 6 |
| 8 | 24 | end | 0 |
The first 2 colums, red row by row, resemble the formula string with constants
and variables replaced by their reference to the Freg[] array.
The third column indicates the priority of the operation and is the addition of operator- and bias priority.
Notice, that row 4 has the priority 13, not 3, because a '(' parenthesis has been passed.
The translation
The Director Table is built while eliminating the Priority Table row by
row, always taking the operation with the highest priority first.
| constant or variable | operation | priority | |
|---|---|---|---|
| 1 | y | = | 2 |
| 2 | 20 | + | 3 |
| 3 | 21 | * | 4 |
| 4 | x | - | 13 |
| 5 | 22 | + | 3 |
| 6 | 23 | * | 4 |
| 7 | x | ^ | 6 |
| 8 | 24 | end | 0 |
| operation | destination | source1 | source2 | |
|---|---|---|---|---|
| 1 | - | 1 | x | 22 |
The operation of row 4 is removed from the priority table and added to the director table.
Since registers x and 22 may not be modified, the first register for intermediate results, 1, receives the difference.
Now, row 6 has the highest priority.
| constant or variable | operation | priority | |
|---|---|---|---|
| 1 | y | = | 2 |
| 2 | 20 | + | 3 |
| 3 | 21 | * | 4 |
| 4 | 1 | + | 3 |
| 5 | 23 | * | 4 |
| 6 | x | ^ | 6 |
| 7 | 24 | end | 0 |
| operation | destination | source1 | source2 | |
|---|---|---|---|---|
| 1 | - | 1 | x | 22 |
| 2 | ^ | 2 | x | 24 |
The result is stored in register 2, the next available register for intermediate results.
| constant or variable | operation | priority | |
|---|---|---|---|
| 1 | y | = | 2 |
| 2 | 20 | + | 3 |
| 3 | 21 | * | 4 |
| 4 | 1 | + | 3 |
| 5 | 23 | * | 4 |
| 6 | 2 | end | 0 |
| operation | destination | source1 | source2 | |
|---|---|---|---|---|
| 1 | - | 1 | x | 22 |
| 2 | ^ | 2 | x | 24 |
| 3 | * | 1 | 21 | 1 |
Register 1 is overwritten, not to waste registers 1..19 continuing the process:
| constant or variable | operation | priority | |
|---|---|---|---|
| 1 | y | = | 2 |
| 2 | 20 | + | 3 |
| 3 | 1 | + | 3 |
| 4 | 23 | * | 4 |
| 5 | 2 | end | 0 |
| operation | destination | source1 | source2 | |
|---|---|---|---|---|
| 1 | - | 1 | x | 22 |
| 2 | ^ | 2 | x | 24 |
| 3 | * | 1 | 21 | 1 |
| 4 | * | 2 | 23 | 2 |
Continuing:
| constant or variable | operation | priority | |
|---|---|---|---|
| 1 | y | = | 2 |
| 2 | 20 | + | 3 |
| 3 | 1 | + | 3 |
| 4 | 2 | end | 0 |
| operation | destination | source1 | source2 | |
|---|---|---|---|---|
| 1 | - | 1 | x | 22 |
| 2 | ^ | 2 | x | 24 |
| 3 | * | 1 | 21 | 1 |
| 4 | * | 2 | 23 | 2 |
| 5 | + | 1 | 20 | 1 |
And after the next step:
| constant or variable | operation | priority | |
|---|---|---|---|
| 1 | y | = | 2 |
| 2 | 1 | + | 3 |
| 3 | 2 | end | 0 |
| operation | destination | source1 | source2 | |
|---|---|---|---|---|
| 1 | - | 1 | x | 22 |
| 2 | ^ | 2 | x | 24 |
| 3 | * | 1 | 21 | 1 |
| 4 | * | 2 | 23 | 2 |
| 5 | + | 1 | 20 | 1 |
| 6 | + | 1 | 1 | 2 |
And after the last step:
| constant or variable | operation | priority | |
|---|---|---|---|
| 1 | y | = | 2 |
| 2 | 1 | end | 0 |
| operation | destination | source1 | source2 | |
|---|---|---|---|---|
| 1 | - | 1 | x | 22 |
| 2 | ^ | 2 | x | 24 |
| 3 | * | 1 | 21 | 1 |
| 4 | * | 2 | 23 | 2 |
| 5 | + | 1 | 20 | 1 |
| 6 | + | 1 | 1 | 2 |
| 7 | = | y | none | 1 |
This completes the translation.
Additional notes
Functions like sin, cos, abs are treated the same way as operators +,- etc. however the source1 operand is ignored.
The separator character ';' for parametric functions (type 3) is regarded as a dummy operator with lowest priority.
This prevents interaction between values of x and y.
The calculated values for x and y are available in Freg[200] and Freg[201] after processing the director table.
Intrinsic functions (type 4) treat the '=' operator as a '-' operator.
An intrinsic function f(x) = g(x) is transformed to v = f(x) - g(x).
A dot (x,y) is plotted if v = 0. If v changes sign, the dot (x,y) with the lowest absolute value is plotted.
Graphics-Explorer contains debug code for examining the tables.
This code is activated/deactivated by typing
The unairy '-' operator is shown as (-).
David E. Dirkse, May 2004, the Netherlands
david@davdata.nl
