Click here to Skip to main content
15,868,150 members
Articles / Desktop Programming / Windows Forms
Article

Implementing an Excel-like formula engine

Rate me:
Please Sign up or sign in to vote.
4.93/5 (49 votes)
17 Mar 2007LGPL310 min read 374.8K   11.5K   199   127
A library to parse and evaluate Excel-style formulas and recalculate in natural order
Using the engine to evaluate an expression

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 the Formula 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:
VB.NET
' 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:

VB.NET
' 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 called ResultType 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.
VB.NET
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 the IReference 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.
VB.NET
' 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:

VB.NET
' 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:

VB.NET
' 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 the FunctionLibrary 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 FormulaFunctionCall delegate
  • Tag the method with either the FixedArgumentFormulaFunction or VariableArgumentFormulaFunction attribute
  • Add it to the function library
Let's define a function that returns the length of the hypotenuse given the length of the other two sides: First we must define a method with the correct signature:
VB.NET
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 Argument instances
  • An instance of the FunctionResult class where we will store our function's return value
  • An instance of the formula engine
Second, we have to adorn our method with the proper attribute so that the function library can recognize it:
VB.NET
<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:

VB.NET
<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:

VB.NET
engine.FunctionLibrary.AddFunction(AddressOf Hypotenuse)

And now we can use it in a function:

VB.NET
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
I will certainly look into implementing them if there is enough demand.

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

License

This article, along with any associated source code and files, is licensed under The GNU Lesser General Public License (LGPLv3)


Written By
Web Developer
Canada Canada
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
AnswerRe: Multithreading? Pin
Eugene Ciloci3-May-07 11:36
Eugene Ciloci3-May-07 11:36 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller3-May-07 12:51
Jeremy T. Fuller3-May-07 12:51 
GeneralRe: Multithreading? Pin
Eugene Ciloci3-May-07 15:19
Eugene Ciloci3-May-07 15:19 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller3-May-07 15:34
Jeremy T. Fuller3-May-07 15:34 
GeneralRe: Multithreading? Pin
Eugene Ciloci4-May-07 6:08
Eugene Ciloci4-May-07 6:08 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller4-May-07 6:15
Jeremy T. Fuller4-May-07 6:15 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller7-May-07 5:41
Jeremy T. Fuller7-May-07 5:41 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller7-May-07 5:50
Jeremy T. Fuller7-May-07 5:50 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller7-May-07 6:13
Jeremy T. Fuller7-May-07 6:13 
GeneralRe: Multithreading? Pin
Eugene Ciloci7-May-07 6:24
Eugene Ciloci7-May-07 6:24 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller7-May-07 6:28
Jeremy T. Fuller7-May-07 6:28 
GeneralRe: Multithreading? Pin
Eugene Ciloci7-May-07 7:16
Eugene Ciloci7-May-07 7:16 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller7-May-07 7:34
Jeremy T. Fuller7-May-07 7:34 
GeneralRe: Multithreading? Pin
Eugene Ciloci7-May-07 9:00
Eugene Ciloci7-May-07 9:00 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller7-May-07 11:48
Jeremy T. Fuller7-May-07 11:48 
GeneralRe: Multithreading? Pin
Eugene Ciloci4-May-07 7:35
Eugene Ciloci4-May-07 7:35 
GeneralRe: Multithreading? Pin
Jeremy T. Fuller4-May-07 7:38
Jeremy T. Fuller4-May-07 7:38 
GeneralExcel Date type simulation... Pin
akinolot1-May-07 16:51
akinolot1-May-07 16:51 
GeneralRe: Excel Date type simulation... Pin
Eugene Ciloci2-May-07 17:29
Eugene Ciloci2-May-07 17:29 
GeneralRe: Excel Date type simulation... Pin
akinolot2-May-07 18:19
akinolot2-May-07 18:19 
GeneralRe: Excel Date type simulation... Pin
Eugene Ciloci3-May-07 12:03
Eugene Ciloci3-May-07 12:03 
GeneralRe: Excel Date type simulation... Pin
Eugene Ciloci7-May-07 10:33
Eugene Ciloci7-May-07 10:33 
GeneralRe: Excel Date type simulation... Pin
akinolot12-May-07 18:59
akinolot12-May-07 18:59 
GeneralSave does not work Pin
akinolot1-May-07 16:19
akinolot1-May-07 16:19 
GeneralRe: Save does not work Pin
Eugene Ciloci2-May-07 17:13
Eugene Ciloci2-May-07 17:13 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.