|
-
Nov 20th, 2014, 04:32 PM
#1
The Basic Principals of Creating an Expression Evaluator
Last edited by dday9; Feb 9th, 2015 at 10:51 PM.
-
Nov 20th, 2014, 04:32 PM
#2
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:
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.
-
Nov 20th, 2014, 04:32 PM
#3
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.
-
Nov 20th, 2014, 06:10 PM
#4
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:
Another is example is that some prefer to type everything in the equation with no whitespace at all like in the following example:
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:
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:
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:
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:
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:
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:
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.
-
Nov 20th, 2014, 06:12 PM
#5
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.
-
Feb 9th, 2015, 10:46 PM
#6
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:
In reverse polish notation the equation would be represented as such:
Where one would read 1 then 2 then add which would produce 3 which would then be represented as such:
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:
In reverse polish notation the equation would be represented as such:
Where one would read 2 then 3 then multiply which would produce 6 and then be represented as such:
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
-
Feb 9th, 2015, 10:47 PM
#7
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
-
Feb 9th, 2015, 10:49 PM
#8
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
-
Feb 9th, 2015, 10:50 PM
#9
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.
-
Mar 9th, 2015, 08:05 PM
#10
Lively Member
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.
-
Mar 10th, 2015, 08:47 AM
#11
Re: The Basic Principals of Creating an Expression Evaluator
 glad you liked it!
-
Mar 10th, 2015, 09:15 AM
#12
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
-
Feb 26th, 2017, 02:02 PM
#13
New Member
Re: The Basic Principals of Creating an Expression Evaluator
Last edited by lloydy; Mar 5th, 2017 at 12:16 PM.
-
Feb 27th, 2017, 10:17 AM
#14
Re: The Basic Principals of Creating an Expression Evaluator
 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!
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|
Reply With Quote