The Basic Principals of Creating an Expression Evaluator

[dday9]

Chapter 7: Conclusion
And that concludes the expression evaluator. To wrap up all the steps of an expression evaluator you must first format the expression to an unambiguous form, scan the expression and convert the text into tokens, rearrange the tokens from infix notation to reverse polish notation, and then finally solve the expression.

Here is a final version of the code with comments throughout the process:

Module Module1
    Sub Main()
        Do
            Dim source As String = Console.ReadLine
            If Not String.IsNullOrWhiteSpace(source) Then
                Dim format As String = FormatExpression(source)
                Dim rpn() As Token = ShuntingYardAlgorithm(Scan(format))
                Console.WriteLine(Evaluate(rpn))
            End If
        Loop
    End Sub
    Private Function FormatExpression(ByVal expression As String) As String
        'Remove all blanks spaces
        Dim format As String = expression.Replace(" ", String.Empty)

        'Add a space before and after all parenthesis
        format = format.Replace("(", " ( ").Replace(")", " ) ")

        'Add a space before unary operator
        Dim unaryEvaluator As System.Text.RegularExpressions.MatchEvaluator = New System.Text.RegularExpressions.MatchEvaluator(AddressOf ReplaceUnary)
        format = System.Text.RegularExpressions.Regex.Replace(format, "(\+|-|\*|\\|\^)-", unaryEvaluator)

        'Add a space before and after any number
        Dim digitEvaluator As System.Text.RegularExpressions.MatchEvaluator = New System.Text.RegularExpressions.MatchEvaluator(AddressOf ReplaceDigits)
        format = System.Text.RegularExpressions.Regex.Replace(format, "(-?[0-9]+(?:\.[0-9]*)?)", digitEvaluator)

        'Remove any excess whitespace
        format = System.Text.RegularExpressions.Regex.Replace(format, " {2,}", " ")

        'Trim any leading or trailing whitespace
        format = format.Trim()

        Return format
    End Function

    Private Function ReplaceUnary(ByVal m As System.Text.RegularExpressions.Match) As String
        Return " " & m.Value
    End Function

    Private Function ReplaceDigits(ByVal m As System.Text.RegularExpressions.Match) As String
        Return " " & m.Value & " "
    End Function
    Private Function AddNumbers(ByVal operand1 As Double, ByVal operand2 As Double) As Double
        Return operand1 + operand2
    End Function
    Private Function SubtractNumbers(ByVal operand1 As Double, ByVal operand2 As Double) As Double
        Return operand1 - operand2
    End Function
    Private Function MultiplyNumbers(ByVal operand1 As Double, ByVal operand2 As Double) As Double
        Return operand1 * operand2
    End Function
    Private Function DivideNumbers(ByVal operand1 As Double, ByVal operand2 As Double) As Double
        Return operand1 / operand2
    End Function
    Private Function ModuloNumbers(ByVal operand1 As Double, ByVal operand2 As Double) As Double
        Return operand1 Mod operand2
    End Function
    Private Function RaiseNumbers(ByVal operand1 As Double, ByVal operand2 As Double) As Double
        Return operand1 ^ operand2
    End Function
    Private Function Scan(ByVal source As String) As Token()
        'Create the rules of the lexical analyzer
        'Rule 1: Left Parenthesis
        'Rule 2: Right Parenthesis
        'Rule 3: Doubles
        'Rules 4 - 5: Addition and Subtraction, precedence: 1
        'Rules 6 - 8: Multiplication, Division, and MOD, precedence: 2
        'Rule 9: Exponent, precedence: 3
        Dim definitions() As Token = {New Token() With {.Pattern = "^\($", .Type = Token.TokenType.LeftParenthesis, .Value = String.Empty}, _
                         New Token() With {.Pattern = "^\)$", .Type = Token.TokenType.RightParenthesis, .Value = String.Empty}, _
                         New Token() With {.Pattern = "^([-+]?(\d*[.])?\d+)$", .Type = Token.TokenType.Digit, .Value = String.Empty}, _
                         New Token() With {.Operation = New Token.MathOperation(AddressOf AddNumbers), .Pattern = "^\+$", .Precedence = 1, .Type = Token.TokenType.Operator, .Value = String.Empty}, _
                         New Token() With {.Operation = New Token.MathOperation(AddressOf SubtractNumbers), .Pattern = "^-$", .Precedence = 1, .Type = Token.TokenType.Operator, .Value = String.Empty}, _
                         New Token() With {.Operation = New Token.MathOperation(AddressOf MultiplyNumbers), .Pattern = "^\*$", .Precedence = 2, .Type = Token.TokenType.Operator, .Value = String.Empty}, _
                         New Token() With {.Operation = New Token.MathOperation(AddressOf DivideNumbers), .Pattern = "^\/$", .Precedence = 2, .Type = Token.TokenType.Operator, .Value = String.Empty}, _
                         New Token() With {.Operation = New Token.MathOperation(AddressOf ModuloNumbers), .Pattern = "^%$", .Precedence = 2, .Type = Token.TokenType.Operator, .Value = String.Empty}, _
                         New Token() With {.Operation = New Token.MathOperation(AddressOf RaiseNumbers), .Pattern = "^\^$", .Precedence = 3, .Type = Token.TokenType.Operator, .Value = String.Empty}}
        Dim tokens As List(Of Token) = New List(Of Token)
        'Loop through each item in the source
        For Each item As String In source.Split({" "}, StringSplitOptions.RemoveEmptyEntries)
            Dim currentToken As Token = Nothing
            Dim regex As Text.RegularExpressions.Regex
            'Loop through each rule of the lexical analyzer
            For Each definition As Token In definitions
                regex = New Text.RegularExpressions.Regex(definition.Pattern)
                'If the item is a match then add it and exit the loop for the rules of the lexical analyzer
                If regex.IsMatch(item) Then
                    currentToken = New Token With {.Operation = definition.Operation, .Pattern = definition.Pattern, .Precedence = definition.Precedence, .Type = definition.Type, .Value = item}
                    tokens.Add(currentToken)
                    Exit For
                End If
            Next
            'If a match was never found then throw and exception
            If currentToken Is Nothing Then
                Throw New Exception(item & " is not a valid character.")
            End If
        Next
        Return tokens.ToArray
    End Function
    Private Function ShuntingYardAlgorithm(ByVal tokens() As Token) As Token()
        Dim output As List(Of Token) = New List(Of Token)
        Dim operatorStack As Stack(Of Token) = New Stack(Of Token)
        'Loop through each token in the collection
        For Each item As Token In tokens
            If item.Type = Token.TokenType.Digit Then
                'If the current token is a digit then add it to the output
                output.Add(item)
            ElseIf item.Type = Token.TokenType.Operator Then
                'If the current token is an operator then add each operator in the stack to the output until we've reached an operator with a lesser precedence
                While operatorStack.Count > 0 AndAlso item.Precedence <= operatorStack.Peek.Precedence
                    output.Add(operatorStack.Pop)
                End While
                'Add the current token to the stack
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.LeftParenthesis Then
                'If the current token is a left parenthesis then add it to the output
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.RightParenthesis Then
                Dim flag As Boolean = False
                'If the current token is a right parenthesis then add all the operators to the output until we've reached a left parenthesis
                'Once we hit the left parenthesis, just dispose of the left parenthesis and exit the loop
                While operatorStack.Count > 0 AndAlso flag = False
                    If operatorStack.Peek.Type = Token.TokenType.Operator Then
                        output.Add(operatorStack.Pop)
                    ElseIf operatorStack.Peek.Type = Token.TokenType.LeftParenthesis Then
                        operatorStack.Pop()
                        flag = True
                    End If
                End While
                'If a left parenthesis was never found then throw an error because there are too many right parenthesis
                If flag = False Then
                    Throw New Exception("There are more right parenthesis than there are left parenthesis in the expression.")
                End If
            End If
        Next
        If operatorStack.Count > 0 Then
            'Loop through each token left in the stack
            Do
                If operatorStack.Peek.Type = Token.TokenType.Operator Then
                    'If the current token in the stack is an operator then add it to the output
                    output.Add(operatorStack.Pop)
                ElseIf operatorStack.Peek.Type = Token.TokenType.LeftParenthesis Then
                    'current token in the stack is a left parenthesis then throw an error because there are too many left parenthesis
                    Throw New Exception("There are more left parenthesis than there are right parenthesis in the expression.")
                End If
            Loop Until operatorStack.Count = 0
        End If
        Return output.ToArray()
    End Function
    Private Function Evaluate(ByVal tokens() As Token) As Double
        Dim valueStack As Stack(Of Token) = New Stack(Of Token)
        'Loop through each token in the collection
        For Each item As Token In tokens
            If item.Type = Token.TokenType.Operator Then
                'If the current token is an operator then get the top two digits off the stack
                Dim operand2 As Token = valueStack.Pop
                Dim operand1 As Token = valueStack.Pop
                'Add a new token to the stack with the value returned by the math operation performed
                valueStack.Push(New Token With {.Type = Token.TokenType.Digit, .Value = item.Operation(Double.Parse(operand1.Value), Double.Parse(operand2.Value)).ToString})
            Else
                'If the current token is a digit, then add it to the stack
                valueStack.Push(item)
            End If
        Next
        'The last item in the stack will be the final value
        Return Double.Parse(valueStack.Pop.Value)
    End Function
End Module
Public Class Token
    Public Enum TokenType
        Digit
        LeftParenthesis
        [Operator]
        RightParenthesis
    End Enum
    Public Delegate Function MathOperation(ByVal value1 As Double, ByVal value2 As Double) As Double
    Private _operation As MathOperation
    Public Property Operation() As MathOperation
        Get
            Return _operation
        End Get
        Set(ByVal value As MathOperation)
            _operation = value
        End Set
    End Property
    Private _pattern As String
    Public Property Pattern() As String
        Get
            Return _pattern
        End Get
        Set(ByVal value As String)
            _pattern = value
        End Set
    End Property
    Private _precedence As Integer
    Public Property Precedence() As Integer
        Get
            Return _precedence
        End Get
        Set(ByVal value As Integer)
            _precedence = value
        End Set
    End Property
    Private _type As TokenType
    Public Property Type() As TokenType
        Get
            Return _type
        End Get
        Set(ByVal value As TokenType)
            _type = value
        End Set
    End Property
    Private _value As String
    Public Property Value() As String
        Get
            Return _value
        End Get
        Set(ByVal value As String)
            _value = value
        End Set
    End Property
End Class