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
Reply With Quote