Dynamic Formula Processing Library

• Download dynamicformula_demo - 213.88 KB
• Download dynamicformula_library - 247.6 KB

Introduction

This library evaluates formulas in strings to a value, e.g. "2+4*6+2" returns 28.

Background

Infix

Simply put infix notation is the notation used by use mere mortals, e.g. 2+4*6+2. In infix notation the operator (e.g. + or *) is inside the operands (e.g. 2, 4, and 6). While this notation is simple for a human to understand it is not so convienient for processing, as the computer typically needs to know what to do before it gets the specifics of what the operand values actually are, hence prefix notation.

Prefix

Prefix notation or a variation of is used by most programming languages and processing arithmetic logic units (ALU), and can be defined as operator operand_1 operand_2 operand_3 and so on. Consider the following infix formula 2 + 4 * 6 + 2, this can be shown in prefix notation as + 2 + * 4 6 2, or perhaps more logically as a tree;

Processing is then performed as + 2 (+ (* 4 6) 2), with evaluation of the formula proceeding up the tree;

The tree structure representation of prefix forms the basis for this library, however it is undesirable to ask user input in this form due to limit comprehension by the general lay-person.

Infix -> Prefix Conversion

Infix to prefix conversation is performed on a stack using a tokenisor (in this case generating tokens via space edges).

1. Reverse the input string.
2. Examine the next element in the input.
3. If it is operand, add it to output string.
4. If it is Closing parenthesis, push it on stack.
5. If it is an operator, then
   1. If stack is empty, push operator on stack.
   2. If the top of stack is closing parenthesis, push operator on stack.
   3. If it has same or higher priority than the top of stack, push operator on stack.
   4. Else pop the operator from the stack and add it to output string, repeat step 5.
6. If it is a opening parenthesis, pop operators from stack and add them to output string until a closing parenthesis is encountered. Pop and discard the closing parenthesis.
7. If there is more input go to step 2.
8. If there is no more input, unstack the remaining operators and add them to output string.
9. Reverse the output string.

Courtesy of Expressions, Conversion and Evaluation with C.

Suppose we want to convert 2 + 4 * 6 + 2 into Prefix form: Reversed Expression: 2 + 6 * 4 + 2

Reverse the output string : + + 2 * 4 6 2

Processing a Dynamic Formula

Each mathematical operator is encapsulated via a class containing the operator and all operands needed by the operator (remembering that the operands may be other mathematical operators and operands), thus allowing the tree pattern as above.

Note: in this implementation of dynamic formula processing, not only may the standard mathematical operators and values be processed, but constants (e.g. x and y) as well. In terms of infix to prefix conversion, values and constants are treated in the same way as during this process the value of the token is not important in so much as the type is more important.

Each operator class contains the following methods;

• String parse(String s); - parses (and sub parses the string); returns the remainder of the string to process
• double evaluate(Hashtable variables); - returns the evaluation, using the appropriate variables as defined in the variable hash table
• bool nextIs(String s); - returns true if the next token is one of these operators
• ArrayList getVariableNames(); - returns a list of all required constants in this operator and sub-operators

The parse method proceeds as follows (* assuming an operator requiring two operands);

1. Read and remove first token; i.e. the operator
2. Read first token (i.e. an operand)
3. If the operand is a value or constant remove the token and save as operand 1
4. Else determine the type of operator and call parse using the remaining input string (saving as operand 1)
5. Using the remaining string (or result of operand 1's parse if operand 1 is really an operator) remove and save as operand 2 if token is a value or constant
6. Else determine the type of operator and call parse using the remaining input string (saving as operand 2)
7. Return the remaining string (or result of operand 2's parse if operand 2 is really an operator).

Thus, processing may complete as follows;

1. Get formula string
2. Convert to prefix notation
3. Determine operator type of first token
4. Parse whole formula string using relevant operator type

Once complete a tree data structure is formed as follows for the example 2 + 4 * 6 + 2 or + + 2 * 4 6 2;

    <add><add>2, <multiply>4, 6</multiply></add>, 2</add>

And hence calling the recursive evaluate method performs;

1. * 4 6
2. + 2 24
3. + 2 26
4. 28

In cases where constants are performed, the evaluate method performs a lookup in the supplied Hashtable.

Using the Code

The library supplied can evaluate mathematic functions + - * / ^(power).

• + encapsulated by Add
• - encapsulated by Subtract
• * encapsulated by Multiply
• / encapsulated by Divide
• ^ encapsulated by Power

In addition;

• values encapsulated by Value
• constants encapsulated by Variable

To use the library simply create a new Formula giving the formula string in the constructor. Calling evaluate with a Hashtable on constants (or new Hashtable() if none exist) returns the formula result.

Points of Interest

Is this the best way to evaluated formulas dynamically? No, the performance of this approach is not good when many formulas are to be processed due to the high number of method calls when evaluating. However, this method is particularly beneficial when using in conjunction with genetic algorithms (evolutionary algorithms) due to the ease of mutation and crossover. My next article on the subject will show how to use this library to generate a curve function that automatically fits ANY trend.

History

Version 1.0.0.0 - Initial build

Additional Licensing Notes

Please feel free to use this in your work, however please be aware that a modified The Code Project Open License (CPOL) is in use; basically it is the same as the standard license except that this code must not be used for commercial or not-for-profit commercial use without prior authorisation. Please see license.txt or license.pdf in the included source and demo files.