 |
||||||||||
| ||||||||||
| ||||||||||
Languages »
VB.NET »
Parsers and Interpreters
Intermediate License: The GNU Lesser General Public License
Implementing an Excel-like formula engineBy Eugene CilociA library to parse and evaluate Excel-style formulas and recalculate in natural order |
VB 8.0, VBWindows, .NET, .NET 2.0, Win2K, WinXP, WinForms, VS2005, Visual Studio, Dev Posted: 3 Mar 2007 Updated: 17 Mar 2007 Views: 55,646 Bookmarked: 99 times |
||
|
|
|||
Announcements
Chapters
Services
Feature Zones
|
Advanced Search Sitemap |
|
|
||||||||||||||||||
- Download sample application - 228.4 KB
- Download library and documentation - 387.1 KB
- Download source code - 321.7 KB
- Download latest version from SourceForge
Introduction
FormulaEngine is a .NET assembly that enables you to add formula support to your application. It takes care of parsing and evaluating formulas, tracking their dependencies, and recalculating in natural order. The formula syntax and much of the engine's functionality are direct replicas of Excel ensuring a low learning curve for users. The library is licensed under the LGPL and the project is hosted here on SourceForge.Features
Here's a list of the engine's major features:- Parses and evaluates Excel-style formulas
- Comes with over a hundred common Excel functions already implemented and makes it easy to add your own
- Custom formula functions are automatically validated for argument type and count
- Supports custom functions with optional arguments and variable-length argument lists
- Named references, volatile functions, and dynamic references are supported
- Supports formulas on multiple sheets
- Interacts with sheets through an interface, allowing any class to be used as a sheet
- Tracks and adjusts references during row/column inserts/deletes and range moves
- Manages formula dependencies and recalculates in natural order
- Supports working without any sheets
- Culture-sensitive decimal point and argument separator
Motivation
I wrote this library for the following reasons:- I needed a hobby project to work on at home and this seemed like an idea with the right balance of challenge and usefulness
- At work, I was working with a formula engine implemented by a third-party component vendor for their grid. I though that their implementation was absolutely horrible (all operands are strings) and that any programmer worth his salt should be able to do better; I decided to put my money where my mouth is.
Yet another expression evaluator?
Seeing that expression evaluators are very popular here on CodeProject, what makes this one different? The two main differences are that this library implements many features found in Excel and that it does more than just evaluate expressions.Overview
In this article, I will give a brief overview of the three major things that this library enables you to do:- Formula parsing/evaluation
- Natural order recalculation
- Defining custom functions for use in formulas
Formula parsing and evaluation
The first thing this library allows you to do is evaluate formula expressions. The supported syntax is based on Excel and 95% of existing formulas should be able to be used without any modification. The engine provides theFormula class, which represents a compiled formula expression. You call the engine's CreateFormula method with an expression and it will return a Formula instance that you can evaluate:
' Create an instance of the engine
Dim engine As New FormulaEngine
' Create a formula
Dim f As Formula = engine.CreateFormula("=sqrt(3^2 + 4^2)")
' Evaluate the formula to get a result (5.0)
Dim result As Double = f.Evaluate()
The method will throw an InvalidFormulaException exception if it cannot create a formula from the expression. This is usually (but is not limited to) due to a syntax error in the expression. The inner exception of the thrown exception will have more details.
The engine also has the ever-popular Evaluate method for when you quickly want to evaluate an expression. Let's try to evaluate the "mega" formula found here:
' Create an instance of the engine
Dim engine As New FormulaEngine
' Assume cell A1 contains "http://j-walk.com/ss/books"
' Call Evaluate to get a result: "books"
Dim result As String = engine.Evaluate("=RIGHT(A1,LEN(A1)-FIND(CHAR(1),_
SUBSTITUTE(A1,""/"",CHAR(1)" _
& ",LEN(A1)-LEN(SUBSTITUTE(A1,""/"","""")))))")
Data types and calculation
The engine supports the following data types when evaluating expressions: Integer, Double, String, Boolean, DateTime, Null, Error values, and References. Just like Excel, operands are loosely typed meaning that any data type is valid as long as it can be converted to the desired data type. For example: the expression="123" + 10 is valid since the string "123" can be converted to a number. One major difference from Excel is that DateTime values are not treated as numbers. If you want to add/subtract dates, you will have to use a function.
When an error is encountered during formula evaluation, an ErrorValueWrapper instance will be returned. This class wraps one of the seven Excel error values and allows you to get the specific error as well as format it.
Formulas and the result type property
The formula class has a property on it calledResultType that allows you to specify the desired type of the formula's result. This is useful when you have an expression like =A1 which could validly evaluate to either the contents of cell A1 or a reference to it. By setting the result type you can control which of the two results you get. The formula will attempt to convert its result to the specified type. If the conversion is not possible, then the #VALUE! error will be returned.
Dim f As Formula = engine.CreateFormula("=A1")
' Make the formula evaluate to any value except a reference
f.ResultType = OperandType.Primitive
' result will be the contents of cell A1
Dim result As Object = f.Evaluate()
' Make the formula evaluate to a sheet reference
f.ResultType = OperandType.SheetReference
' result will be a reference to cell A1
result = f.Evaluate()
Natural order recalculation
The second thing the library allows you to do is natural order recalculation. For those unfamiliar with the term, recalculating in natural order means that a formula is recalculated after any formulas that it depends on. Consider the a worksheet with the following values and formulas:(A1): 15
(B2): =A1 + 10
(C1): =A1 + B2
(D2): =C1 * 2
When the contents of cell A1 change, the three formulas need to be recalculated. The formula at B2 must be recalculated first since it only depends on A1. The formula at C1 is recalculated second since it depends on the value of B2. Finally, the formula at D2 is recalculated last since it depends on C1.
For the engine to be able to recalculate in natural order, it must keep track of the dependencies between formulas. It does this by acting as a container for formulas. As formulas are added to the engine, their dependencies are analyzed and a dependency graph is built. You then tell the engine to recalculate and it will use the graph to build up a calculation list, sort it in natural order, and recalculate each formula.
References
The basic unit that the engine uses to track dependencies is the reference. There are various types of references, they all implement theIReference interface, and the ReferenceFactory class creates them all. When you add a formula to the engine, you need to specify a reference that the formula will be bound to. The formula will then "live" at that reference. By changing the type of reference you bind the formula to, you can change how that formula is referenced from other formulas. For example: by binding a formula to a named reference, you allow other formulas to reference it by using a name.
' Associate the name Root2 with a formula
engine.AddFormula("=sqrt(2)", engine.ReferenceFactory.Named("Root2"))
' Use the name in an expression (result is 2.0)
Dim result As Double = engine.Evaluate("=root2 ^ 2")
Now that we've seen how the engine tracks dependencies, let's see how the initial example above would be set up using code:
' Assume we've already added a worksheet to the engine
' Add a formula at B2
engine.AddFormula("=A1 + 10", engine.ReferenceFactory.Cell(2, 2))
' Add a formula at C1
engine.AddFormula("=A1 + B2", engine.ReferenceFactory.Parse("C1"))
' Add a formula at D2
engine.AddFormula("=C1 * 2", engine.ReferenceFactory.Parse("D2"))
Our engine now contains 3 formulas and a graph describing their dependencies. All we need to do is tell the engine that a reference has changed and that all its dependents need to be recalculated. We do this using the Recalculate method:
' Create a reference to cell A1
Dim a1Ref As ISheetReference = engine.ReferenceFactory.Parse("A1")
' Recalculate all dependents of A1
engine.Recalculate(a1Ref)
Custom functions
The last thing the engine allows you to do is define your own functions for use in formulas. To do this we must use theFunctionLibrary class, which is accessible through a property on the engine. The extensibility mechanism I used is based on delegates. I felt that this makes it easier to add many functions because you don't have to define a new class for each function as with the alternative interface/subclass based mechanism. It also allows the engine to use reflection to add all the methods of a class in bulk. Defining a custom function requires three steps:
- Define a method with the same signature as the
FormulaFunctionCalldelegate - Tag the method with either the
FixedArgumentFormulaFunctionorVariableArgumentFormulaFunctionattribute - Add it to the function library
Public Sub Hypotenuse(ByVal args() As Argument, ByVal result As FunctionResult,_
ByVal engine As FormulaEngine)
End Sub
Explanation of the three arguments:
- The arguments to our function as an array of
Argumentinstances - An instance of the
FunctionResultclass where we will store our function's return value - An instance of the formula engine
<FixedArgumentFormulaFunction(2, New OperandType() {OperandType.Double, _
OperandType.Double})> _
Public Sub Hypotenuse(ByVal args() As Argument, ByVal result As FunctionResult,_
ByVal engine As FormulaEngine)
End Sub
We have now declared our method as requiring 2 arguments, both of type Double. The engine will only call our method if exactly 2 arguments were specified in the formula and both arguments can be converted to Double. This frees us from having to write argument validation code for every function we want to implement.
Finally, we must write the actual implementation of our function:
<FixedArgumentFormulaFunction(2, New OperandType() {OperandType.Double, _
OperandType.Double})> _
Public Sub Hypotenuse(ByVal args() As Argument, ByVal result As FunctionResult,_
ByVal engine As FormulaEngine)
' Get the value of the first argument as a double
Dim a As Double = args(0).ValueAsDouble
' Get the value of the second argument as a double
Dim b As Double = args(1).ValueAsDouble
' Compute the hypotenuse
Dim hyp As Double = System.Math.Sqrt(a ^ 2 + b ^ 2)
' Set the function's result
result.SetValue(hyp)
End Sub
We get the value of each of our arguments as a double, compute the hypotenuse, and set the value into the FunctionResult.
Next we add our custom function to the library:
engine.FunctionLibrary.AddFunction(AddressOf Hypotenuse)
And now we can use it in a function:
dim result as Double = engine.Evaluate("=10 + Hypotenuse(3, 4)")
Please note that all functions must return a value and you cannot define/undefine functions while formulas are defined.
Demo application
The demo application is a poor man's version of Excel. It is meant to be a reference implementation showing how to use all of the engine's features. It shows off the following:- Multiple sheets and cross-sheet references
- Named references
- Reference tracking through row/column insert/delete and range move
- Cut/Copy/Paste and fill right/down support
- Absolute/relative references
- Save and load of the formula engine and worksheets
- Formulas that aren't on any sheet and that "watch" sheet values (go to Insert -> Chart)
Implementation details
Formula Parsing
To implement parsing of formulas, I used the excellent Grammatica parser generator. I wrote a grammar describing the syntax of a formula and let Grammatica generate a parser. I then let the parser parse, listen to callbacks, and fill out the parse tree with my own objects. At the end, I have a root element representing the entire parse tree of the formula. I re-arrange the tree into postfix form and save that into a formula instance. Evaluating a formula then simply consists of iterating through each element and having it push/pop values off a stack. In the end, there should be one value left on the stack, which is the formula's result.I chose Grammatica because it has a clean separation between grammar and parser code, has easy to use grammar syntax, and it outputs VB .NET code. The project hasn't had any activity in a while but it is not dead and even though the version I'm using is an alpha, I found it to be very stable: no crashes and no incorrect functionality. I highly recommend it if you, like me, are new to parsers and grammars.
Also, since the grammatica parser is created at runtime, it is very easy to dynamically change the decimal and argument separator patterns to use the values of the current culture. This means that instead of =1.2 + sum(1,2,3), a user in Estonia can enter =1,2 + sum(1;2;3) and have it be a valid formula.
Natural order recalculation
The engine maintains a dependency graph for all formulas. When a recalculate is required, a temporary graph is built starting at the root node of the recalculate. Once all circular references are removed, a topological sort is performed on the graph to get a list of formulas in natural order. With this calculation list, it is simply a matter of iterating through it and re-evaluating each formula.Not Implemented
The following things are not implemented because they are obscure or advanced features that most people won't know about or find useful:- Array formulas
- Range, union and intersection operators
- 3D references
Conclusion
I found that coding this project gave me lots of insight into how Excel works. Having to implement 100+ Excel functions makes you very familiar with all their little quirks. For example: the formula=Offset(A1,1,1) entered into cell A1 is not treated as a circular reference by Excel even though it depends on its own cell. Another example is that the concatenate formula does not work with non-cell ranges. Whereas you can say =Sum(A1:B2), you cannot say =Concatenate(A1:B2).
This project is currently in the alpha phase because it hasn't had any real-world testing/usage. As mentioned in the introduction, the project is hosted on SourceForge. Any bugs or feature requests should be reported there using the provided tools. Any new releases will be also posted there.
Well, I hope you guys find this project useful!
History
- Mar 4, 2007
- Initial Release
- Mar 6, 2007
- Switched from Dundas chart to ZedGraph due to its smaller footprint
- Source release now includes chart assembly
- Mar 17, 2007
- Fixed bug where named references wouldn't get recalculated
- Added Variable class to make using named constant values easier
