The Basic Principals of Creating an Expression Evaluator-VBForums
Results 1 to 5 of 5

Thread: The Basic Principals of Creating an Expression Evaluator

  1. #1

    Thread Starter
    Super Moderator dday9's Avatar
    Join Date
    Mar 2011
    Location
    South Louisiana
    Posts
    5,126

    The Basic Principals of Creating an Expression Evaluator

    General Overview
    An expression evaluator is a program that takes in a combination of values and operators as input and the input received is then analyzed and processed based on universal mathematical rules such as the order of operations(PEMDAS or BODMAS). Expression evaluators contain the basic principals of compiler design and they are often created to get a better understanding of those principals.

    There are three main steps in creating a expression evaluator: lexical analysis, syntax analysis, and evaluation. Each step has their own common pitfalls and it's important as a programmer to recognize those pitfalls in order to avoid them. Throughout this tutorial, I will explain the basic principals of creating an expression evaluator and breakdown each step in detail.

    Tokens
    Each major step in creating an expression evaluator uses or returns a series of tokens for the next step to work with. A token is simply a representation of a character in the expression. Take the following expression as an example:
    Code:
    1 + 2
    In that expression we would have 3 total tokens and 2 separate types of tokens. The first token would be a digit token and it's value would be the number 1, the second token would be an operator token and it's value would be the plus sign, and finally the last token would be a digit token and it's value would be the number 2.

    Tokens can be recognized by using regular expressions. In this tutorial, it is assumed that you have a basic understanding of regular expressions or at least a basic understanding of how to apply regular expressions to the programming language that you are using. The following are regular expression patterns used to match the characters that will be used in the expressions:

    Digit Pattern
    Code:
    ^([-+]?(\d*[.])?\d+)$
    Operator Pattern
    Code:
    ^(\+|-|\*|/|\^)$
    Left Parenthesis Pattern
    Code:
    ^(\()$
    Right Parenthesis Pattern
    Code:
    ^(\))$
    I will not go into detail on how the patterns work, but the digit pattern matches any number with optionally a positive or negative sign in front of it as well as a single optional dot to account for double precision floating point. The operator pattern matches the following operators: +, -, *, /, ^. Finally the left and right parenthesis literally match a ( and a ).

    The different characteristics, or properties, of a token which was lightly touched up on earlier are: Name, Pattern, Precedence, and Value. The name property is a text property and it is a description of what the token is. For example using the expression from earlier:
    Code:
    1 + 2
    The first token(the number 1)'s name would be digit because it is a number. The pattern property is also a text property and represents the regular expression pattern used to recognize the character. Using same example, we would set the pattern property of the first token to the digit pattern provided
    Code:
    ^([-+]?(\d*[.])?\d+)$
    The precedence property is a numeric property and only applies to operator tokens. According to the order of operations, addition/subtraction will have a lower precedence to multiplication/division and multiplication/division will have a lower precedence to exponents(power). The last property, value, is a text property and is a literal representation of the token.

    If we were to make every character in the expression used earlier we'd have the following tokens:

    Token1
    Name: Digit
    Pattern: ^([-+]?(\d*[.])?\d+)$
    Precedence: Null or Nothing
    Value: 1

    Token2
    Name: Operator
    Pattern: ^(\+|-|\*|/|\^)$
    Precedence: 1
    Value: +

    Token3
    Name: Digit
    Pattern: ^([-+]?(\d*[.])?\d+)$
    Precedence: Null or Nothing
    Value: 2

    The following is a code representation of a token written in Visual Basic.Net:
    Code:
    Public Class Token
    	
    	Public Property Name As String
    	Public Property Pattern As String
    	Public Property Precedence As Int32
    	Public Property Value As String
    	
    End Class
    Last edited by dday9; Nov 20th, 2014 at 04:59 PM.

  2. #2

    Thread Starter
    Super Moderator dday9's Avatar
    Join Date
    Mar 2011
    Location
    South Louisiana
    Posts
    5,126

    Re: The Basic Principals of Creating an Expression Evaluator

    Lexical Analyzer
    Lexical analysis is the process of converting our characters in the expression into a collection of tokens. The object that performs the lexical analysis is called a lexical analyzer the processes actually that does the analysis is known scanning. The different properties of a lexical analyzer are: Definitions, Error, and Source.

    The definition property is a collection of tokens and represents the different tokens that can possibly be returned after scanning. This is not to say that every token in the definitions will be returned after scanning, it's just the possible tokens that can be returned. The error property represents the error returned after scanning. Hopefully the error property will always be null or nothing! The unique thing with the error property is that depending on what language you are using, it could be a text property or an exception property if it's available. Finally the source property is a text property and it represents the expression that was inputted.

    The process of scanning the source code can be defined as a function that returns a collection of tokens. What is done in the scan function is it first loops through each character in the source and ignores any blank entries, this will be know as our character loop. Inside the character loop, another loop is ran to iterate through each definition we have in the definitions property, this will be known as our definitions loop. Inside the definitions loop, we check if the token's pattern matches the current character we're on in the character loop. If there is a pattern match then we add the token to the tokens collection that will be returned from the function and set the value of the token to the character we're on. Otherwise, if we get to the end of the loop and there is no match then unfortunately there is an error. This error is a syntax error meaning that the character that we're currently on in the character loop is not a parenthesis, digit, or operator. However, if there is no error at the end of the character loop then the collection of tokens that have been added are returned.

    Now something that programmers tend to forget before splitting up the source code into tokens is to account for parenthesis. Typically people will write an expression with parenthesis like this:
    Code:
    (1 + 2)
    As opposed to this:
    Code:
    ( 1 + 2 )
    But the rules as dictated above, it would return an error because (1 and 2) are not valid characters.

    To deal with this, before we split up the tokens, loop through each individual character in the source code. If it's an open parenthesis then add a space after it, if it's a closed parenthesis then add a space before it. However, during this process we can check if an express ends with an open parenthesis or starts with a closed parenthesis and return an error if it does.

    The following is a code representation of a lexical analyzer written in Visual Basic.Net:
    Code:
    Public Class LexicalAnalyzer
        Public Property Definitions As List(Of Token)
        Public Property Exception As Exception
        Public Property Source As String
    
        Public Function Scan() As List(Of Token)
            Dim tokens As List(Of Token) = New List(Of Token)
    
            'Go through each character in the source
            For i As Integer = Me.Source.Length - 1 To 0 Step -1
                'Check if it's a left or right parenthesis
                If Me.Source(i) = "(" Then
                    If i = Me.Source.Length - 1 Then
                        'If the left parenthesis is at the end of the expression, then it's a syntax error
                        Me.Exception = New Exception(String.Format("Syntax Error:{0}'An expression cannot end with an open parenthesis.", _
                                                    Environment.NewLine))
                    Else
                        'Otherwise add a space after the parenthesis
                        Me.Source = Me.Source.Insert(i + 1, " ")
                    End If
                ElseIf Me.Source(i) = ")" Then
                    If i = 0 Then
                        'If the right parenthesis is at the beginning of the expression, then it's a syntax error
                        Me.Exception = New Exception(String.Format("Syntax Error:{0}'An expression cannot start with a closed parenthesis.", _
                                                    Environment.NewLine))
                    Else
                        'Otherwise remove a space after the parenthesis
                        Me.Source = Me.Source.Insert(i, " ")
                    End If
                End If
            Next
    
            For Each item As String In Me.Source.Split({" "}, StringSplitOptions.RemoveEmptyEntries)
                Dim found As Boolean = False
                Dim regex As Text.RegularExpressions.Regex
    
                For Each def As Token In Definitions
                    regex = New Text.RegularExpressions.Regex(def.Pattern)
                    found = regex.IsMatch(item)
    
                    If found Then
                        tokens.Add(def.Clone(item))
                        Exit For
                    End If
                Next
    
                If found = False Then
                    Me.Exception = New Exception(String.Format("Syntax Error:{0}'{1}' is not a parenthesis, operator, or valid number.", _
                                                    Environment.NewLine, item))
                    Return Nothing
                End If
            Next
    
            Return tokens
        End Function
    
        Sub New()
            Me.Definitions = New List(Of Token)
            Me.Exception = Nothing
            Me.Source = String.Empty
        End Sub
    
    End Class
    Last edited by dday9; Nov 20th, 2014 at 06:22 PM.

  3. #3

    Thread Starter
    Super Moderator dday9's Avatar
    Join Date
    Mar 2011
    Location
    South Louisiana
    Posts
    5,126

    Re: The Basic Principals of Creating an Expression Evaluator

    Syntax Analyzer
    The syntax analyzer, also known as a parser, checks to make sure that the tokens received are grammatically correct according to the syntax of the language. Many parsers will build what is known as an abstract syntax tree(AST) or a parse tree, however with this being an expression evaluator we do not need to build an AST or parse tree. Instead the parser will convert the order of the tokens from infix notation to reverse polish notation.

    However, before we do any converting, we should first check to make sure that there are no double operators in the token collection. This is automatically a syntax error because the following expression would be invalid:
    Code:
    1 + + 2
    The way that this is done is by loop through the token collection, backwards to forwards, from the last item all the way to the second item. Inside of the loop simply check if the token that we're currently on in the iteration is a operator and if the operator before it is an operator as well. If they're both operators then return an error.

    Another thing that should be done before we do any converting is to check if the expression starts or ends with an operator. This, again, is syntactically invalid. Take the following two examples:
    Code:
    + 1 - 2
    and
    Code:
    2 + 1 -
    Both are incorrect expressions.

    Now, to continue onto the conversion. Infix notation is the most common arithmetic notation, many of you reading this were probably taught how to solve equations that are in an infix notation. Here is an example:
    Code:
    (1 + 2)
    Reverse polish notation(RPN) is a postfix notation that does not have any brackets and was created by a mathematician in the 1920's by the name of Jan Lukasiewicz. Postfix notation simply means that the operators follow their operands. The example given earlier for infix notation would be represented like this using RPN:
    Code:
    1 2 +
    The reason why you would want to use RPN over infix notation is because with RPN you are able to evaluate the expression reading the tokens from left to right where as with infix notation you'd have to jump around back and forth to account for the order of operations. A method to convert infix notation to RPN is to use the shunting-yard algorithm.

    The shunting-yard algorithm is based around a stack. What it does is store values into a collection and operators/parenthesis into a stack. Eventually the stack will pop out the operator into the value collection. Once everything is said and done, you're left with just the value collection that contains digits and operators. This means that there will be no parenthesis to deal with! The formal steps of the shunting-yard algorithm are:

    1. Loop through each token in the collection returned by the lexical analyzer.
    2. If the token is an operand, then add it to the value collection.
    3. If the token is an operator(a) then
      • While there is an operator(b) of higher or equal precedence than operator(a) at the top of the stack, pop B off the stack and append it to the value collection.
      • Finally push operator(a) into the stack.
    4. If the token is an opening bracket, then push it onto the stack.
    5. If the token is a closing bracket
      • Pop all operators off the stack and add them to the value collection, until the operator at the top of the stack is a opening bracket.
      • Pop the opening bracket off the stack without adding it to the value collection.
    6. Once all of the tokens have been read... If there are still operator tokens in the stack, pop all the operators off of the stack, and add it to the value collection.

    The resulting value collection will be the token collection converted into a RPN format.

    Some common pitfalls of this process is whenever you're working with the while loops, is that you need to check to make sure that the stack is not empty. Otherwise you'll get an error.

    The following is a code representation of a syntax analyzer written in Visual Basic.Net:
    Code:
    Public Class SyntaxAnalyzer
        Public Property Exception As Exception
        Public Property Tokens As List(Of Token)
    
        Public Function ConvertToRPN() As List(Of Token)
            Dim conversionList As List(Of Token) = New List(Of Token)
            Dim conversionStack As Stack(Of Token) = New Stack(Of Token)
    
            'Check if there are any obvious errors before we start the loop
            If Not Me.DoubleOperator AndAlso Not Me.StartOrEndsWithOperator() Then
    
                For i As Integer = 0 To Me.Tokens.Count - 1
                    Dim item As Token = Me.Tokens.Item(i)
    
                    If item.Name = "digit" Then
                        'If the token is an operand, append it to the postfix output
                        conversionList.Add(item)
                    ElseIf item.Name = "operators" Then
                        'If the token(a) is an operator then...
                        'While there is an operator(b) of higher or equal precident than (a) at the top of the stack,
                        'pop (b) off the stack and append it to the output
                        While conversionStack.Count > 0 AndAlso conversionStack.Peek.Precedence >= item.Precedence
                            conversionList.Add(conversionStack.Pop)
                        End While
    
                        'Push (a) onto the stack
                        conversionStack.Push(item)
    
                    ElseIf item.Name = "lParen" Then
                        'If the token is an opening bracket, then push it onto the stack
                        conversionStack.Push(item)
                    Else 'If item.Name ="rParen" Then
    
                        Dim found As Boolean = False
                        While conversionStack.Count > 0 AndAlso found = False
                            If conversionStack.Peek.Name <> "lParen" Then
                                'Pop operators off the stack and append them to the output
                                conversionList.Add(conversionStack.Pop)
                            ElseIf conversionStack.Peek.Name = "lParen" Then
                                'Pop the left parentheses without adding it to the output
                                conversionStack.Pop()
                                found = True
                            End If
                        End While
    
                        'If the left parenthesis was never found then return an error
                        If Not found Then
                            Me.Exception = New Exception(String.Format("Syntax Error:{0}There are too many closed parentheses.", _
                                                      Environment.NewLine))
                            Return Nothing
                        End If
                    End If
                Next
    
                'When all the tokens have been read, if there are still objects in the stack:
                If conversionStack.Count > 0 Then
                    Do
                        If conversionStack.Peek.Name <> "lParen" AndAlso conversionStack.Peek.Name <> "rParen" Then
                            'Pop the operator on the top of the stack and append it to the output
                            conversionList.Add(conversionStack.Pop)
                        Else
                            'There was a parentheses left, which means there were to many left parenthesis
                            Me.Exception = New Exception(String.Format("Syntax Error:{0}There are too many open parentheses.", _
                                                      Environment.NewLine))
                            Return Nothing
                        End If
                    Loop Until conversionStack.Count = 0
                End If
            Else
                'Return nothing, there was an error
                Return Nothing
            End If
    
            Return conversionList
        End Function
    
        Private Function DoubleOperator() As Boolean
            For i As Integer = Me.Tokens.Count - 1 To 1 Step -1
                Dim currentItem As Token = Me.Tokens(i)
                Dim priorItem As Token = Me.Tokens(i - 1)
    
                If currentItem.Name = "operator" AndAlso priorItem.Name = "operator" Then
                    Me.Exception = New Exception(String.Format("Syntax Error:{0}There is a double operator at: {1}{2}.", _
                                                 Environment.NewLine, currentItem.Value, priorItem.Value))
                    Return True
                End If
            Next
    
            Return False
        End Function
    
        Private Function StartOrEndsWithOperator() As Boolean
            If Me.Tokens.First.Name = "operator" Then
                Me.Exception = New Exception(String.Format("Syntax Error:{0}An expression cannot start with a {1}.", _
                                                 Environment.NewLine, Me.Tokens.First.Value))
                Return True
            ElseIf Me.Tokens.Last.Name = "operator" Then
                Me.Exception = New Exception(String.Format("Syntax Error:{0}An expression cannot end with a {1}.", _
                                                 Environment.NewLine, Me.Tokens.First.Value))
                Return True
            End If
    
            Return False
        End Function
    
    End Class
    Last edited by dday9; Nov 20th, 2014 at 06:25 PM.

  4. #4

    Thread Starter
    Super Moderator dday9's Avatar
    Join Date
    Mar 2011
    Location
    South Louisiana
    Posts
    5,126

    Re: The Basic Principals of Creating an Expression Evaluator

    Evaluator
    The final step of the expression evaluator is to evaluate the RPN expression, and arguably the easier step. Just as we used a stack to convert the infix notation to reverse polish notation, a stack is used to evaluate the RPN. The rules are very simple:
    1. Loop through each token
    2. If the token is not an operator then push it to the stack
    3. Otherwise if it is, then...
      • Get the two parts of the equation by popping the top two values off the stack. The second part of the equation will be at the top of the stack and the first part of the equation will be next.
      • Check if the value of the current token.
      • Push a new digit token to the stack, where it's value is equal to the two parts and either added, subtracted, multiplied, divide, or raise to the power


    Once you're finished looping through the entire token collection, the value at the top of the stack is the final value.

    The following is a code representation of a syntax analyzer written in Visual Basic.Net:
    Code:
    Public Class Evaluator
        Public Property Tokens As List(Of Token)
    
        Public Function EvaluateExpression() As Double
            Dim valueStack As Stack(Of Token) = New Stack(Of Token)
    
            For Each t As Token In Me.Tokens
    
                If t.Name <> "operator" Then
                    valueStack.Push(t)
                Else
                    Dim part2 As Double = Double.Parse(valueStack.Pop.Value)
                    Dim part1 As Double = Double.Parse(valueStack.Pop.Value)
    
                    If t.Value = "+" Then
                        valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 + part2).ToString})
                    ElseIf t.Value = "-" Then
                        valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 - part2).ToString})
                    ElseIf t.Value = "*" Then
                        valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 * part2).ToString})
                    ElseIf t.Value = "/" Then
                        valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 / part2).ToString})
                    Else
                        valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 ^ part2).ToString})
                    End If
                End If
    
            Next
    
            Return Double.Parse(valueStack.Pop.Value)
        End Function
    
    End Class
    Last edited by dday9; Nov 20th, 2014 at 06:25 PM.

  5. #5

    Thread Starter
    Super Moderator dday9's Avatar
    Join Date
    Mar 2011
    Location
    South Louisiana
    Posts
    5,126

    Re: The Basic Principals of Creating an Expression Evaluator

    Conclusion
    Now you should have a good understanding of how an expression evaluator works. It splits up a sequence of characters into tokens. Then it parses the tokens and reorders them into a reverse polish notation. Finally it goes through each token and performs each operation one by one. Hopefully I've explained this in a very basic way to were you're able to create your own!

    If you'd like a working version of an expression evaluator, here is one written in Visual Basic.Net:
    Code:
    Option Strict On
    Option Explicit On
    
    Imports ConsoleApplication1.ExpressionEvaluator
    Module Module1
    
        Sub Main()
            Dim lexer As LexicalAnalyzer = New LexicalAnalyzer
            lexer.Definitions = New List(Of Token) From {
                                                        {New Token() With {.Name = "lParen", .Pattern = "^(\()$", .Value = String.Empty}},
                                                        {New Token() With {.Name = "rParen", .Pattern = "^(\))$", .Value = String.Empty}},
                                                        {New Token() With {.Name = "digit", .Pattern = "^([-+]?(\d*[.])?\d+)$", .Value = String.Empty}},
                                                        {New Token() With {.Name = "const", .Pattern = "^(E)$", .Precedence = 0, .Value = Math.E.ToString}},
                                                        {New Token() With {.Name = "const", .Pattern = "^(PI)$", .Precedence = 0, .Value = Math.PI.ToString}},
                                                        {New Token() With {.Name = "operator", .Pattern = "^(\+|-)$", .Precedence = 1, .Value = String.Empty}},
                                                        {New Token() With {.Name = "operator", .Pattern = "^(\*|/)$", .Precedence = 2, .Value = String.Empty}},
                                                        {New Token() With {.Name = "operator", .Pattern = "^(\^)$", .Precedence = 3, .Value = String.Empty}}}
    
            Do
                lexer.Source = Console.ReadLine
    
                If Not String.IsNullOrWhiteSpace(lexer.Source) Then
                    Dim tokens As List(Of Token) = lexer.Scan
                    If tokens IsNot Nothing Then
                        Dim parser As SyntaxAnalyzer = New SyntaxAnalyzer With {.Tokens = tokens}
                        Dim rpn As List(Of Token) = parser.ConvertToRPN
    
                        If rpn IsNot Nothing Then
                            Dim solver As Evaluator = New Evaluator With {.Tokens = rpn}
                            Console.WriteLine(solver.EvaluateExpression.ToString)
                        Else
                            Console.WriteLine()
                            Console.WriteLine(parser.Exception.Message)
                        End If
                    Else
                        Console.WriteLine()
                        Console.WriteLine(lexer.Exception.Message)
                    End If
    
                    Console.ReadLine()
                End If
            Loop
        End Sub
    
    End Module
    
    Namespace ExpressionEvaluator
    
        Public Class Token
    
            Public Property Name As String
            Public Property Pattern As String
            Public Property Precedence As Integer
            Public Property Value As String
    
        End Class
    
        Public Class LexicalAnalyzer
            Public Property Definitions As List(Of Token)
            Public Property Exception As Exception
            Public Property Source As String
    
            Public Function Scan() As List(Of Token)
                Dim tokens As List(Of Token) = New List(Of Token)
    
                'Go through each character in the source
                For i As Integer = Me.Source.Length - 1 To 0 Step -1
                    'Check if it's a left or right parenthesis
                    If Me.Source(i) = "(" Then
                        If i = Me.Source.Length - 1 Then
                            'If the left parenthesis is at the end of the expression, then it's a syntax error
                            Me.Exception = New Exception(String.Format("Syntax Error:{0}'An expression cannot end with an open parenthesis.", _
                                                        Environment.NewLine))
                        Else
                            'Otherwise add a space after the parenthesis
                            Me.Source = Me.Source.Insert(i + 1, " ")
                        End If
                    ElseIf Me.Source(i) = ")" Then
                        If i = 0 Then
                            'If the right parenthesis is at the beginning of the expression, then it's a syntax error
                            Me.Exception = New Exception(String.Format("Syntax Error:{0}'An expression cannot start with a closed parenthesis.", _
                                                        Environment.NewLine))
                        Else
                            'Otherwise remove a space after the parenthesis
                            Me.Source = Me.Source.Insert(i, " ")
                        End If
                    End If
                Next
    
                For Each item As String In Me.Source.Split({" "}, StringSplitOptions.RemoveEmptyEntries)
                    Dim found As Boolean = False
                    Dim regex As Text.RegularExpressions.Regex
    
                    For Each def As Token In Definitions
                        regex = New Text.RegularExpressions.Regex(def.Pattern)
                        found = regex.IsMatch(item)
    
                        If found Then
                            tokens.Add(New Token With {.Name = def.Name, .Pattern = def.Pattern, .Precedence = def.Precedence, .Value = If(Not String.IsNullOrWhiteSpace(def.Value), def.Value, item)})
                            Exit For
                        End If
                    Next
    
                    If found = False Then
                        Me.Exception = New Exception(String.Format("Syntax Error:{0}'{1}' is not a parenthesis, operator, or valid number.", _
                                                        Environment.NewLine, item))
                        Return Nothing
                    End If
                Next
    
                Return tokens
            End Function
    
            Sub New()
                Me.Definitions = New List(Of Token)
                Me.Exception = Nothing
                Me.Source = String.Empty
            End Sub
    
        End Class
    
        Public Class SyntaxAnalyzer
            Public Property Exception As Exception
            Public Property Tokens As List(Of Token)
    
            Public Function ConvertToRPN() As List(Of Token)
                Dim conversionList As List(Of Token) = New List(Of Token)
                Dim conversionStack As Stack(Of Token) = New Stack(Of Token)
    
                'Check if there are any obvious errors before we start the loop
                If Not Me.DoubleOperator AndAlso Not Me.StartOrEndsWithOperator() Then
    
                    For i As Integer = 0 To Me.Tokens.Count - 1
                        Dim item As Token = Me.Tokens.Item(i)
    
                        If item.Name = "digit" OrElse item.Name = "const" Then
                            'If the token is an operand, append it to the postfix output
                            conversionList.Add(item)
                        ElseIf item.Name = "operator" Then
                            'If the token(a) is an operator then...
                            'While there is an operator(b) of higher or equal precident than (a) at the top of the stack,
                            'pop (b) off the stack and append it to the output
                            While conversionStack.Count > 0 AndAlso conversionStack.Peek.Precedence >= item.Precedence
                                conversionList.Add(conversionStack.Pop)
                            End While
    
                            'Push (a) onto the stack
                            conversionStack.Push(item)
    
                        ElseIf item.Name = "lParen" Then
                            'If the token is an opening bracket, then push it onto the stack
                            conversionStack.Push(item)
                        ElseIf item.Name = "rParen" Then
    
                            Dim found As Boolean = False
                            While conversionStack.Count > 0 AndAlso found = False
                                If conversionStack.Peek.Name <> "lParen" Then
                                    'Pop operators off the stack and append them to the output
                                    conversionList.Add(conversionStack.Pop)
                                ElseIf conversionStack.Peek.Name = "lParen" Then
                                    'Pop the left parentheses without adding it to the output
                                    conversionStack.Pop()
                                    found = True
                                End If
                            End While
    
                            'If the left parenthesis was never found then return an error
                            If Not found Then
                                Me.Exception = New Exception(String.Format("Syntax Error:{0}There are too many closed parentheses.", _
                                                          Environment.NewLine))
                                Return Nothing
                            End If
                        End If
                    Next
    
                    'When all the tokens have been read, if there are still objects in the stack:
                    If conversionStack.Count > 0 Then
                        Do
                            If conversionStack.Peek.Name <> "lParen" AndAlso conversionStack.Peek.Name <> "rParen" Then
                                'Pop the operator on the top of the stack and append it to the output
                                conversionList.Add(conversionStack.Pop)
                            Else
                                'There was a parentheses left, which means there were to many left parenthesis
                                Me.Exception = New Exception(String.Format("Syntax Error:{0}There are too many open parentheses.", _
                                                          Environment.NewLine))
                                Return Nothing
                            End If
                        Loop Until conversionStack.Count = 0
                    End If
                Else
                    'Return nothing, there was an error
                    Return Nothing
                End If
    
                Return conversionList
            End Function
    
            Private Function DoubleOperator() As Boolean
                For i As Integer = Me.Tokens.Count - 1 To 1 Step -1
                    Dim currentItem As Token = Me.Tokens(i)
                    Dim priorItem As Token = Me.Tokens(i - 1)
    
                    If currentItem.Name = "operator" AndAlso priorItem.Name = "operator" Then
                        Me.Exception = New Exception(String.Format("Syntax Error:{0}There is a double operator at: {1}{2}.", _
                                                     Environment.NewLine, currentItem.Value, priorItem.Value))
                        Return True
                    End If
                Next
    
                Return False
            End Function
    
            Private Function StartOrEndsWithOperator() As Boolean
                If Me.Tokens.First.Name = "operator" Then
                    Me.Exception = New Exception(String.Format("Syntax Error:{0}An expression cannot start with a {1}.", _
                                                     Environment.NewLine, Me.Tokens.First.Value))
                    Return True
                ElseIf Me.Tokens.Last.Name = "operator" Then
                    Me.Exception = New Exception(String.Format("Syntax Error:{0}An expression cannot end with a {1}.", _
                                                     Environment.NewLine, Me.Tokens.First.Value))
                    Return True
                End If
    
                Return False
            End Function
    
        End Class
    
        Public Class Evaluator
            Public Property Tokens As List(Of Token)
    
            Public Function EvaluateExpression() As Double
                Dim valueStack As Stack(Of Token) = New Stack(Of Token)
    
                For Each t As Token In Me.Tokens
    
                    If t.Name <> "operator" Then
                        valueStack.Push(t)
                    Else
                        Dim part2 As Double = Double.Parse(valueStack.Pop.Value)
                        Dim part1 As Double = Double.Parse(valueStack.Pop.Value)
    
                        If t.Value = "+" Then
                            valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 + part2).ToString})
                        ElseIf t.Value = "-" Then
                            valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 - part2).ToString})
                        ElseIf t.Value = "*" Then
                            valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 * part2).ToString})
                        ElseIf t.Value = "/" Then
                            valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 / part2).ToString})
                        Else
                            valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 ^ part2).ToString})
                        End If
                    End If
    
                Next
    
                Return Double.Parse(valueStack.Pop.Value)
            End Function
    
        End Class
    
    End Namespace
    To compile it, simply start a new console application project and paste the code over any auto generated code.

    Something to notice that I do differently than I what I put in the earlier post is that I create three operator tokens. One for addition/subtraction, one for multiplication/division, and one for exponents. This is so that I can set the precedence properly.
    Last edited by dday9; Nov 21st, 2014 at 03:43 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width

Survey posted by VBForums.