Menu
What's the best algorithm for evaluating a mathematical expression? I'd like to be able to optimize this a little in the sense that I may have one formula with various variables, which I may need to evaluate hundreds of times using different variables. So basically if I can initially parse the formula so that it is optimized in some way, and I can then pass in the variables to this optimized version as many times as I need, each time it produces a result for me.
I'll be writing this in either Delphi or C#. I have already written something similar by using the shunting yard algorithm, but each time I need to calculate the same formula, I'm having to go through the parsing stage. There must be a better way to do this.
633
To evaluate an algebraic expression, you have to substitute a number for each variable and perform the arithmetic operations. In the example above, the variable x is equal to 6 since 6 + 6 = 12. If we know the value of our variables, we can replace the variables with their values and then evaluate the expression.
The stack organization is very effective in evaluating arithmetic expressions. Expressions are usually represented in what is known as Infix notation, in which each operator is written between two operands (i.e., A + B).
Step 1: Create an operand stack. Step 2: If the character is an operand, push it to the operand stack. Step 3: If the character is an operator, pop two operands from the stack, operate and push the result back to the stack. Step 4:After the entire expression has been traversed, pop the final result from the stack.
If you want to do it with Delphi, you could look into how the JclExprEval unit works, part of the JEDI Code Library. I wrote it several years ago (it's a little over-engineered); it parses functions and variables and can hand you back a method pointer which evaluates the expression quickly. Pass the variables in by reference, and you can change them directly and the re-evaluated expression will be calculated accordingly.
In any case, the basics of how it works may be helpful for you. Recursive-descent parsing of expressions is easy, and by building a tree you can evaluate multiple times without re-parsing. JclExprEval actually generates code for a simple stack machine, so that it can work a little faster than tree interpretation; stack machines largely restrict their memory operations to arrays and use switches for opcodes, while tree interpretation follows links throughout the heap and often uses virtual dispatch (or double-dispatch) for opcodes, so they usually end up slower.
Taking the same approach as JclExprEval in parsing but written in C#, and building up an Expression, like Marc suggests, is another perfectly valid approach. The JIT-compiled expression ought to be quite a bit faster than an interpreted expression program or tree, which themselves are a lot faster than parsing.
127
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
