A Math Expression Evaluator

Michael Combs

Rate me:

4.87/5 (57 votes)

31 Mar 2003CPOL6 min read

378K

4.4K

106

Math Expression Evaluator

Download source - 7.70 Kb

Introduction

A mathematical expression evaluator can be a useful piece of code if you often write applications which rely on any kind of scripting. Graphics applications which create composite images from templates, form filling or spreadsheet software which performs configurable calculations based on user input, or data analysis applications that perform calculations on batch data from scripts are just a few that come to my mind.

Some knowledge of lexical analysis, state machines and parsing would be helpful, but not necessary. The brief discussion here and a little experimentation with the code in the debugger, should hopefully provide adequate explanation to at least get started using the code.

Lexical scanning

The first step in evaluating an expression is to identify the individual components, or tokens, of the expression. This evaluator uses a finite state machine based lexical scanner to identify tokens, assigning each a category such as number, operator, punctuation, or function. A state machine uses a set of predefined rules to make transitions between states, based on the current state and input (characters from a buffer). It will eventually reach an end state (let's hope), at which point, end state specific code can be executed. In this case, an end state signals that a token has been found, and end state specific code identifies it within the input buffer and stores it to a list of tokens.

State machines are typically driven by a table like the one below, which is used in the code presented in this article. The state is indicated on each row, and the column is determined by the input character. The end states are those states in which all entries are 1. When one of these end states is reached, the code, having tracked it's start position and it's current position, cuts out the token from the buffer, stores it to a list with an associated type (number, operator, etc.) and then returns to the start state, state one.

For example, lets start with a buffer of "73 " (a space is added as an end marker). The transition would be as follows: From State 1, an input of 7 (number) indicates a move to state 4. From state 4, an input of 3 (number) indicates staying in state 4. From state 4, an input of ' ' (space) indicates a move to state 5. State 5 is the end state for a number. At this point the number 73 has been identified, which would then be stored in a list of tokens.

	Letter	Number	Tab	Space	.	Punctuation	Operator
1	2	4	1	1	4	6	7
2	2	3	3	3	3	3	3
3	1	1	1	1	1	1	1
4	2	4	5	5	4	5	5
5	1	1	1	1	1	1	1
6	1	1	1	1	1	1	1
7	1	1	1	1	1	1	1

You might have noticed a little cheating on the column marked Operator. Ordinarily, each operator might have its own column, directing the state machine when that operator character is input. However, single character operators can be combined, provided that some special handling to set the column correctly, is added to the code. This was done so that new operators could easily be added without any modification to the state table. More on this later.

Parsing and evaluation

Once a list of tokens has been generated, each assigned an appropriate type (operator, number, etc), the expression is parsed and evaluated. Parsing verifies the syntax of the expression, restructures the expression to account for operator precedence and, in this case, also evaluates the expression. This code uses a relatively simple recursive descent parsing algorithm.

Recursive descent parsing is implemented through a series of recursive functions, each function handling a different portion of the syntax of an expression. The virtue of recursive decent parsing is that, it is easy to implement. The primary drawback though is that, the language of the expression, math in this case, is hard coded into the structure of the code. As a consequence, a change in the language often requires that the code itself be modified. There are standard parsing algorithms driven by tables, rather than functions, but typically require additional software to generate portions of the code and the tables, and can require much greater effort to implement.

However, the recursive descent parser used in this code has been written in a manner that will allow language modifications typical of those in math expressions (functions and operators), with no changes to the structure of the code.

Adding new operators and functions

This code handles most of the basic operators and functions normally encountered in an expression. However, adding support for additional operators and functions can be implemented simply.

The recursive descent parsing functions have been coded in a series of levels, each level handling operators of a particular precedence, associativity (left, or right) and what might be referred to as degree (unary, or binary). There are 3 levels of precedence (level1, level2 and level3) for binary, left associative operators. By default, level1 handles addition and subtraction (+,-), level2 handles multiplicative operands (*, /, %, \) and level three handles exponents (^). Adding a new operator at any of these levels requires 2 steps. One is to modify the init_operators function to include a symbol for the new operator, specifying the precedence level and the character denoting the operation. Only single character operators can be added without additional changes to the lexical scanner. The second step is to modify the calc_op function to handle the operation, which should become clear once in the code. Level4 handles right associative unary operators (-, + i.e. negation, etc.) and level5 handles left associative unary operators (! factorials). The process to add new operators at these levels is the same as above.

The addition of functions is equally simple. The new function name must first be added to the m_funcs array which is initialized in the declarations of the mcCalc class. Then the calc_function function must be modified to perform the function operation. Function arguments are passed to the calc_function function in a collection. The parser simple passes in the number of comma delimited values it finds enclosed in parenthesis, following the function. The calc_function function is responsible for removing the number of arguments required for the function, and generating any errors when an incorrect number of arguments is passed. Variable length argument lists can even be implemented by simply indicating the number of function arguments in the first argument.

Points of interest

There are several interesting modifications to this code that could provide additional utility. Variable identifiers and substitution could also be of use to those needing a more thorough evaluation tool. Support for caller defined functions or operators through the use of delegates would be a nice addition for anyone interested in using this code as an external assembly. There are certainly more, and any suggestions or modifications for such are welcome. Hopefully this code will prove useful to you in it's application or at least in it's explanation of some of the principles behind expression evaluation.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By

Michael Combs

Architect

United States

Michael has been developing software for about 19 years primarily in C#, C/C++, Fortran, and Visual Basic. His previous experience includes Internet data services (communication protocols, data storage and GIS) for the mortgage industry, oil platform instrumentation and explosives simulation and testing. He holds a B.S. in astrophysics and computer science. He is currently working for Global Software in Oklahoma City developing law enforcement and emergency services related software.

Comments and Discussions

Re: Thanks it's very useful

Ruprt19-Aug-07 9:09

Ruprt

19-Aug-07 9:09

I agree... simple, functional, comprhensible, implementable. Thumb up!

bug

scalpa983-Nov-06 9:13

scalpa98

3-Nov-06 9:13

I try to use your evaluator to evaluate theese kind of strings : ( 8 * 0.001 ) + ( 5 * 1 ) + ( 5 * 100 ) + ( 5 * 10 ) + ( 1 * 1 000 ) + ( 9 * 0.01 ) + ( 0 * 0.1 ) and i ve got a message telling it's invalid !!!!!!!
I think it's a bug because when i try with a shorter one, it works fine (example : ( 1 * 100 ) + ( 7 * 10 ) + ( 3 * 1 )

quisnam igitur sanus ?

Re: bug

paulhumphris19-Jan-07 4:23

paulhumphris

19-Jan-07 4:23

Problem is the space in your one thousand value.

Should be 1000 not 1 000.

The space makes it think it is dealing with two numbers without an operator, clearly an Invalid Expression.

Rounding The Answer.

mshariq5-Oct-06 0:35

mshariq

5-Oct-06 0:35

I f I m using Math.Round(,0), then it will give the answer of 25.5 to 25 instead of 26. How this problem cann't be saved?

Congratulation

snort11-Sep-06 22:20

snort

11-Sep-06 22:20

I dont understand anything to ur code but it works greatly Smile | :)

