Introduction
The purpose of this article is to develop and explore a utility for taking a text-based mathematical algorithm and parse it to produce an actual numeric value. Furthermore, the utility should also be extensible, such that the developer should be able to supply custom methodologies and extensions to perform further operations on the values. The article also discusses the difference between using a textual-based parser and a token or call-stack based parser.
Background
The idea to develop this framework came to light after reading a few articles on parsing algorithms. The general trend appeared to be the use of Regular Expressions (Regex) to extract sets of mathematical formulae and execute them, eventually resulting in a final value.
Instead, this article will focus on constructing a 'stack' of instructions, which will be executed in order of priority to calculate a final value. The stacks will be generated by parsing the individual characters of the mathematical formula, and then determining the type, order and tier of the stacks before being executed to generate the resulting value.
Regex vs. Call Stack
Regex
The theory behind using Regex when parsing formulae is that the library has the capability to dynamically replace text depending on matched criteria, which simplifies the process of ordering the execution by extracting the highest priority operators first. For instance:
function execute(string formula)
{
for each brackets in formula:
replace brackets in formula = execute (brackets)
for each division in formula
replace division in formula = division.left / division.right
for each multiply in formula
replace multiply in formula = multiply.left * multiply.right
for each subtract in formula
replace subtract in formula = subtract.left - subtract.right
for each addition in formula
replace addition in formula = addition.left + addition.right
return (formula as double);
}
This crude pseudo-code is simply a representation of how the code, using Regex, would iterate through a string formula. With the Regex ability to replace in-line text within a string, each iteration through the formula would replace mathematical operators with the results of the operator.
So, using the pseudo-code above, let's consider the following formula:
2 + 5 * 10 / 2 + (100 - 90)
First, the execute() method would match that (100 - 90) satisfies the brackets condition of the function, thus calling the same execute() method on the inner formula within the brackets, and execute 100 - 90 and return the result from the inner call. After Regex replaces the brackets within the string, the formula would then look like:
2 + 5 * 10 / 2 + 10
The method would then continue on to search for division operators, which would match the 10 / 2 within the string, execute the division using the left and right values around the operator, and replace the value within the string, resulting in the formula looking like so:
2 + 5 * 5 + 10
The method would move forward to identify the multiplication (5 * 5) and replace that with the resulting value of the operation within the string, then fail to identify a subtraction operator, which leaves us with the following operation:
2 + 25 + 10
At this stage, the method will process every addition operator (2 + 25, then 27 + 10) replacing the values within the string, which will finally leave the value 37 within the string. Finally, the method will cast the number into a C# double type and return the value from the method.
The use of Regex for this operation is desirable because it makes processing mathematical formula a simple process. String operations are easy to perform, and Regex's ability to identify groups matching sequences and characters and being able to replace these with values reduces the amount of manual work involved. In addition, the implementation of mathematical functions and variables is extremely easy to satisfy, as Regex can match criteria based on the exact sequence of characters.
Call Stack
The idea of a 'call stack' for creating a mathematical sequence is to avoid the use of Regex when processing a string formula. Instead, the formula is dissected into blocks of information, which are identified as operations, and executed by order of importance. If a block is a sub-stack (such as any part of the formula which is within brackets, which needs executing as a sub-formula [much like the aforementioned Regex method] before the procedure uses the value) then these can be nested as callable blocks which need invoking.
The method in which the 'call stack' was implemented in this article is by using flexible structures which can serve as one of three different types: a numeric value, a sub-block (formula which needs parsing) or a method invocation. In order to retain this information, a single structure must be able to store any of the data, structured like so:
struct block
{
byte[] operations;
block[] stack;
block_method method;
double value;
};
In the above, stripped-down version of the structure used in this C# library, the structure can serve as the three different types using the below logic.
It is important to know that the value field of the structure will always contain the value of the block: if the block is executable (such as a nested block or formula, or a method invocation) then the value field will contain the result of the execution after it has been performed.
Numeric Value
When the block is nothing more than a number value, the block's value field will be populated with the number.
Formula
When a sub-formula (such as anything between brackets) is detected within the formula, the block will be constructed as another formula. The value field will contain a zero value by default, until the block is executed.
Method Invocation
When a method invocation is detected within the formula, the block_method field is populated, which contains the name of the method, and a list of comma-delimited parameters. The value field will contain a zero value by default, until the method invocation is executed.
So what does this mean for the order of execution? How do these tie in together and how does the block process exactly?
Let's consider the below formula:
2 + 2 * 3
This is a relatively simple operation, but it does need converting into a stack of operations. So, we iterate through the formula sequentially (left-to-right).
Parsing into a Call Stack
The first thing the parsing algorithm will do is allocate a 'parent block', which is an instance of the block structure which will serve as the almighty owner of the formula. After doing this, the operations field will be initialized as a new byte array and the stack field will be constructed. The parser will then proceed through the formula to identify fields.
The parser will find the number 2 at the beginning of the formula. This is a simple number, and shall be retained in the block as such. A new block structure will be allocated for this number, and the value field will be populated with the number 2. The parser will then append this new block into the stack array of the parent block, at index 0 and then record the index of the block in the operations field as the first byte.
At this stage, the parent block is structured like the following:
stack[0] = block { .value = 2 };
operations = {
00
};
The next item the parser will identify is the addition operator. An operator does not require a new block structure because it does not represent a value. The operations array follows a certain order, where every odd index represents an operator (so any bytes at indices 1, 3, 5 etc. will always be an operator between the previous and next blocks.)
The parser will append the byte representing the addition operator (in the case of this project this is 0x03) into the operations array at the next index, so the parent block will look like the following:
stack[0] = block { .value = 2 };
operations = {
00, 03
};
Following the same sequence of operations, the parser will identify another block representing the number 2 and append this into the stack. Next, the operator * representing the multiplication operator, and append this directly into the operations array (the byte representing multiplication being 0x05). Finally, the number 3 will be parsed and appended as a new block and registered in the operations array.
After these operations, the parent block will look like the below:
stack[0] = block { .value = 2 };
stack[1] = block { .value = 2 };
stack[2] = block { .value = 3 };
operations = {
00, 03, 01, 05, 02
};
To understand this simply, the 00, 01 and 02 bytes represent the indices of the blocks in the stack, while the 03 and 05 represent the addition and multiplication operators, respectively.
Executing the Call Stack
The execution of the call stack for this is relatively simple. In order to calculate the correct value of the formula, we must first execute all operators which have the highest importance. This can be achieved by iterating through the operations field of the parent block, check each odd index (1, 3, 5 etc.) and cross-check the operator.
function execute(block parent)
{
order = { 05, 03 }
operations = parent.operations
for each operator in order
{
for i = 1; operations.Length > i; i = i + 2
{
if operations[i] == operator then
calculate(operations, i)
}
}
}
As the pseudo-code above suggests, we traverse through and check each operator. The order variable stores the order in which operators must execute. If an operator is matched, we execute a yet-undefined calculate() function on the operations array with the current index within the array.
The purpose of the calculate() function for this formula is to run the operator on the values on the left and right of the operator index. To do this, consider the below function:
function calculate(block[] operations, int index)
{
double left = operations[index - 1].value
double right = operations[index + 1].value
byte operator = operations[index];
switch operator
{
when add: left += right; break;
when sub: left -= right; break;
when mul: left *= right; break;
when div: left /= right; break;
}
operations[index - 1].value = left;
operations[index + 1].value = left;
}The pseudo-code above has a simple purpose, to consume the left and right values of the blocks surrounding the operator, and then execute the operator command on the blocks. The code then updates both blocks with the calculated left value, so that if separate operators are executed on either block, they contain the latest value.
In reality, the implementation of this function is a little more complex. The sample supplied with the article has a procedure which updates a 'chain' of linked blocks. For example, take the following formula:
2 + 5 * 5 * 5 - 1
If this was executed using the above query then the values would not calculate correctly as the blocks wouldn't synchronise horizontally. The running order would look like so:
2 + 25 * 25 * 5 - 1
2 + 25 * 125 * 125 - 1
2 + 25 * 125 * 124 - 124
27 + 27 * 125 * 124 - 124
This may look confusing, but consider that values are always assigned to the left. With only processing the one link, the final resulting value of this formula would likely be 27 because we have not dragged across the changes made to the other values. If you investigate the Execute() method within the MQ.cs file of our sample application, you'll see that the changes are applied to any values which have previously been calculated.
See the below code, where any value which has been highlighted in bold has already had it's value modified, and should become the target of future updates:
2 + 25 * 25 * 5 - 1
2 + 125 * 125 * 125 - 1
2 + 124 * 124 * 124 - 124
126 + 126 * 126 * 126 - 126
The above code now produces the result 126, which is actually the value we need. It may seem confusing, but what should be digested is that any value which has already had it's value calculated (anything in bold) will not be calculated again, but will be updated when any directly linked block to the left or right has had its value changed. The latest value of an operation in the formula is always stored to the left, which means that it should be accessible through the order of operations.
To better understand the procedure, the below image highlights each stage of the calculation, where any blocks highlighted in orange are next to be calculated and any blocks highlighted in green denote blocks which have been calculated previously. Blocks which are green (or orange) which are directly next to any other blocks which are orange or green will be affected by the result of the calculation:
Any time an operator has been completed, the nodes on the left and right become linked. This link continues to spread as operators are executed next to each other, which results in the values of operations being shared across the formula where nodes are linked.
Taking a different approach, consider the below formula which has two high priority operators separated by lesser priority addition and subtraction operators:
2 * 2 + 1 - 20 / 2
The two first operators which shall be run are the division (20 / 2) and multiplication (2 * 2) respectively. This means that the two blocks will not be connected because an addition of 1 lies between the two blocks. This produces the following order of operation:
2 * 2 + 1 - 10 / 10
4 * 4 + 1 - 10 / 10
At this stage, the 1 is now the only non-calculated block within the formula, which means it becomes the subject of whichever next operator executes first. In this case, this is the subtraction operator, followed by the addition:
4 * 4 + -9 - -9 / -9
-5 * -5 + -5 - -5 / -5
The value of the 1 - 10 operation occurs, updating the value of the block representing 1 to -9, but the value -9 is not carried across to the 4 * 4 block because the addition operator has not yet been executed, and is not linked to the right-side of the formula. Only when the addition operator is executed does the left-side become updated, with the value of 4 + -9
This visualised in a similar diagram to the one previously would look like so:
This is similar idea to a linked list, where nodes are connected using left and right fields which reference to the locations of nodes. Whenever a block is first created within the formula, both left and right fields hold no reference to another block. However, once a block has been executed, the value of the left field points to the value of the right field, and visa versa.
If another block is executed, and the left or right field has a value linking to another block, then the block in either field is updated and the same iteration continues occurring until the left or right field has no more references.
Executing Brackets
Bracket operations are stored as their own blocks within the stack field of the parent block. They are stored this way as they represent a sub-formula which needs to be executed to produce a value, which can then be used in the parent formula as normal.
Consider the below formula which utilises brackets as one of the operations:
2 * (2 + 2)
If the aforementioned execution practise was used, the parser would execute the 2 * 2 prior to adding the additional 2. Instead, to separate the 2 + 2 as an executable sub-formula, the value within the formula should be contained within an executable block.
Therefore, when constructing the call stack for this operation, the order of parsing would begin by parsing the 2 and multiplication symbol into the parent block:
stack[0] = block { .value = 2 };
operations = {
00, 05
};At this point, the parser will now recognise that an opening bracket has been matched, which signals the start of a sub-formula. A new block will be constructed in preparation of appending it into the stack, but instead of setting the value field of the new block, instead the same parsing function will be called from the index after the opening bracket, with this new block as the target of the call stack.
The parser would recognise and store the value within the brackets within the new block:
child_stack[0] = block { .value = 2 };
child_stack[1] = block { .value = 2 };
child_operations = {
00, 03, 01
};Once the closing bracket is reached, the nested parse function will exit and the parent block now has a child block which has a set of operations and a stack assigned, with a value of zero. The parent block will now append this child block into the operations array and continue forward. The parent block will finally look like the following:
stack[0] = block { .value = 2 };
stack[1] = block
{
stack[0] = block { .value = 2 };
stack[1] = block { .value = 2 };
operations = {
00, 03, 01
};
};
operations = {
00, 05, 01
}; At this stage, the block is ready to be executed. The only difference this time is that the second block in the stack needs executing prior to the value field being used.
To do this, a minor alteration needs adding the calculate() pseudo-function we created earlier, which will ensure that the block is executed:
function calculate(block[] operations, int index)
{
if operations[index - 1].stack is not null then
execute(operations[index - 1]);
if operations[index + 1].stack is not null then
execute(operations[index + 1]);
double left = operations[index - 1].value
double right = operations[index + 1].value
byte operator = operations[index];
switch operator
{
when add: left += right; break;
when sub: left -= right; break;
when mul: left *= right; break;
when div: left /= right; break;
}
operations[index - 1].value = left;
operations[index + 1].value = left;
} All that has been added is a check to see if an operation block contains a stack of its own, which means that there's an operation which needs to be performed on the block before the value field can be used for calculation. When the execute function is called on the block, the stack and operations fields will then be set to null so that future references to the block uses either the calculated value, or the most recent value as assigned by the formula.
Executing Methods
Implementing support for custom methods works in a very similar fashion. During the parse routine, if the parser encounters any function-name character (a-z, A-Z or an underscore) it will begin a 'function' loop. This essentially informs the parser than it needs to prepare to construct a stack block representing a method invocation:
10 + pow2(2)
Using the above formula, the parser will recognise the 10 and addition operator as standard and append these values into the stack and operations fields.
At which point, the next recognised character is p, so the parser enters a 'parsing method' state, which reads all valid characters (a-z, A-Z, 0-9 or underscore) until a bracket or space is reached. Once the opening bracket is reached, the parser enters a 'parsing method parameters' state, which calls the same parsing method on the script from index after the opening bracket. See the below parsing structure, where each part within quotations is the current parse target:
'pow2'(2)
The name of the method is extracted ('pow2')
pow2'('2)
The opening bracket is matched, and the parser begins the parameter parsing mode.
pow2('2')
The digit 2 is extracted from the parameters.
pow2(2')'
The closing bracket is matched, the script leaves the method parsing states.To understand the exact process more in-depth, refer to the ParseMethod method within the MQ.cs file.
Finally, once the method name and parameters have been successfully parsed from the formula, the parser constructs a block_method object and copies the method name and parameters. This block_method is then stored against a new block object, in the method field, and this is pushed onto the stack (the same as any number or sub-formula block.)
So, for the formula described above, the stack would look like the following:
stack[0] = block { .value = 10 };
stack[1] = block
{
method = block_method
{
parameters[0] = block { .value = 2 };
name = "pow2";
};
};
operations = {
00, 03, 01
};The block at stack index 1 has a zero value by default. A similar change needs making to the calculate() method to ensure that the method is invoked before the value field is used:
function calculate(block[] operations, int index)
{
if operations[index - 1].method is not null then
invoke_method(operations[index - 1])
if operations[index + 1].method is not null then
invoke_method(operations[index + 1])
if operations[index - 1].stack is not null then
execute(operations[index - 1])
if operations[index + 1].stack is not null then
execute(operations[index + 1])
double left = operations[index - 1].value
double right = operations[index + 1].value
byte operator = operations[index]
switch operator
{
when add: left += right
when sub: left -= right
when mul: left *= right
when div: left /= right
}
operations[index - 1].value = left
operations[index + 1].value = left
} Added is a check to validate whether the method field of the left and right stack blocks have been assigned. If this is the case, then the invoke_method() function is called on the relevant blocks to calculate the value.
Below is an example of how the pow2 method might be implemented for the above formula:
function invoke_method(block parent)
{
for i = 0; parent.parameters.Length > i; i = i + 1
{
execute(parent.parameters[i])
}
if parent.method.name = "pow2" then
parent.value = parent.parameters[0].value ^ 2;
parent.method = null
} The method performs an execution on each of the parameters (in-case these parameters are also method invocations or sub-formulas) and then checks the name of the method to execute the pow2 function. Once the method has been successfully invoked, the value field of the block is assigned, and the method field is reset to null to prevent being invoked again.
Using the Code
Getting Started
The attached sample project includes a Class Library project (MQ) and a Console Application project (MQExample) which you can use for testing.
To begin using the parser, construct a new instance of the MQ class and store it. It's recommended to keep a persistent copy of the class available, rather than creating instances on-the-fly.
private System.Parsers.MQ parser = new System.Parsers.MQ();
Executing mathematical formula is as easy as invoking the Calculate() method of the class. The method accepts a string parameter which is the text representation of the formula to calculate. For instance:
public double GetFormulaValue()
{
return parser.Calculate("2 * 5 / 3 + (1 * 2 * 3) / (4 - 2)");
}Adding Functions
The parser also has support for registering custom functions. Any function which can be handled by the parsing engine must implement the MQFunctionHandler signature, which is the following:
double MQFunctionHandler(MQParameters e);
The function must return a double value which is the result of the method invocation. And the MQParameters class is a collection of all the parameters which were passed into the method. Each value within the parameters is a double value.
myFunction(1, (2 * 3), ((1 + 1) / 0.25))
This would generate an MQParameters list with the values:
e[0] = 1.00
e[1] = 6.00
e[2] = 8.00
To register a function handler for "myFunction" we simply create a new instance of an MQFunction object and append it into the Functions property of the parser. The constructor for an MQFunction object accepts multiple arguments which determine the behaviour of the function:
MQFunction(string name, MQFunctionHandler callback);MQFunction(string name, MQFunctionHandler callback, int parameters);MQFunction(string name, MQFunctionHandler callback, int minParams, int maxParams);
Where the parameters of the method are as such:
name - The name of the method to be recognised in a formula.callback - The callback method which will be raised when the method is invoked in the formula.parameters - The precise number of parameters that the method requires.minParams - The minimum number of parameters required by the method.maxParams - The maximum number of parameters the method will accept.
To register an instance of our "myFunction" method, we add the function so:
private void SetupFunctions()
{
parser.Functions.Add(new MQFunction("myFunction", new MQFunctionHandler(MyFunction), 3));
}
private double MyFunction(MQParameters parameters)
{
return parameters[0] + parameters[1] + parameters[2];
} Or, using an anonymous function and lambda:
parser.Functions.Add(new MQFunction("myFunction", (e) => { return e[0] + e[1] + e[2]; }, 3)); Thus, any call to the "myFunction" method will add the three parameters together and return the result, which will then be placed into the call stack for the method invocation.
Note:
The MQ class comes with some basic mathematical functions already built-in. These include abs(x), ceil(x), cos(x), floor(x), log(x, y), log10(x), max(x, y), min(x, y), pow2(x), round(x), round(x, y), sin(x), sqrt(x) and tan(x)
Benchmark
A comparative benchmark was run against the MQ parser which included three alternative parsing libraries:
These libraries were selected because each provides it's own different take on the parsing of expressions. Regular Expressions refers to the origin methodology mentioned at the beginning of the article, which involves parsing and manipulating the string directly using complex matching patterns, while a token-based approach behaves similarly to a call-stack approach in that symbols are extracted and converted into 'blocks' or 'tokens' which are then executed.
The results of the benchmark are as follows:
MQ - MQ Parser
MPN - Math Parser .NET
MP - Math Processor
CE - Calculation Engine for .NET
Formula | Cycles | MQ (ms) | MPN (ms) | MP (ms) | CE (ms)
-----------------------------------------------------------------------
E1 | 100 | 11.008 | 91.0592 | 50.0352 | 1.9968
E1 | 1000 | 4.0064 | 309.2096 | 33.0112 | 2.0096
E1 | 10000 | 40.0256 | 3015.0144 | 337.2288 | 124.0832
-----------------------------------------------------------------------
E2 | 100 | 0.9984 | 35.0336 | 4.992 | 0.00
E2 | 1000 | 5.9904 | 330.2144 | 46.0416 | 2.9952
E2 | 10000 | 59.0464 | 3268.1856 | 458.304 | 449.3056
-----------------------------------------------------------------------
E3 | 100 | 7.0016 | 66.048 | 19.008 | 0.9984
E3 | 1000 | 8.9984 | 612.416 | 57.0368 | 3.9936
E3 | 10000 | 84.0448 | 6127.104 | 577.3824 | 575.3856
-----------------------------------------------------------------------
E4 | 100 | 0.9984 | 36.032 | 7.0016 | 0.00
E4 | 1000 | 9.0112 | 359.232 | 63.04 | 4.0064
E4 | 10000 | 81.0496 | 3585.3952 | 630.4256 | 573.376
-----------------------------------------------------------------------
E5 | 100 | 3.008 | 120.0768 | 6.0032 | 1.0112
E5 | 1000 | 14.0032 | 1180.80 | 57.0368 | 4.992
E5 | 10000 | 131.0848 | 11799.8976 | 565.376 | 460.3008
-----------------------------------------------------------------------
E6 | 100 | 2.9952 | 51.0336 | 10.0096 | 0.9984
E6 | 1000 | 18.0096 | 479.3216 | 101.0688 | 8.00
E6 | 10000 | 163.1104 | 4821.2224 | 1013.6704 | 361.2416
-----------------------------------------------------------------------
These are the results of a single execution of the benchmark (which is available in the attached source code) after performing different equations. The equations for each formula are as below, where the letter R denotes a random value which is generated for each cycle of the formula:
E1 - 100.00 * 50.00 + (R / 123.00)
E2 - 20.00 / (3.35 * 0.52) / (R / 2.05) * 4.32
E3 - 4.00 * 2.00 / 0.345 * R / 7.42 * cos(8.83) / 0.128
E4 - 1.00 + (200.00 * (2.00 * 100.00 / 8.00) / (8.00 + 10.00)) * R
E5 - cos(tan(R) * 0.293) / sin(2.3994 * R)
E6 - ((2.12 / 1200) * ((1 + 2 / 1200) * (1 + 2 / 1200)) / ((1 + 2 / 1200) * (1 + 2 / 1200) - 1)) * R
The benchmarks highlight that the MQ parser engine functions significantly faster than the Math Parser .NET library (which uses the Regex approach) and the Math Processor library (which uses tokens.)
However, the MQ parser engine performs worse during lower numbers of cycles of a formula than the Calculation Engine library. In contrast, during high numbers of cycles of a formula, the MQ parser engine performs greater. A potential explanation for this might be that the MQ parser does not use any collection for storing blocks of data. Instead, the MQ parser allocates a fixed array size prior to the expression being executed and only expands when the limit is reached. While an ArrayList object may perform the same functionality, using a collection object means allocating all the memory surrounding the object and relying entirely on the object to perform as efficiently as possible, which is hindered slightly by the need to cast items of the ArrayList back to the original type.
In any case, the benchmark highlights the fact that regular expression parsing of a formula is very inefficient. Even if regular expressions are pre-compiled and executed upon strings, the time taken to process symbols in the string, execute the corresponding calculation, and then replace the value within the originating string is a long and expensive process. Extracting the symbols and allocating small amounts of memory to store the information is far more effective, since the process is essentially the same as moving data from one location (the string) to another (the target blocks) and running this memory through the execution algorithm.
Summary
While the use of regular expressions makes parsing calculations easier, reducing the footwork necessary by the developer, it's not entirely the best methodology for use in expression-intensive software. Regular expressions are a costly utility to use, especially as expressions become larger and more complex, increasing the amount of searches required on the string and increasing the number of replacements.
Using a tokenized or call-stack approach when parsing expressions can be tedious to build, but the performance gains are worth the additional development time. If we took the same principles and applied them to a 'pseudo-code' parser, which dissected and interpreted a custom scripting language, the use of a regular expression parser would become impractical.
Once we discover that sub-expressions and functions can be converted into their own blocks, it becomes easier to manage such expressions. One of the more difficult problems encountered when developing parsers is how to consider the order of priority when dealing with mathematics. Particularly in pseudo-code parsers, designing code which will effectively process nested codes becomes an issue once the developer begins to think linearly. Instead, embedding nodes and blocks is a practical approach to resolving some of these priority and nesting issues.
Points of Interest
I understand that some of the projects used in this article for benchmarking are rather old. The purpose of the article was to highlight more the efficiency of using call stacks, than actually developing a library which functions at the highest speed and accuracy. The article should probably used more as a reference, for those interested in generating your own script and expression tree parsers, than an actual library for parsing expressions.
The MQ parsers misses out some fundamental ideals when parsing expressions. Some basic mathematical problems which aren't addressed in the source code include:
- Negative and positive prefixes for numbers do not function correctly. For example:
2 - -2
This will not function properly because the MQ parser expects a number following an operator. This could be fixed easily in the source, however I have not had time to resolve the issue. - Many additional/desirable operators are missing, such as:
<< >> | & ~
History
- 1.0.0 - 3rd April, 2014 - Initial article.
- 1.0.1 - 7th April, 2014 - Re-uploaded the ZIP archive to include all solution files.
