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

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

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.

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.

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.

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

---

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

---

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

---

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

---

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.

:thumb: glad you liked it!

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

nice code

Quote:

---

Originally Posted by lloydy

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!