I needed this to implement a skin motor in my media center: www.mydomotix.com

Thanks again Smile | :)

Olixelle

Please Help, just trying to add an X

Brad Galloway4-Sep-06 15:00

Brad Galloway

4-Sep-06 15:00

I'm having trouble adding a single variable into this code. I need to add an X value into the code which will be known when the code runs, so it will need to be passed as into the function. Please help.

The langauge all programmers know best is profanity.

Re: Please Help, just trying to add an X [modified]

nim5220-Sep-06 10:33

nim52

20-Sep-06 10:33

I built an interface to this calculator over a year ago that lets you type in variables. You can type in "X" or "Bills" or "Crazy Something" or anything pretty much that isn't a number and it will treat it as a variable unless its a function like sqrt().

Check out PoolwarePack at planet source code. It contains 10 programs, the one you want is called SciONE_Calculator.

EXP and Error Handling

Peter Verijke7-Jun-06 10:25

Peter Verijke

7-Jun-06 10:25

Hi,

Very nice piece of code. Big Grin | :-D

I altered it a bit with the code from the previous posts and changed a few things.
- Bugfixed of previous posts in this forum (Also Globalization support)
- support for EXP.
- Don't allow punctuation, as this is prawn to error.
If you would set CultureInfo to use comma as decimal point an you enter by accident a point in your formula, then the code just skiped the point. So 2*2.5 would result in 50.
Now the code will throw an exception, wich is better IMHO.
- Change in the class and the test Code, to work with exceptions instead of messagebox in Class.

I hope this helps to get to a better solution for everybody.

Hereby the code

Class:

<br />
Option Strict On<br />
Imports System.Globalization<br />
Imports System.Threading<br />
<br />
Public Class mcCalc<br />
<br />
    Private Class mcSymbol<br />
        Implements IComparer<br />
<br />
        Public Token As String<br />
        Public Cls As mcCalc.TOKENCLASS<br />
        Public PrecedenceLevel As PRECEDENCE<br />
        Public tag As String<br />
<br />
        Public Delegate Function compare_function(ByVal x As Object, ByVal y As Object) As Integer<br />
<br />
        Public Overridable Overloads Function compare(ByVal x As Object, ByVal y As Object) As Integer Implements IComparer.Compare<br />
<br />
            Dim asym, bsym As mcSymbol<br />
            asym = CType(x, mcSymbol)<br />
            bsym = CType(y, mcSymbol)<br />
<br />
<br />
            If asym.Token > bsym.Token Then Return 1<br />
<br />
            If asym.Token < bsym.Token Then Return -1<br />
<br />
            If asym.PrecedenceLevel = -1 Or bsym.PrecedenceLevel = -1 Then Return 0<br />
<br />
            If asym.PrecedenceLevel > bsym.PrecedenceLevel Then Return 1<br />
<br />
            If asym.PrecedenceLevel < bsym.PrecedenceLevel Then Return -1<br />
<br />
            Return 0<br />
<br />
        End Function<br />
<br />
    End Class<br />
<br />
    Private Enum PRECEDENCE<br />
        NONE = 0<br />
        LEVEL0 = 1<br />
        LEVEL1 = 2<br />
        LEVEL2 = 3<br />
        LEVEL3 = 4<br />
        LEVEL4 = 5<br />
        LEVEL5 = 6<br />
    End Enum<br />
<br />
    Private Enum TOKENCLASS<br />
        KEYWORD = 1<br />
        IDENTIFIER = 2<br />
        NUMBER = 3<br />
        OPERATOR = 4<br />
        PUNCTUATION = 5<br />
    End Enum<br />
<br />
    Private m_tokens As Collection<br />
    Private m_State(,) As Integer<br />
    Private m_KeyWords() As String<br />
    Private m_colstring As String<br />
    Private Const ALPHA As String = "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"<br />
    Private Const DIGITS As String = "#0123456789"<br />
<br />
    Private m_funcs() As String = {"sin", "cos", "tan", "arcsin", "arccos", _<br />
                                 "arctan", "sqrt", "max", "min", "floor", _<br />
                                 "ceiling", "log", "log10", "ln", _<br />
                                 "exp", "round", "abs", "neg", "pos"}<br />
