Parser for Mathematical Expressions ?

I want to add something to a script to evaluate user given string inputs as mathematical expressions.

What is Grasshopper itself using ? Is it something David has written, part of QWhale, or some other library ? Can I use the same thing, or can anyone recommend a good freely available library with a not too restrictive license ?

Just to clarify - This has to be something that will work within the script, not just a separate component which evaluates the expression for a certain set of input values and passes it as a numerical input, because the script will be generating its own changing input values for the variables of the expression and using the results as it runs.

I'd like it to be able to cope with at least the same sort of range of functions as GH's own expression editor, and ideally to be able to add one or two extras.

Any pointers much appreciated, thanks.

Replies to This Discussion

Permalink Reply by David Rutten on February 20, 2010 at 12:08pm

Hi Daniel,

I wrote the parser myself. Due to a number of successive optimisations it's a bit difficult to make hay of the current class, but maybe the comments will help.

Have a look in Grasshopper.Kernel.Expressions
The class that does all the work is GH_ExpressionParser

You can also use the Grasshopper.Kernel.GH_Convert.ParseExpression function, it probably does what you need.

--
David Rutten
david@mcneel.com
Poprad, Slovakia

Permalink Reply by David Rutten on February 20, 2010 at 12:12pm

Just in case GH_Convert.ParseExpression doesn't do what you need, here's the contents of that function, it might hold some vital clues to writing your own implementation:

'''
''' Attempts to parse an expression.
'''
''' Expression to parse. ''' If True, and the result of the expression is a String, ''' the result is parsed again until the result is no longer a String or until the expression fails. ''' The result of the (recursive) expression.
Public Shared Function ParseExpression(ByVal exp As String, ByVal bRecursive As Boolean) As IGH_ParserVariant
If (String.IsNullOrEmpty(exp)) Then Return New VAR_Null

Try
exp = Expressions.GH_ExpressionSyntaxWriter.RewriteForEvaluator(exp)

Dim prs As New Kernel.Expressions.GH_ExpressionParser
Dim res As IGH_ParserVariant = prs.Evaluate(exp)

If (Not bRecursive) Then
If (res Is Nothing) Then res = New VAR_Null
Return res
End If

If (res.VariantType = GH_VariantType.String) Then
'attempt recursive parsing
Dim res2 As IGH_ParserVariant = ParseExpression(res.ToString(), True)
If (res2 Is Nothing) Then Return res
Return res2

Else
If (res Is Nothing) Then res = New VAR_Null
Return res
End If

Catch ex As Exception
Return New VAR_Null
End Try
End Function

Note that it is possible to cache the expression symbols, which will (greatly) improve performance if you want to re-evaluate the same expression over and over again. However, the thing is reasonably fast to begin with, so you probably won't need to do this.

--
David Rutten
david@mcneel.com
Poprad, Slovakia

Permalink Reply by Daniel Piker on February 20, 2010 at 1:25pm

Many thanks David, that is great and just what I need.

I'm still a little confused over this business of caching the expression symbols, but maybe it will become clearer once I get started - I'll give it a go and see how I get on.

Daniel

Permalink Reply by David Rutten on February 21, 2010 at 2:23am

Evaluating an expression typically consists of three steps:

1. Rewrite the expression so that the parser understands it. This means replacing a bunch of symbols with other symbols. For example, the parser can only handle operators that consist of a single character. Thus things like NOT and OR have to be replaced with symbols like ¬ and |. It's not a simple replace, since the contents of String are not to be touched. This step is easy to cache, since the input is a single string and the output is also a single string.

2. Create a queue of operations from the Expression. This basically involves solving all the operator precedence levels. This process results in a Queue(Of GH_ParserSymbol), which is a binary representation of the Expression string, where the elements have not only been ordered correctly, but have also already been converted into actual numbers and operator pointers.

3. Evaluate the Symbol Queue. This step typically takes the least time, and it is the only step necessary if all you change is the value of the constants.

Thus, by caching the Queue, you'll only have to perform step 3 over and over again if you want to plot, say, 10*sin(t) for a thousand different values for t.

ps. There is a potential step (let's call it step 0 since it should be performed prior to step 1) you may need to make. The expression always needs to be rewritten for the parser, but sometimes you also want to rewrite the expression for the screen. There are special tags users can add to an expression which get replaced with difficult to reach symbols. For example:

10 * sin(t/˂pi˃)

When this expression is rewritten for the screen, it will result in:

10 * sin(t/π)

If you are potentially dealing with a such a String, you should use the RewriteAll() method on GH_ExpressionSyntaxWriter instead of only RewriteForEvaluator(). Now, I typically perform this step inside the user interface, so the expression string which is stored in any given parameter has already been through step zero.

--
David Rutten
david@mcneel.com
Poprad, Slovakia

Permalink Reply by Daniel Piker on February 21, 2010 at 7:20am

Excellent, got it. Thanks again.

RSS