Results 1 to 14 of 14

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
    11,698

    The Basic Principals of Creating an Expression Evaluator

    Chapter 1: Expression Evaluator
    Chapter 2: Stack Oriented Programming
    Chapter 3: Formatting Expressions
    Chapter 4: Lexical Analyzer
    Chapter 5: Reverse Polish Notation
    Chapter 6: Evaluator
    Chapter 7: Conclusion
    Last edited by dday9; Feb 9th, 2015 at 10:51 PM.
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  2. #2

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

    Re: The Basic Principals of Creating an Expression Evaluator

    Chapter 1: Expression Evaluator

    In order to understand what an expression evaluator is, one must understand what an expression is. In computer science, an expression represents a combination of values, variables, and mathematical operators that will ultimately be evaluated following the order of operations.

    Values in an expression are number literals meaning that they literally represent a fixed number, positive or negative, with an optional decimal point. By contrast, variables are character representations of literals but are dynamic which mean that the value they represent can change. Mathematical operators are basic mathematical procedures that return a new value from two other values. Some operators are addition, subtraction, multiplication, division, exponent, and square root just to name a few.

    The order of operations is something that we all learned in math class in high school, you may remember the acronyms PEMDAS or BIDMAS. PEMDAS stands for Parenthesis, Exponents, Multiplication, Division, Addition, and Subtraction. BIDMAS stands for Brackets, Indices, Multiplication, Division, Addition, and Subtraction. Both acronyms represent the order in which a mathematical equation should be evaluated and it is important that and expression evaluator follows these rules because an equation can be evaluated wrong if they are not followed. Take the following equation:
    Code:
    2 - 2 * 10
    Without following the order of operations, 2 would be subtracted by 2 and would return 0 then 0 multiplied by 10 would return 0. However following the order of operations, 2 would be multiplied by 10 because multiplication takes precedence over subtraction and would return 20 then 2 subtracted by 20 would be -18
    Last edited by dday9; Feb 27th, 2015 at 12:21 PM.
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  3. #3

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

    Re: The Basic Principals of Creating an Expression Evaluator

    Chapter 2: Stack Oriented Programming

    In stacked oriented programming, one or more stack objects are used to control the flow of the actions being made. Just like an expression evaluator, in order for one to understand stack oriented programming, one must understand what a stack is. A stack object represents a LIFO(Last In, First Out) object where the last element that was placed in the stack is the first element to be removed. The major methods of a stack object are peek, pop, and push.

    The peek method returns the object at the top of the stack without actually removing it from the stack; the peek method could be thought of as a preview of the top of the stack. The pop method returns the object at the top of the stack while also removing the object from the stack; the pop method is where the LIFO comes into play. The push method simply inserts an object at the top of the stack.

    Stack oriented programming is used in expression evaluators because they are very simple to create and can be very efficient when it comes to memory consumption and the overall execution time. The main reason why stack oriented programming is simple to create is because typically there are two major "front end" functions of a compiler, the lexical analyzer (which is something covered in a later chapter) and a syntax analyzer each of which can be rather complex. However, with stack oriented programming the syntax analyzer is completely eliminated! The reason why stack oriented programming is efficient is because it will ultimately shorten the expression that was originally entered which lowers the memory consumption and most times lower memory consumption translates to a quicker execution.
    Last edited by dday9; Feb 9th, 2015 at 09:53 PM.
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  4. #4

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

    Re: The Basic Principals of Creating an Expression Evaluator

    Chapter 3: Formatting Expressions

    In order to properly read an expression, the entered expression must be formatted properly for the computer to read it. However, there are many different styles of entering an expression. For example, most people tend to not place whitespace after opening parenthesis or before closing parenthesis like in the following example:
    Code:
    (1 + 2) * 3
    Another is example is that some prefer to type everything in the equation with no whitespace at all like in the following example:
    Code:
    1*-2/4
    The two examples given, while can be interpreted fairly easily by humans, are too ambiguous for computers. The format that a computer needs in order to evaluate the expression is to have a single whitespace between each character and this can be done by writing a function which will properly format the expression.

    The first step will be to create a function which will return a String. There will be just one parameter which will take in the originally entered expression:
    Code:
    Private Function FormatExpression(ByVal expression As String) As String
    
    End Function
    We will assume for a second that the user entered the following expression:
    Code:
    1 + -2 * (3 + 4)
    Inside the function we will need to first remove all blank spaces:
    Code:
    Private Function FormatExpression(ByVal expression As String) As String
        'Remove all blanks spaces
        Dim format As String = expression.Replace(" ", String.Empty)
    
    End Function
    The expression will now look like this:
    Code:
    1+-2*(3+4)
    Next we will need to add a space before an after each parenthesis:
    Code:
    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(")", " ) ")
    End Function
    The expression will now look like this:
    Code:
    1+-2* ( 3+4 )
    The next step will be to add a space prior to any unary operators. A unary operator in this instance a negative sign for a digit. In order to do this we will use RegEx. The RegEx will be used to match any operator(+, -, /, *, or ^) prior to a negative sign(-):
    Code:
    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)
    
    End Function
    With the ReplaceUnary function structured as such:
    Code:
    Private Function ReplaceUnary(ByVal m As System.Text.RegularExpressions.Match) As String
        Return " " & m.Value
    End Function
    The expression will now look like this:
    Code:
    1+ -2* ( 3+4 )
    The next step will be to add a space before and after any digit. We will use RegEx again to match any doubles with the option for a negative sign. The RegEx will be used to match any number with the option for a negative sign before it and also allow for a decimal:
    Code:
    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)
    End Function
    With the ReplaceDigits function structured like this:
    Code:
    Private Function ReplaceDigits(ByVal m As System.Text.RegularExpressions.Match) As String
        Return " " & m.Value & " "
    End Function
    The expression will now look like this:
    Code:
     1 +  -2 * (  3 + 4  )
    The expression is now unambiguous, however we can do one more bit of cleanup by eliminating all excess whitespace. This again is going to be done by using RegEx but also by using the built-in Trim function. The RegEx will match any blank space two or more times and replace it with a single blank space where as the Trim method will remove any leading or trailing whitespace:
    Code:
    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
    The expression will now look like this:
    Code:
    1 + -2 * ( 3 + 4 )
    This function will properly format the expression to where there is a single whitespace after each character, excluding unary operators which makes the expression completely unambiguous.
    Last edited by dday9; Jul 2nd, 2015 at 09:18 AM.
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  5. #5

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

    Re: The Basic Principals of Creating an Expression Evaluator

    Chapter 4: Lexical Analyzer
    A lexical analyzer takes in an arrangement of characters and then converts those characters into an arrangement of tokens; this process is also known as scanning. A token is an object that stores information to be processed at a later time and is identified based on specific rules of the analyzer by using Regular Expressions. Regular Expressions(RegEx) is combination of characters that form a search pattern used for string matching. Each character in RegEx is either represents it’s literal meaning or it will have a special meaning. Together, they can be used to identify patterns in a string.

    The token object will be represented as a class with the following properties: Operation, Pattern, Precedence, and Type. The Operation property’s type will be a custom delegate; delegates are objects that refer to methods and in this case the methods will be used to represent the operation that the token will perform. This means that the Operation property is only applicable on tokens that are operators. The Pattern property will be a string property used to represent the Regular Expression pattern of the token. The Precedence property will be an Integer property used to represent an operators precedence in the order of operations. This means that the Precedence property will only be applicable on tokens that are operators. The Type property will be a custom enumerator property; the enumerator will store values such as: digit, left parenthesis, operator, and right parenthesis. Finally the last property, Value, will be a string value and will be used to represent the literal value of the character.

    This is how the token class should appear:
    Code:
    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
    Once the token class has been created the actual process of scanning can begin. To structure the lexical analyzer, it will be a function with a single parameter. The parameter will be used to represent the formatted expression. The value returned from the function will be a collection of tokens:
    Code:
    Private Function Scan(ByVal source As String) As Token() 
     
    End Function
    Once the foundation of the function has been built, the next step is to create the rules of the lexical analyzer. These rules will be a collection of tokens, however before the rules are created the lambdas for the Operation property in the token class must be created and these must be placed outside of the function. You will need to do this for each operator that you wish to have and here are a few of the more common operations:
    Code:
    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
    Now that the lambdas are in place, the rules of the lexical analyzer can be created. There will be a number of tokens that need to be created: left parenthesis, right parenthesis, digit, addition, subtraction, multiplication, division, mod, and exponent. To store these rules, create a collection of tokens inside the Scan function:
    Code:
    Private Function Scan(ByVal source As String) As Token() 
        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}} 
     
    End Function
    The following are explanations of the RegEx patterns:
    ^\($ : Left Parenthesis RegEx
    ^: matches the beginning of the string
    \(: matches the ( character
    $: matches the end of the string

    ^\)$: Right Parenthesis RegEx
    ^: matches the beginning of the string
    \): matches the ) character
    $: matches the end of the string

    ^([-+]?(\d*[.])?\d+)$: Digit RegEx
    ^: matches the beginning of the string
    [-+]?: matches an optional positive or negative symbol
    (\d*[.])?: optionally matches any amount of digits 0 – 9 with a decimal point
    \d+: matches 1 or more digits
    $: matches the end of the string

    ^\+$: Addition RegEx
    ^: matches the beginning of the string
    \+: matches the + character
    $: matches the end of the string

    ^-$: Subtraction RegEx
    ^: matches the beginning of the string
    -: matches the - character
    $: matches the end of the string

    ^\*$: Multiplication RegEx
    ^: matches the beginning of the string
    \*: matches the * character
    $: matches the end of the string
    ^\/$: Division RegEx
    ^: matches the beginning of the string
    \/: matches the / character
    $: matches the end of the string

    ^\%: Modulos RegEx
    ^: matches the beginning of the string
    \%: matches the % character
    $: matches the end of the string
    ^\^$: Exponent RegEx
    ^: matches the beginning of the string
    \^: matches the ^ character
    $: matches the end of the string

    The next step in the lexical analyzer process is to loop through each character in the expression and adding a token based on that character to a collection throughout the loop. Because the expression is guaranteed to be formatted correctly by having a whitespace after each character, String.Split will be used to split the formatted source parameter into an array of characters:
    Code:
    Private Function Scan(ByVal source As String) As Token() 
    	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) 
     
        For Each item As String in source.Split({“ “}, StringSplitOptions.RemoveEmptyEntries) 
     
        Next 
     
    End Function
    Once the loop is setup, the next step will be to add a token to the collection to be returned if it matches one of the rules that have already been established. This will be done by looping through each rule and checking if there is a RegEx match on the current character:
    Code:
    For Each item As String In source.Split({" "}, StringSplitOptions.RemoveEmptyEntries) 
    	Dim currentToken As Token = Nothing 
    	Dim regex As Text.RegularExpressions.Regex 
    	For Each definition As Token In definitions 
    		regex = New Text.RegularExpressions.Regex(definition.Pattern) 
    		If regex.IsMatch(item) Then 
    			currentToken = New Token With {.Operation = definition.Operation, .Pattern = definition.Pattern, .Precedence = definition.Precedence, .Type = definition.Type, .Value = definition.Value} 
    			tokens.Add(currentToken)
    			Exit For
    		End If
    	Next
    Next
    After each rule has been evaluated, it’s necessary to check that the currentToken variable is Nothing, because if it is then that means that there is an error. If the currentToken is Nothing then throw a new Exception explaining what occurred:
    Code:
    For Each item As String In source.Split({" "}, StringSplitOptions.RemoveEmptyEntries) 
    	Dim currentToken As Token = Nothing 
    	Dim regex As Text.RegularExpressions.Regex 
    	For Each definition As Token In definitions 
    		regex = New Text.RegularExpressions.Regex(definition.Pattern) 
    		If regex.IsMatch(item) Then 
    			currentToken = New Token With {.Operation = definition.Operation, .Pattern = definition.Pattern, .Precedence = definition.Precedence, .Type = definition.Type, .Value = definition.Value} 
    			tokens.Add(currentToken) 
    			Exit For 
    		End If
    	Next 
    	If currentToken Is Nothing Then 
    		Throw New Exception(item & " is not a valid character.")
    	End If 
    Next
    The final step is to return the token collection:
    Code:
    Return tokens.ToArray
    This is how the final code should look for the lexical analyzer:
    Code:
    Private Function Scan(ByVal source As String) As Token() 
    	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) 
    	For Each item As String In source.Split({" "}, StringSplitOptions.RemoveEmptyEntries) 
    		Dim currentToken As Token = Nothing 
    		Dim regex As Text.RegularExpressions.Regex 
    		For Each definition As Token In definitions 
    			regex = New Text.RegularExpressions.Regex(definition.Pattern) 
    			If regex.IsMatch(item) Then 
    				currentToken = New Token With {.Operation = definition.Operation, .Pattern = definition.Pattern, .Precedence = definition.Precedence, .Type = definition.Type, .Value = definition.Value} 
    				tokens.Add(currentToken) 
    				Exit For 
    			End If 
    		Next
    		
    		If currentToken Is Nothing Then 
    			Throw New Exception(item & " is not a valid character.") 
    		End If
    	
    	Next 
    	Return tokens.ToArray 
    End Function
    The function will return a collection of tokens that will eventually be evaluated.
    Last edited by dday9; Feb 9th, 2015 at 10:14 PM.
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  6. #6

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

    Re: The Basic Principals of Creating an Expression Evaluator

    Chapter 5: Reverse Polish Notation
    Reverse polish notation is a mathematical postfix notation where the operators follow their operands. This is the very core of the stack oriented programming in that how the expression is converted from infix notation to reverse polish notation and also how the expression is solved.
    The easiest way to understand reverse polish notation is by examples because its difficult to understand the notation by simply it's description. Take the following expression:
    Code:
    1 + 2 - 3
    In reverse polish notation the equation would be represented as such:
    Code:
    1 2 + 3 -
    Where one would read 1 then 2 then add which would produce 3 which would then be represented as such:
    Code:
    3 3 -
    Where one would read 3 then 3 then subtract would then give the final value of 0.
    Another example where the order of operations would be applicable:
    Code:
    1 + 2 * 3
    In reverse polish notation the equation would be represented as such:
    Code:
    2 3 * 1 +
    Where one would read 2 then 3 then multiply which would produce 6 and then be represented as such:
    Code:
    6 1 +
    Where one would read 6 then 1 then add which would produce the final value of 7.

    The input received by the user will be in infix notation, but this can be a bit ambiguous because of the order of operations not to mention difficult and inefficient for a computer to evaluate; infix notation is the type of notation more commonly seen and taught in schools. Therefore the infix notated input will be converted to reverse polish notation, this is done by using the shunting-yard algorithm.

    There are several steps involved in the shunting-yard algorithm. The first step is to read every token in the collection. If the current token being read is a digit, then add it to the collection to be returned. If the token is an operator(o1) then loop through every token(o2) in the operator stack. If the token(o2)'s precedence is less than or equal to the operator(o1) then add it to the collection to be returned. If the token(o2)'s precedence is less than the operator(o1) then push the operator(o1) to the operator stack. If the current token being read is a left parenthesis, then push it to the operator stack. If the current token is being read is a right parenthesis then loop through every token in the operator stack and pop all tokens off of the operator stack into the collection to be returned until the token at the top of the operator stack is a left parenthesis. Once the token at the top of the operator stack is a left parenthesis, pop it off of the operator stack without adding to the collection to be returned. Once all of the tokens have been read, pop the remaining tokens that are left in the operator stack into the collection to be returned.
    Now that you have an understanding of how to execute the shunting-yard algorithm, the actual process of converting infix notation to reverse polish notation can begin. To structure the shunting-yard algorithm, it will be a function with a single parameter. The parameter will be used to represent the collection of tokens returned by the lexical analyzer. The value returned from the function will be a collection of tokens:
    Code:
    Private Function ShuntingYardAlgorithm(ByVal tokens() As Token) As Token()
    
    End Function
    Once structure of the algorithm has been built, the next step will be to create the collection of tokens that will be returned as well as the stack that will hold the operators:
    Code:
    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)
    
    End Function
    Now the actual execution of the algorithm will be done. First, loop through each token in the collection:
    Code:
    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)
    
        For Each item As Token In tokens
    
        Next
    End Function
    Next, inside the loop setup a conditional statement to check if the token is a digit, operator, left parenthesis, or right parenthesis:
    Code:
    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)
    
        For Each item As Token In tokens
            If item.Type = Token.TokenType.Digit Then
    
            ElseIf item.Type = Token.TokenType.Operator Then
    
            ElseIf item.Type = Token.TokenType.LeftParenthesis Then
    
            ElseIf item.Type = Token.TokenType.RightParenthesis Then
    
            End If
        Next
    End Function
    The action needed to take for if the current token being iterated is a digit is very simple, simply add it to the output:
    Code:
    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)
    
        For Each item As Token In tokens
            If item.Type = Token.TokenType.Digit Then
                output.Add(item)
            ElseIf item.Type = Token.TokenType.Operator Then
    
            ElseIf item.Type = Token.TokenType.LeftParenthesis Then
    
            ElseIf item.Type = Token.TokenType.RightParenthesis Then
    
            End If
        Next
    End Function
    However moving to the next token type, the operator, things get a bit more difficult. The first step to take is to step up the loop that will iterate through the operator stack. This loop will be a While loop and it will need to check for multiple conditions. The first condition is to prevent an exception being thrown and that is to make sure that there are items in the stack. The second condition will be used to check if the operator(o1)'s precedence is less than or equal to the operator(o2) at the top of the stack:
    Code:
     While operatorStack.Count > 0 AndAlso item.Precedence <= operatorStack.Peek.Precedence
    
    End While
    The next step will be to pop the operator(o2) at the top of the stack to the output:
    Code:
    While operatorStack.Count > 0 AndAlso item.Precedence <= operatorStack.Peek.Precedence
        output.Add(operatorStack.Pop)
    End While
    Finally once the loop is finished executing, push the operator(o1) to the operator stack:
    Code:
    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)
    
        For Each item As Token In tokens
            If item.Type = Token.TokenType.Digit Then
                output.Add(item)
            ElseIf item.Type = Token.TokenType.Operator Then
                While operatorStack.Count > 0 AndAlso item.Precedence <= operatorStack.Peek.Precedence
                    output.Add(operatorStack.Pop)
                End While
    
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.LeftParenthesis Then
    
            ElseIf item.Type = Token.TokenType.RightParenthesis Then
    
            End If
        Next
    End Function
    The next step handles tokens that are left parenthesis and this step is just as simple as the step for the digit only the left parenthesis will be pushed into the operatorStack:
    Code:
    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)
    
        For Each item As Token In tokens
            If item.Type = Token.TokenType.Digit Then
                output.Add(item)
            ElseIf item.Type = Token.TokenType.Operator Then
                While operatorStack.Count > 0 AndAlso item.Precedence <= operatorStack.Peek.Precedence
                    output.Add(operatorStack.Pop)
                End While
    
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.LeftParenthesis Then
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.RightParenthesis Then
    
            End If
        Next
    End Function
    The last action to take while looping through the token collection is to check for right parenthesis, and this is the most difficult part of the loop. The first thing needed to be done is to declare a flag that will check if a left parenthesis was ever found in the operator stack because if a left parenthesis was never found then there is an error, too many closed parenthesis. The flag will be set equal to False by default because it will be assumed that there is an error in the original source code:
    Code:
    Dim flag As Boolean = False
    The next step will be to loop through the operator stack until a left parenthesis is found. Just like when the token type was an operator, looping through the operator stack will be a While loop with multiple conditions. The first condition will be used to make sure that there are still tokens in the operator stack. The second condition will be used to check if the flag is True:
    Code:
    Dim flag As Boolean = False
    
    While operatorStack.Count > 0 AndAlso flag = False
    
    End While
    Inside the while loop, there will be two conditions. The first condition will be to check if the token at the top of the stack is an operator and the second condition will be to check if the token at the top of the stack is a left parenthesis:
    Code:
    Dim flag As Boolean = False
    
    While operatorStack.Count > 0 AndAlso flag = False
        If operatorStack.Peek = Token.TokenType.Operator Then
    
        ElseIf operatorStack.Peek = Token.TokenType.LeftParenthesis Then
    
        End If
    End While
    If the token at the top of the stack is an operator, then pop it off of the stack into the output:
    Code:
    Dim flag As Boolean = False
    
    While operatorStack.Count > 0 AndAlso flag = False
        If operatorStack.Peek = Token.TokenType.Operator Then
            output.Add(operatorStack.Pop)
        ElseIf operatorStack.Peek = Token.TokenType.LeftParenthesis Then
    
        End If
    End While
    If the token at the top of the stack is a left parenthesis, then pop it off of the stack without adding it to the output and set the flag to True:
    Code:
    Dim flag As Boolean = False
    
    While operatorStack.Count > 0 AndAlso flag = False
        If operatorStack.Peek = Token.TokenType.Operator Then
            output.Add(operatorStack.Pop)
        ElseIf operatorStack.Peek = Token.TokenType.LeftParenthesis Then
            operatorStack.Pop
            flag = True
        End If
    End While
    The last step occurs after the While loop is finished and it is to check if the flag property is False. Because if the flag property is False then there is an error:
    Code:
    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)
    
        For Each item As Token In tokens
            If item.Type = Token.TokenType.Digit Then
                output.Add(item)
            ElseIf item.Type = Token.TokenType.Operator Then
                While operatorStack.Count > 0 AndAlso item.Precedence <= operatorStack.Peek.Precedence
                    output.Add(operatorStack.Pop)
                End While
    
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.LeftParenthesis Then
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.RightParenthesis Then
                Dim flag As Boolean = False
    
                While operatorStack.Count > 0 AndAlso flag = False
                    If operatorStack.Peek = Token.TokenType.Operator Then
                        output.Add(operatorStack.Pop)
                    ElseIf operatorStack.Peek = Token.TokenType.LeftParenthesis Then
                       operatorStack.Pop
                        flag = True
                    End If
                End While
    
                If Not flag Then
                    Throw New Exception("There are more right parenthesis than there are left parenthesis in the expression.")
                End If
    
            End If
        Next
    End Function
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  7. #7

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

    Re: The Basic Principals of Creating an Expression Evaluator

    Chapter 5: Reverse Polish Notation - Continued
    Now that each action in the conditional statements have finished, we're finished looping through each token. The next step is to clear each token out of the operator stack. The first step to take will be to check if there are any tokens left in the operator stack:
    Code:
    If operatorStack.Count > 0 Then
    
    End If
    If there are tokens left in the operator stack then start looping through them. This loop will be a Do loop, the condition will be to loop until the operator stack has no tokens left in it, and the condition will be at the bottom of the loop:
    Code:
    If operatorStack.Count > 0 Then
    
        Do
    
        Loop Until operatorStack.Count = 0
    
    End If
    Inside the loop, there will be two conditions. The first condition will be to check if the token at the top of the operator stack is an operator and the second condition will be to check if the token at the top of the operator stack is a left parenthesis:
    Code:
    If operatorStack.Count > 0 Then
    
        Do
            If operatorStack.Peek.Type = Token.TokenType.Operator Then
    
            ElseIf operatorStack.Peek.Type = Token.TokenType.LeftParenthesis Then
    
            End If
        Loop Until operatorStack.Count = 0
    
    End If
    If the token at the top of the operator stack is an operator then pop it off of the stack into the output, but if the token at the top of the operator stack is a left parenthesis then throw an error because there are more left parenthesis than there are right parenthesis:
    Code:
    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)
    
        For Each item As Token In tokens
            If item.Type = Token.TokenType.Digit Then
                output.Add(item)
            ElseIf item.Type = Token.TokenType.Operator Then
                While operatorStack.Count > 0 AndAlso item.Precedence <= operatorStack.Peek.Precedence
                    output.Add(operatorStack.Pop)
                End While
    
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.LeftParenthesis Then
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.RightParenthesis Then
                Dim flag As Boolean = False
    
                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 Not flag 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
    
                Do
                    If operatorStack.Peek.Type = Token.TokenType.Operator Then
                        output.Add(operatorStack.Pop)
                    ElseIf operatorStack.Peek.Type = Token.TokenType.LeftParenthesis Then
                        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
    End Function
    The final step in the shunting-yard algorithm is to return the output:
    Code:
    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)
    
        For Each item As Token In tokens
            If item.Type = Token.TokenType.Digit Then
                output.Add(item)
            ElseIf item.Type = Token.TokenType.Operator Then
                While operatorStack.Count > 0 AndAlso item.Precedence <= operatorStack.Peek.Precedence
                    output.Add(operatorStack.Pop)
                End While
    
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.LeftParenthesis Then
                operatorStack.Push(item)
            ElseIf item.Type = Token.TokenType.RightParenthesis Then
                Dim flag As Boolean = False
    
                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 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
    
                Do
                    If operatorStack.Peek.Type = Token.TokenType.Operator Then
                        output.Add(operatorStack.Pop)
                    ElseIf operatorStack.Peek.Type = Token.TokenType.LeftParenthesis Then
                        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
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  8. #8

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

    Re: The Basic Principals of Creating an Expression Evaluator

    Chapter 6: Evaluator
    The last step in the expression evaluator is to actually evaluate the expression and this is one of the easiest steps. The evaluator will be a function that returns a Double and takes in a single parameter, the parameter is a collection of tokens that represents the tokens formatted in reverse polish notation:
    Code:
    Private Function Evaluate(ByVal tokens() As Token) As Double
    
    End Function
    Now that the function has been structured, the next step will be to declare a stack of tokens that will ultimately return the final value:
    Code:
    Private Function Evaluate(ByVal tokens() As Token) As Double
        Dim valueStack As Stack(Of Token) = New Stack(Of Token)
    End Function
    Next, loop through each token in the tokens parameter using a For/Each loop:
    Code:
    Private Function Evaluate(ByVal tokens() As Token) As Double
        Dim valueStack As Stack(Of Token) = New Stack(Of Token)
    
        For Each item As Token in Tokens
    
        Next
    End Function
    Once the loop has been built, the next step will be to structure a conditional statement. The conditional statement will have two conditions, the first condition checks if the current token in the iteration is an operator and the second condition checks if the current token in the iteration is anything but an operator:
    Code:
    Private Function Evaluate(ByVal tokens() As Token) As Double
        Dim valueStack As Stack(Of Token) = New Stack(Of Token)
    
        For Each item As Token in Tokens
            If item.Type = Token.TokenType.Operator Then
    
            Else
    
            End If
        Next
     End Function
    The first condition I will go over will be the Else statement because it is the simplest. If the current token in the iteration is not an operator then simply add it to the stack:
    Code:
    Private Function Evaluate(ByVal tokens() As Token) As Double
        Dim valueStack As Stack(Of Token) = New Stack(Of Token)
    
        For Each item As Token in Tokens
            If item.Type = Token.TokenType.Operator Then
    
            Else
                valueStack.Push(item)
            End If
        Next
    End Function
    The other condition that check if the current token in the iteration has a few steps. The first step will be to pop the top two values off of the stack, now because the notation is in reverse polish notation this means that the second operand will be at the top of the stack and the first operand will be after:
    Code:
    Private Function Evaluate(ByVal tokens() As Token) As Double
        Dim valueStack As Stack(Of Token) = New Stack(Of Token)
    
        For Each item As Token in Tokens
            If item.Type = Token.TokenType.Operator Then
                Dim operand2 As Token = valueStack.Pop
                Dim operand1 As Token = valueStack.Pop
            Else
                valueStack.Push(item)
            End If
        Next
    End Function
    The last step of the condition will be to push the value of operand1 and operand2 using the operator token's Operation delegate method:
    Code:
    Private Function Evaluate(ByVal tokens() As Token) As Double
        Dim valueStack As Stack(Of Token) = New Stack(Of Token)
    
        For Each item As Token in Tokens
            If item.Type = Token.TokenType.Operator Then
                Dim operand2 As Token = valueStack.Pop
                Dim operand1 As Token = valueStack.Pop
    
                valueStack.Push(New Token With {.Type = Token.TokenType.Digit, .Value = item.Operation(Double.Parse(operand1.Value), Double.Parse(operand2.Value)).ToString})
            Else
                valueStack.Push(item)
            End If
        Next
    End Function
    Now that the conditions are finished, the last step of the process will be to return the final value in the stack:
    Code:
    Private Function Evaluate(ByVal tokens() As Token) As Double
        Dim valueStack As Stack(Of Token) = New Stack(Of Token)
    
        For Each item As Token in Tokens
            If item.Type = Token.TokenType.Operator Then
                Dim operand2 As Token = valueStack.Pop
                Dim operand1 As Token = valueStack.Pop
    
                valueStack.Push(New Token With {.Type = Token.TokenType.Digit, .Value = item.Operation(Double.Parse(operand1.Value), Double.Parse(operand2.Value)).ToString})
            Else
                valueStack.Add(item)
            End If
        Next
    
        Return Double.Parse(valueStack.Pop.Value)
    End Function
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  9. #9

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

    Re: The Basic Principals of Creating an Expression Evaluator

    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:
    Code:
    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
    Last edited by dday9; Jul 2nd, 2015 at 09:23 AM.
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  10. #10
    Lively Member
    Join Date
    Mar 2015
    Posts
    104

    Re: The Basic Principals of Creating an Expression Evaluator

    Interesting reading. I like the way you explain the logic behind your coding. I will have to try out your code by compiling the program. Thank you DDay9 for your effort in preparing the clear explanation of coding.

  11. #11

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

    Re: The Basic Principals of Creating an Expression Evaluator

    glad you liked it!
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

  12. #12
    Smooth Moperator techgnome's Avatar
    Join Date
    May 2002
    Posts
    34,522

    Re: The Basic Principals of Creating an Expression Evaluator

    Yeah, I'll need to read this later when I have more time. I've thought about developing my own language, but I'm not sure what it would look like - every time I go to map it out, I realize, "HEck! This looks just like BASIC!" snerk! Maybe I'll base it off of my Malamute using a series of Woos and wuffs.

    -tg
    * I don't respond to private (PM) requests for help. It's not conducive to the general learning of others.*
    * I also don't respond to friend requests. Save a few bits and don't bother. I'll just end up rejecting anyways.*
    * How to get EFFECTIVE help: The Hitchhiker's Guide to Getting Help at VBF - Removing eels from your hovercraft *
    * How to Use Parameters * Create Disconnected ADO Recordset Clones * Set your VB6 ActiveX Compatibility * Get rid of those pesky VB Line Numbers * I swear I saved my data, where'd it run off to??? *

  13. #13
    New Member
    Join Date
    Feb 2017
    Posts
    1

    Re: The Basic Principals of Creating an Expression Evaluator

    nice code
    Last edited by lloydy; Mar 5th, 2017 at 12:16 PM.

  14. #14

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

    Re: The Basic Principals of Creating an Expression Evaluator

    Quote Originally Posted by lloydy View Post
    hi dday9, im getting some problems when implementing this code to a simple calculator, can you help me?
    Absolutely, I'd suggest posting the question in the appropriate forum. If you want you can private message me the link to your thread and I'll be happy to help out!
    "Code is like humor. When you have to explain it, it is bad." - Cory House
    VbLessons | Code Tags | Sword of Fury - Jameram

Posting Permissions

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



Click Here to Expand Forum to Full Width