<br />
    Private m_operators As ArrayList<br />
<br />
    Private m_stack As New Stack()<br />
<br />
    Private Sub init_operators()<br />
<br />
        Dim op As mcSymbol<br />
<br />
        m_operators = New ArrayList()<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "-"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL1<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "+"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL1<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "*"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL2<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "/"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL2<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "\"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL2<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "%"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL2<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "^"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL3<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "!"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL5<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "&"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL5<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "-"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL4<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "+"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL4<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = "("<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL5<br />
        m_operators.Add(op)<br />
<br />
        op = New mcSymbol()<br />
        op.Token = ")"<br />
        op.Cls = TOKENCLASS.OPERATOR<br />
        op.PrecedenceLevel = PRECEDENCE.LEVEL0<br />
        m_operators.Add(op)<br />
<br />
        m_operators.Sort(op)<br />
    End Sub<br />
<br />
<br />
    Public Function evaluate(ByVal expression As String) As Double<br />
        Dim symbols As Queue<br />
<br />
        Try<br />
            If IsNumeric(expression) Then Return CType(expression, Double)<br />
<br />
            calc_scan(expression, symbols)<br />
<br />
            Return level0(symbols)<br />
<br />
        Catch ex As Exception<br />
<br />
            Throw New System.Exception(ex.Message)<br />
<br />
        End Try<br />
<br />
    End Function<br />
<br />
    Private Function calc_op(ByVal op As mcSymbol, ByVal operand1 As Double, Optional ByVal operand2 As Double = Nothing) As Double<br />
<br />
<br />
        Select Case op.Token.ToLower<br />
<br />
            Case "&" ' sample to show addition of custom operator<br />
                Return 5<br />
<br />
            Case "^"<br />
                Return (operand1 ^ operand2)<br />
<br />
            Case "+"<br />
<br />
                Select Case op.PrecedenceLevel<br />
                    Case PRECEDENCE.LEVEL1<br />
                        Return (operand2 + operand1)<br />
                    Case PRECEDENCE.LEVEL4<br />
                        Return operand1<br />
                End Select<br />
<br />
            Case "-"<br />
                Select Case op.PrecedenceLevel<br />
                    Case PRECEDENCE.LEVEL1<br />
                        Return (operand1 - operand2)<br />
                    Case PRECEDENCE.LEVEL4<br />
                        Return -1 * operand1<br />
                End Select<br />
<br />
<br />
            Case "*"<br />
                Return (operand2 * operand1)<br />
<br />
            Case "/"<br />
                Return (operand1 / operand2)<br />
<br />
            Case "\"<br />
                Return (CLng(operand1) \ CLng(operand2))<br />
<br />
            Case "%"<br />
                Return (operand1 Mod operand2)<br />
<br />
            Case "!"<br />
                Dim i As Integer<br />
                Dim res As Double = 1<br />
<br />
                If operand1 > 1 Then<br />
                    For i = CInt(operand1) To 1 Step -1<br />
                        res = res * i<br />
                    Next<br />
<br />
                End If<br />
                Return (res)<br />
<br />
        End Select<br />
<br />
    End Function<br />
<br />
    Private Function calc_function(ByVal func As String, ByVal args As Collection) As Double<br />
<br />
        Select Case func.ToLower<br />
<br />
            Case "cos"<br />
                Return (Math.Cos(CDbl(args(1))))<br />
<br />
            Case "sin"<br />
                Return (Math.Sin(CDbl(args(1))))<br />
<br />
            Case "tan"<br />
                Return (Math.Tan(CDbl(args(1))))<br />
<br />
            Case "floor"<br />
                Return (Math.Floor(CDbl(args(1))))<br />
<br />
            Case "ceiling"<br />
                Return (Math.Ceiling(CDbl(args(1))))<br />
<br />
            Case "max"<br />
                Return (Math.Max(CDbl(args(1)), CDbl(args(2))))<br />
<br />
            Case "min"<br />
                Return (Math.Min(CDbl(args(1)), CDbl(args(2))))<br />
<br />
            Case "arcsin"<br />
                Return (Math.Asin(CDbl(args(1))))<br />
<br />
<br />
            Case "arccos"<br />
                Return (Math.Acos(CDbl(args(1))))<br />
<br />
            Case "arctan"<br />
                Return (Math.Atan(CDbl(args(1))))<br />
<br />
<br />
            Case "sqrt"<br />
                Return (Math.Sqrt(CDbl(args(1))))<br />
<br />
            Case "log"<br />
                Return (Math.Log10(CDbl(args(1))))<br />
<br />
<br />
            Case "log10"<br />
                Return (Math.Log10(CDbl(args(1))))<br />
<br />
<br />
            Case "abs"<br />
                Return (Math.Abs(CDbl(args(1))))<br />
<br />
<br />
            Case "round"<br />
                Return (Math.Round(CDbl(args(1))))<br />
<br />
            Case "ln"<br />
                Return (Math.Log(CDbl(args(1))))<br />
<br />
            Case "exp"<br />
                Return (Math.Exp(CDbl(args(1))))<br />
<br />
            Case "neg"<br />
                Return (-1 * CDbl(args(1)))<br />
<br />
            Case "pos"<br />
                Return (+1 * CDbl(args(1)))<br />
<br />
        End Select<br />
<br />
    End Function<br />
<br />
    Private Function identifier(ByVal token As String) As Double<br />
<br />
        Select Case token.ToLower<br />
<br />
            Case "e"<br />
                Return Math.E<br />
            Case "pi"<br />
                Return Math.PI<br />
            Case Else<br />
                ' look in symbol table....?<br />
        End Select<br />
    End Function<br />
<br />
    Private Function is_operator(ByVal token As String, Optional ByVal level As PRECEDENCE = CType(-1, PRECEDENCE), Optional ByRef operator As mcSymbol = Nothing) As Boolean<br />
<br />
        Try<br />
            Dim op As New mcSymbol()<br />
            op.Token = token<br />
            op.PrecedenceLevel = level<br />
            op.tag = "test"<br />
<br />
            Dim ir As Integer = m_operators.BinarySearch(op, op)<br />
<br />
            If ir > -1 Then<br />
<br />
                operator = CType(m_operators(ir), mcSymbol)<br />
                Return True<br />
            End If<br />
<br />
            Return False<br />
<br />
        Catch<br />
            Return False<br />
        End Try<br />
    End Function<br />
<br />
    Private Function is_function(ByVal token As String) As Boolean<br />
<br />
        Try<br />
            Dim lr As Integer = Array.BinarySearch(m_funcs, token.ToLower)<br />
<br />
            Return (lr > -1)<br />
<br />
        Catch<br />
            Return False<br />
        End Try<br />
<br />
    End Function<br />
<br />
<br />
    Public Function calc_scan(ByVal line As String, ByRef symbols As Queue) As Boolean<br />
<br />
        Dim sp As Integer  ' start position marker<br />
        Dim cp As Integer  ' current position marker<br />
        Dim col As Integer ' input column<br />
        Dim lex_state As Integer<br />
        Dim cls As TOKENCLASS<br />
        Dim cc As Char<br />
        Dim token As String<br />
<br />
        symbols = New Queue()<br />
<br />
        line = line & " " ' add a space as an end marker<br />
<br />
        sp = 0<br />
        cp = 0<br />
        lex_state = 1<br />
<br />
<br />
        Do While cp <= line.Length - 1<br />
<br />
            cc = line.Chars(cp)<br />
<br />
            ' if cc is not found then IndexOf returns -1 giving col = 2.<br />
            col = m_colstring.IndexOf(cc) + 3<br />
<br />
            ' set the input column <br />
            Select Case col<br />
<br />
                Case 2 ' cc wasn't found in the column string<br />
<br />
                    If ALPHA.IndexOf(Char.ToUpper(cc)) > 0 Then      ' letter column?<br />
                        col = 1<br />
                    ElseIf DIGITS.IndexOf(Char.ToUpper(cc)) > 0 Then ' number column?<br />
                        col = 2<br />
                    Else ' everything else is assigned to the punctuation column<br />
                        'col = 6<br />
                        Throw New System.Exception("Invalid character in expression '" & cc & "'")<br />
                    End If<br />
<br />
                Case Is > 5 ' cc was found and is > 5 so must be in operator column<br />
                    col = 7<br />
<br />
                    ' case else ' cc was found - col contains the correct column<br />
<br />
            End Select<br />
<br />
            ' find the new state based on current state and column (determined by input)<br />
            lex_state = m_State(lex_state - 1, col - 1)<br />
<br />
            Select Case lex_state<br />
<br />
                Case 3 ' function or variable  end state <br />
<br />
                    ' TODO variables aren't supported but substitution <br />
                    '      could easily be performed here or after<br />
                    '      tokenization<br />
<br />
                    Dim sym As New mcSymbol()<br />
<br />
                    sym.Token = line.Substring(sp, cp - sp)<br />
                    If is_function(sym.Token) Then<br />
                        sym.Cls = TOKENCLASS.KEYWORD<br />
                    Else<br />
                        sym.Cls = TOKENCLASS.IDENTIFIER<br />
                    End If<br />
<br />
                    symbols.Enqueue(sym)<br />
<br />
                    lex_state = 1<br />
                    cp = cp - 1<br />
<br />
                Case 5 ' number end state<br />
                    Dim sym As New mcSymbol()<br />
<br />
                    sym.Token = line.Substring(sp, cp - sp)<br />
                    sym.Cls = TOKENCLASS.NUMBER<br />
<br />
                    symbols.Enqueue(sym)<br />
<br />
                    lex_state = 1<br />
                    cp = cp - 1<br />
<br />
                Case 6 ' punctuation end state<br />
                    Dim sym As New mcSymbol()<br />
<br />
                    sym.Token = line.Substring(sp, cp - sp + 1)<br />
                    sym.Cls = TOKENCLASS.PUNCTUATION<br />
<br />
                    symbols.Enqueue(sym)<br />
<br />
                    lex_state = 1<br />
<br />
                Case 7 ' operator end state<br />
<br />
                    Dim sym As New mcSymbol()<br />
<br />
                    sym.Token = line.Substring(sp, cp - sp + 1)<br />
                    sym.Cls = TOKENCLASS.OPERATOR<br />
<br />
                    symbols.Enqueue(sym)<br />
<br />
                    lex_state = 1<br />
<br />
            End Select<br />
<br />
            cp += 1<br />
            If lex_state = 1 Then sp = cp<br />
<br />
        Loop<br />
<br />
        Return True<br />
<br />
    End Function<br />
<br />
    Private Sub init()<br />
<br />
        Dim op As mcSymbol<br />
<br />
        Dim state(,) As Integer = {{2, 4, 1, 1, 4, 6, 7}, _<br />
                                   {2, 2, 3, 3, 3, 3, 3}, _<br />
                                   {1, 1, 1, 1, 1, 1, 1}, _<br />
                                   {2, 4, 5, 5, 4, 5, 5}, _<br />
                                   {1, 1, 1, 1, 1, 1, 1}, _<br />
                                   {1, 1, 1, 1, 1, 1, 1}, _<br />
                                   {1, 1, 1, 1, 1, 1, 1}}<br />
<br />
        Thread.CurrentThread.CurrentCulture = New CultureInfo("nl-BE")<br />
        'Thread.CurrentThread.CurrentCulture = New CultureInfo("en-US")<br />
<br />
        init_operators()<br />
<br />
        m_State = state<br />
        'm_colstring = Chr(9) & " " & ".()"<br />
        m_colstring = Chr(9) + " " + System.Globalization.CultureInfo.CurrentCulture.NumberFormat.CurrencyDecimalSeparator() + "()"<br />
        For Each op In m_operators<br />
            m_colstring = m_colstring & op.Token<br />
        Next<br />
<br />
        Array.Sort(m_funcs)<br />
        m_tokens = New Collection()<br />
<br />
    End Sub<br />
<br />
<br />
    Public Sub New()<br />
<br />
        init()<br />
<br />
    End Sub<br />
<br />
#Region "Recusrsive Descent Parsing Functions"<br />
<br />
<br />
<br />
    Private Function level0(ByRef tokens As Queue) As Double<br />
<br />
        Return level1(tokens)<br />
<br />
    End Function<br />
<br />
<br />
    Private Function level1_prime(ByRef tokens As Queue, ByVal result As Double) As Double<br />
<br />
        Dim symbol, operator As mcSymbol<br />
<br />
        If tokens.Count > 0 Then<br />
            symbol = CType(tokens.Peek, mcSymbol)<br />
        Else<br />
            Return result<br />
        End If<br />
<br />
        ' binary level1 precedence operators....+, -<br />
        If is_operator(symbol.Token, PRECEDENCE.LEVEL1, operator) Then<br />
<br />
            tokens.Dequeue()<br />
            result = calc_op(operator, result, level2(tokens))<br />
            result = level1_prime(tokens, result)<br />
<br />
        End If<br />
<br />
<br />
        Return result<br />
<br />
    End Function<br />
<br />
    Private Function level1(ByRef tokens As Queue) As Double<br />
<br />
        Return level1_prime(tokens, level2(tokens))<br />
<br />
    End Function<br />
<br />
    Private Function level2(ByRef tokens As Queue) As Double<br />
<br />
        Return level2_prime(tokens, level3(tokens))<br />
    End Function<br />
<br />
    Private Function level2_prime(ByRef tokens As Queue, ByVal result As Double) As Double<br />
<br />
        Dim symbol, operator As mcSymbol<br />
<br />
        If tokens.Count > 0 Then<br />
            symbol = CType(tokens.Peek, mcSymbol)<br />
        Else<br />
            Return result<br />
        End If<br />
<br />
        ' binary level2 precedence operators....*, /, \, %<br />
<br />
        If is_operator(symbol.Token, PRECEDENCE.LEVEL2, operator) Then<br />
<br />
            tokens.Dequeue()<br />
            result = calc_op(operator, result, level3(tokens))<br />
            result = level2_prime(tokens, result)<br />
<br />
        End If<br />
<br />
        Return result<br />
<br />
    End Function<br />
<br />
    Private Function level3(ByRef tokens As Queue) As Double<br />
<br />
        Return level3_prime(tokens, level4(tokens))<br />
<br />
    End Function<br />
<br />
    Private Function level3_prime(ByRef tokens As Queue, ByVal result As Double) As Double<br />
<br />
        Dim symbol, operator As mcSymbol<br />
<br />
        If tokens.Count > 0 Then<br />
            symbol = CType(tokens.Peek, mcSymbol)<br />
        Else<br />
            Return result<br />
        End If<br />
<br />
        ' binary level3 precedence operators....^<br />
<br />
        If is_operator(symbol.Token, PRECEDENCE.LEVEL3, operator) Then<br />
<br />
            tokens.Dequeue()<br />
            result = calc_op(operator, result, level4(tokens))<br />
            result = level3_prime(tokens, result)<br />
<br />
        End If<br />
<br />
<br />
        Return result<br />
<br />
    End Function<br />
<br />
    Private Function level4(ByRef tokens As Queue) As Double<br />
<br />
        Return level4_prime(tokens)<br />
    End Function<br />
<br />
    Private Function level4_prime(ByRef tokens As Queue) As Double<br />
<br />
        Dim symbol, operator As mcSymbol<br />
<br />
        If tokens.Count > 0 Then<br />
            symbol = CType(tokens.Peek, mcSymbol)<br />
        Else<br />
            Throw New System.Exception("Invalid expression.")<br />
        End If<br />
<br />
        ' unary level4 precedence right associative  operators.... +, -<br />
<br />
        If is_operator(symbol.Token, PRECEDENCE.LEVEL4, operator) Then<br />
<br />
            tokens.Dequeue()<br />
            Return calc_op(operator, level5(tokens))<br />
        Else<br />
            Return level5(tokens)<br />
        End If<br />
<br />
<br />
    End Function<br />
<br />
    Private Function level5(ByVal tokens As Queue) As Double<br />
<br />
        Return level5_prime(tokens, level6(tokens))<br />
<br />
    End Function<br />
<br />
    Private Function level5_prime(ByVal tokens As Queue, ByVal result As Double) As Double<br />
<br />
        Dim symbol, operator As mcSymbol<br />
<br />
        If tokens.Count > 0 Then<br />
            symbol = CType(tokens.Peek, mcSymbol)<br />
        Else<br />
            Return result<br />
        End If<br />
<br />
        ' unary level5 precedence left associative operators.... !<br />
<br />
        If is_operator(symbol.Token, PRECEDENCE.LEVEL5, operator) Then<br />
<br />
            tokens.Dequeue()<br />
            Return calc_op(operator, result)<br />
<br />
        Else<br />
            Return result<br />
        End If<br />
<br />
    End Function<br />
<br />
    Private Function level6(ByRef tokens As Queue) As Double<br />
<br />
        Dim symbol As mcSymbol<br />
<br />
        If tokens.Count > 0 Then<br />
            symbol = CType(tokens.Peek, mcSymbol)<br />
        Else<br />
            Throw New System.Exception("Invalid expression.")<br />
            Return 0<br />
        End If<br />
<br />
        Dim val As Double<br />
<br />
<br />
        ' constants, identifiers, keywords, -> expressions<br />
        If symbol.Token = "(" Then ' opening paren of new expression<br />
<br />
            tokens.Dequeue()<br />
            val = level0(tokens)<br />
<br />
            symbol = CType(tokens.Dequeue, mcSymbol)<br />
            ' closing paren<br />
            If symbol.Token <> ")" Then Throw New System.Exception("Invalid expression.")<br />
<br />
            Return val<br />
        Else<br />
<br />
            Select Case symbol.Cls<br />
<br />
                Case TOKENCLASS.IDENTIFIER<br />
                    tokens.Dequeue()<br />
                    Return identifier(symbol.Token)<br />
<br />
                Case TOKENCLASS.KEYWORD<br />
                    tokens.Dequeue()<br />
                    Return calc_function(symbol.Token, arguments(tokens))<br />
                Case TOKENCLASS.NUMBER<br />
<br />
                    tokens.Dequeue()<br />
                    m_stack.Push(CDbl(symbol.Token))<br />
                    Return CDbl(symbol.Token)<br />
<br />
                Case Else<br />
                    Throw New System.Exception("Invalid expression.")<br />
            End Select<br />
        End If<br />
<br />
<br />
    End Function<br />
<br />
    Private Function arguments(ByVal tokens As Queue) As Collection<br />
<br />
        Dim symbol As mcSymbol<br />
        Dim args As New Collection()<br />
<br />
        If tokens.Count > 0 Then<br />
            symbol = CType(tokens.Peek, mcSymbol)<br />
        Else<br />
            Throw New System.Exception("Invalid expression.")<br />
            Return Nothing<br />
        End If<br />
<br />
        Dim val As Double<br />
<br />
        If symbol.Token = "(" Then<br />
<br />
            tokens.Dequeue()<br />
            args.Add(level0(tokens))<br />
<br />
            symbol = CType(tokens.Dequeue, mcSymbol)<br />
            Do While symbol.Token <> ")"    <br />
<br />
                If symbol.Token = "," Then<br />
                    args.Add(level0(tokens))<br />
                Else<br />
                    Throw New System.Exception("Invalid expression.")<br />
                    Return Nothing<br />
                End If<br />
                symbol = CType(tokens.Dequeue, mcSymbol)<br />
            Loop<br />
<br />
            Return args<br />
        Else<br />
            Throw New System.Exception("Invalid expression.")<br />
            Return Nothing<br />
        End If<br />
<br />
    End Function<br />
<br />
#End Region<br />
<br />
<br />
End Class<br />

Test Code (cmdEvaluate_Click)

<br />
    Private Sub cmdEvaluate_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdEvaluate.Click<br />
<br />
        Dim calc As New mcCalc()<br />
        Try<br />
            MsgBox("The answer is " & calc.evaluate(txtExpression.Text), , "Expression Evaluation Test")<br />
<br />
        Catch ex As Exception<br />
            MsgBox("Error " & ex.Message, , "Expression Evaluation Error")<br />
<br />
        End Try<br />
<br />
    End Sub<br />

Peter Verijke

Extending the Parser to Simplify Expressions

JasonSG26-Nov-05 10:25

JasonSG

26-Nov-05 10:25

I am trying to extend your parser to give expressions in simplesest exact form in addition to an approximate value. For instance, I want it to give the string "pi" for arcsin(sin(sqrt(ln(e^pi))^2)), and e^pi for arcsin(sin(sqrt(e^pi)^2)). Is there any simple way to do this with lexical scanning. My code is extremely complicated (and unwieldly and large), probobly buggy, and I am stuck on a portion of it. I was wonerering if there was an eaiser way to do this. I also wrote in support for complex numbers (this worked).

Additional Functions

JasonSG25-Nov-05 7:48

JasonSG

25-Nov-05 7:48

I was wondering if it is possible to add support for funtions such as summation to the parser (without rewriting much of the code). For example, (for summation) it would evaluate sum(x,1,5,e+pi+x) by taking the sum of e+pi+x for every integral value of x from 1 to 5.

Code extension: Formulas with variables inside

Panzermeyer18-Aug-05 2:09

Panzermeyer

18-Aug-05 2:09

In order to work with formulas like
Dim Area As String = "Width*Length"
I wrote an extension to replace the words by numbers before evalutating them:

Private Variables As ArrayList 'place the line at the beginning of the class

Public Sub New()
Me.Variables = New ArrayList 'this line is the addition
init()
End Sub

'this function is used to define variables
Public Function AddVariable(ByVal Name As String, ByVal Value As Double)
Dim vp As New ValuePair(Name, Value)
Me.Variables.Add(vp)
End Function

'some additions before the evaluating gets started
Public Function evaluate(ByVal expression As String) As Double
'first replace all defined variables by their value
For i = 0 To Me.Variables.Count - 1
If Expression.IndexOf(Me.Variables.Item(i).Variable) > 0 Then
Expression = Expression.Replace(Me.Variables.Item(i).Variable, Me.Variables.Item(i).Value)
End If
Next
'... the rest stayed the same
End Function

'a new class (place it after the mccalc-class)
Public Class ValuePair
Public Variable As String
Public Value As Double
Public Sub New(ByVal Variable As String, ByVal Value As Double)
Me.Variable = Variable
Me.Value = Value
End Sub
End Class

There's only one problem:
if you use two variables, which begin with the same letters, you have
to add the longer one first!!
Otherwise you could encounter some trouble.

Example:
Original: "Ship+ShipmentCharge"
Formula1.AddVariable("Ship", 4)
Formula1.AddVariable("ShipmentCharge", 35)
Replaced: "4+4mentCharge"

Another tiny thing I have to mention is, that it can be up to three times
faster to write the replace-lines "by hand":

Dim Calculation As String = "Width*Length"
Calculation = Calculation.Replace("Width", 4)
Calculation = Calculation.Replace("Length", 12)

instead of

Formula.AddVariable(Width, 4)
Formula.AddVariable(Length, 12)

The manual replacement reduces the function calls inside the class to
a minimum. But for calculations below hundred formulas it doesn't matter.

I hope I could help some people with the code Smile | :)

I enjoyed the expression evaluator very much!
I compared it to my own CODEDOM-Evaluator and
the speed of mccalc is about 10 to 1000 times faster!!

IIf statements...

JPamental27-Jul-05 8:39

JPamental

27-Jul-05 8:39

I am about to give this a shot, but frankly I don't really have a good understanding of how this should work - can this be set up to evaluate conditional statements? (i.e. 5*(IIf(6<7.5,3,5)) should evaluate to 15)

Thanks for any help you can provide!

Jason
(likewise if I sort it out I'll post it back if you like)

Re: IIf statements...

jokiz25-Sep-06 16:54

jokiz

25-Sep-06 16:54

since the calculations returns double, you can have the boolean returns to treat just zero and non-zero values just like excel. you just have to define your iif function which accepts three arguments

(x-a)(x-b)(x-c)...(x-z)

What should I do if...

viettho4-Jun-04 8:34

viettho

4-Jun-04 8:34

How should I modify the code if the input is:
CT > 5 and UC < 30, where CT and UC are variable.

Thanks for helping.

Readability Suggestions

JimHugh2-Feb-04 9:55

JimHugh

2-Feb-04 9:55

In the interest of optimization and readability, I would suggest modifying Class mcSymbol by adding the following three New Functions:

Public Sub New()

End Sub

Public Sub New(ByVal vToken As String, ByVal vTokenClass As TOKENCLASS, ByVal vPrecedenceLevel As PRECEDENCE)
Token = vToken
Cls = vTokenClass
PrecedenceLevel = vPrecedenceLevel
End Sub

Public Sub New(ByVal vToken As String, ByVal vTokenClass As TOKENCLASS, ByVal vPrecedenceLevel As PRECEDENCE, ByVal vTag As String)
Token = vToken
Cls = vTokenClass
PrecedenceLevel = vPrecedenceLevel
tag = vTag
End Sub

'And modifying mcCalc.init_operators as follows:

Private Sub init_operators()
m_operators = New ArrayList
m_operators.Add(New mcSymbol("-", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL1))
m_operators.Add(New mcSymbol("+", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL1))
m_operators.Add(New mcSymbol("*", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL2))
m_operators.Add(New mcSymbol("/", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL2))
m_operators.Add(New mcSymbol("\", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL2))
m_operators.Add(New mcSymbol("%", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL2))
m_operators.Add(New mcSymbol("^", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL3))
m_operators.Add(New mcSymbol("!", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL5))
m_operators.Add(New mcSymbol("&", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL5))
m_operators.Add(New mcSymbol("-", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL4))
m_operators.Add(New mcSymbol("+", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL4))
m_operators.Add(New mcSymbol("(", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL5))
Dim op As mcSymbol = New mcSymbol(")", TOKENCLASS.OPERATOR, PRECEDENCE.LEVEL0)
m_operators.Add(op)
m_operators.Sort(op)
End Sub

Private Function is_operator(ByVal token As String, Optional ByVal level As PRECEDENCE = CType(-1, PRECEDENCE), Optional ByRef operator As mcSymbol = Nothing) As Boolean

Try
Dim op As New mcSymbol(token, TOKENCLASS.OPERATOR, level, "test")

Dim ir As Integer = m_operators.BinarySearch(op, op)

If ir > -1 Then

operator = CType(m_operators(ir), mcSymbol)
Return True
End If

Return False

Catch
Return False
End Try
End Function

Private Function calc_op(ByVal op As mcSymbol, ByVal operand1 As Double, Optional ByVal operand2 As Double = Nothing) As Double

' ToLower is not necessary, no Alpha operators
Select Case op.Token.ToString

Case "&" ' sample to show addition of custom operator
Return 5

Case "^"
Return (operand1 ^ operand2)

Case "+"

Select Case op.PrecedenceLevel
Case PRECEDENCE.LEVEL1
Return (operand2 + operand1)
Case PRECEDENCE.LEVEL4
Return operand1
End Select

Case "-"
Select Case op.PrecedenceLevel
Case PRECEDENCE.LEVEL1
Return (operand1 - operand2)
Case PRECEDENCE.LEVEL4
Return -1 * operand1
End Select

Case "*"
Return (operand2 * operand1)

Case "/"
Return (operand1 / operand2)

Case "\"
Return (CLng(operand1) \ CLng(operand2))

Case "%"
Return (operand1 Mod operand2)

Case "!"
Dim i As Integer
Dim res As Double = 1

If operand1 > 1 Then
For i = CInt(operand1) To 1 Step -1
res = res * i
Next

End If
Return (res)

End Select

End Function

Null value

Member 1289811-Feb-04 7:21

Member 128981

1-Feb-04 7:21

I'd like to add a function "IsNull" that will return "1" if True and "0" if False.
How do I do that?

Also, how do I eliminate the "Nulls" from an "Avg" function?

Many thanks for your help.

GG

Compact Framework Problem "BinarySearch"

carterbarnes13-Jan-04 11:48

carterbarnes

13-Jan-04 11:48

I am trying to make this work with the Compact Framework, but CF doesn't like line 325 Dim ir as Integer = m_operators.BinarySearch(op, op)... I was trying to do some backwards engineering and couldn't figure out what this BinarySearch does... All I can see the containing sub doing is returning a boolean weather it is a operator or not, which I could do a lot easier than the code here... The only problem is the operator argument which is sometimes returned, I am reluctant to just chop code out of here without first finding an explanation or some understanding... Please help me figure this out... Thanks... Confused | :confused:

Carter Barnes
GIS Analyst

Re: Compact Framework Problem "BinarySearch"

Michael Combs14-Jan-04 18:33

Michael Combs

14-Jan-04 18:33

The BinarySearch method searches the m_operators arraylist for the mcSymbol object that is associated with the token passed to the is_operator function. Rather than just determine if the token is an operator the function determines if the token is one of the predefined operators. The search is based on the actual character and the precedence level. Precedence is required because of the ambiguity of some operators (i.e. - is negation and minus). I think your problem is most likely with the IComparer interface. The mcSymbol class implements IComparer. This is used to perform the BinarySearch. The second argument to the BinarySearch method is the IComparer. There is a 'Compare' function on mcSymbol which is used for the search. Place a breakpoint in the Compare function before the BinarySearch is called. This might help you determine what the problem is. I hope this helps. Let me know if I can be of anymore assistance.

-Michael

Re: Compact Framework Problem "BinarySearch"

john_miller_williams24-Feb-04 13:54

john_miller_williams

24-Feb-04 13:54

Just looking at the help files, the CF supports a version of Binary search that looks exactly the same, but also requires the range you want to sort.

So changing the above line to :

Dim ir As Integer = m_operators.BinarySearch(0, m_operators.Count - 1, op, op)

..seems to do the trick.

John M-W

steady decline of memory

Anonymous3-Nov-03 23:11

Anonymous

3-Nov-03 23:11

Hi Michael!

Thanks again for that wonderful piece of code! I have implemented it and it works fine, but i have now found out that it steadily decreases my free memory. Of course, I must be doing something wrong with using it. I know its not your job the give free advise but i would be VERY grateful if you could help me out of this. This is what i do (simplified). I call the Function ABC hundreds of times from a separate class (not shown in the example below) and with each call some additional memory is used. What am I doing wrong? I really just need to get the result then all working variables can be cleared again. Why does my code below use additional ram with every call?

thank you VERY much for your help!

Kind rgds,
Marc

Public Class Main<br />
Public Shared ParseFormula as New mcCalc()<br />
Public Shared Function ABC<br />
Dim dblResult as double<br />
Dim strFormula as string<br />
...<br />
dblresult=parseformula.evaluate(strFormula)<br />
End Function<br />
End Class<br />
<br />
Public Class mcCalc()<br />
<small>' your unamended class</small><br />
end Class

Re: steady decline of memory

Anonymous4-Nov-03 4:07

Anonymous

4-Nov-03 4:07

hi again!

i found the problem. I have changed my code to create the ParseFormula object as a local object within the funtion ABC itself. No more memory problems now as the GC.Collect frees memory nicely now.

Still, a question:

I am using your code thousand of times, usually the same formula 1500 times, then the formula changes and calculates again 1500 times and so on. is there a way i can use your code in a form that evaluates the formula only once, then uses it for 1500 times (with different values), then evaluates the next formulastring (which might have changed in the meantime) and applies that formula again for 1500 times. i think that would speed up things even more.

do you get what i mean, please excuse my english.

kind rgds,
Marc

log10

Serena_Sutton16-Oct-03 3:27

Serena_Sutton

16-Oct-03 3:27

Log10 is in the example but doesnt work when its written as "log10(5)". Any ideas ? Confused | :confused:

Re: log10

Michael Combs16-Oct-03 4:23

Michael Combs

16-Oct-03 4:23

Yes. I found the problem. There is an error in the state table definition. Here is the replacement:

Dim state(,) As Integer = {{2, 4, 1, 1, 4, 6, 7}, _
{2, 2, 3, 3, 3, 3, 3}, _
{1, 1, 1, 1, 1, 1, 1}, _
{2, 4, 5, 5, 4, 5, 5}, _
{1, 1, 1, 1, 1, 1, 1}, _
{1, 1, 1, 1, 1, 1, 1}, _
{1, 1, 1, 1, 1, 1, 1}}

The change is in bold. That error prevented scanning alphanumeric function names. Replace the state definition in the init function with the above and it should work. I'll update the article code soon.

C++

A M Ginsberg24-Aug-03 21:56

A M Ginsberg

24-Aug-03 21:56

Thanks for the article
I have converted it to a C++ version for use in a CAD system
The validation really needs to be better for use in an application

A mispelled function e.g. asb turns up as an identifier

For functions next token should be (

Built in function list should include the number of parameters expected

There is a problem if you have more Right hand parentheses then left - it stops the evaluation but does not signal an error
round would be better as round(value,NoOfDecimalPlaces)

Misplaced , not signalled - especially important in Europe where people are in habit of using , as decimal point

Does not pick up things like ..

Space also terminates without an error e.g 1 3/4 returns 1

I have added a fair amount of validation to my version.

Cannot see why you pushed tokens on to a Stack object - you not need it

decimal numbers?

TheDoc1-Aug-03 9:49

TheDoc

1-Aug-03 9:49

When you enter a number like 2,2 it give's an error. I tried 2.2 but then it calculates the number like 22.

How can I use numbers like 2,2 without getting an error message?

Greetings Guido

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