How I used the visitor pattern to solve the Shunting Yard algorithm
Introduction
A few months ago, the idea for a mob programming exercise was prompted in our company. The concept was simple, form groups and face a programming challenge together using the mob programming approach. The challenge consisted in a few sets of test cases that would be solved one by one using test driven development, each test suit adding new design challenges for the team. The challenge while fun, had a pretty interesting wall to surpass, at one point the challengers were asked to solve a simple mathematical equation like this one: "(2+3)*5"
This was really interesting because even though it is a well known domain, it prompted a lot of different designs and approaches that didn’t quite get it right. The most common idea when prompted with this kind of equations, is a binary tree. If I can turn this equation into a binary tree structure, solving it becomes easy with a recursive algorithm. With this in mind, I decided to give it a go and try to design a solution.
About INFIX and POSTFIX
Going back to my college years, I remembered something about Reverse Polish Notation as a way of expressing binary trees. This notation is essentially a different way of expressing a mathematical equation. Instead of the traditional infix notation "(2+3)*5" , RPN or Postfix notation, would be "23+5*"
The first thing that stands out, is the lack of parentheses in the postfix expression. Secondly, if you read through the RPN documentation, you will discover that the algorithm to solve this kind of expressions is rather simple.
I was one step closer now: Instead of a binary tree, I just needed to turn my infix expression into a postfix one and solve it.
Shunting-Yard algorithm
After my last infix/postfix epiphany, it did not take long for me to find the Shunting-Yard algorithm. This algorithm, invented by Edsger Dijkstra turns a tokenized infix expression into a tokenized postfix expression.
At this point, I could finally see the light at the end of the tunnel.
The only thing standing between me and my solution, was modeling the algorithm in a more object oriented way, since it is described in a very procedural way in the wiki.
The ‘Token’ model
Starting from the base, there was one object upon which all others will build over, the Token. Since every part of this algorithm works over a tokenized string, and those tokens can either be numbers, operators, or parentheses, this was my design:
As you can probably gather, there is an accept method in the Token interface which suggests the use of the visitor design pattern, but we will get there later, for now pay no mind to it.
The getLiteral method on the other hand, is just a method that returns the string value of the token. It can become handy if you want just to convert an infix string into a postfix string.
Another thing that comes to mind, is the operator attribute in the OperatorToken. This attribute’s class is called Operator, and it was my next design step.
The ‘Operator’ model
Since my domain was reduced to the four main operations only, this operator design was a lot simpler than it might have been.
I decided to create an abstract class, with four extensions on the solve method. Each operator, has different precedences, which are represented by numbers (0: most precedence, N: least precedence). In this case, SumOperator and SubstractOperator will have a value of 1 and the ProductOperator and DivideOperator, a value of 0.
The isLeftAssociative attribute, refers to the operator associativity which is involved in the algorithm solution. In this case, all operators are left associative.
As you would expect, each class will implement their solve method, to solve the proper operation between both numbers. For example
public class SumOperator extends Operator {
public SumOperator() {
this.precedence = 1;
this.leftAssociative = true;
}
@Override
public Double solve(Double first, Double second) {
return first + second;
}
}The ‘PostfixConverter’ class
With all the base models ready, I needed a class that would handle the conversion from an infix tokenized list to a postfix tokenized list.
This ‘PostfixConverter’ receives a list of ‘Token’ objects in the infix order, and returns the same but in the postfix order.
Let us take a look at the code of this particular class implementation.
public class PostfixConverter {
private ShuntingYardVisitor visitor;
public PostfixConverter(){
this.visitor = new ShuntingYardVisitor();
}
public ArrayList<Token> convert(ArrayList<Token> tokens) {
for (Token token : tokens) {
token.accept(this.visitor);
}
return visitor.getResult();
}
}As you can see, it is quite simple. It just iterates over all the tokens in the array, asking them to accept the visitor, which will then process them and return the expected result. Before we get inside this ‘ShuntingYardVisitor’ I woud like to recomend you to look a the visitor pattern, to make it easier to understand.
Visiting tokens
Let us take a look first at how the tokens implement the accept method.
@Override
public void accept(Visitor visitor) {
visitor.visit(this);
}It is pretty simple, but there is a catch. When they call the visit method in the visitor, they are sending themselves, and that means, that the visit method the ‘OperatorToken’ utilizes is different from the one the ‘NumberToken’ utilizes, since they receive different types of arguments. With this in mind, let us take a look now at the visitors UML class diagram.
We can see now in the interface, that there are multiple visit methods, one for each type of token that may be visited.
Looking to the ‘ShuntingYardVisitor’s implementation of ‘Visitable’, there are 2 very familiar attributes there that come straight from the algorithm’s definition, the operatorStack and the outputQueue.
Now, this is the implementation of the ‘ShuntingYardVisitor’ for each type of ‘Token’ through the visit method.
@Override
public void visit(NumericToken token) {
outputQueue.add(token);
}
@Override
public void visit(OperatorToken token) {
while(shouldProcessOperators(token)) {
outputQueue.add(opStack.pop());
}
opStack.push(token);
}
@Override
public void visit(RightParenthesesToken token) {
while(!opStack.empty() && topIsNotLeftParenthesis()) {
outputQueue.add(opStack.pop());
}
if(!opStack.empty()) {
opStack.pop();
} else {
throw new MismatchedParenthesesException()
}
}
@Override
public void visit(LeftParenthesesToken token) {
opStack.push(token);
}Finally we can see where the algorithm implementation lies. Each different type of token, will invoke a different visit method for its own type and that will operate over the algorithm structures accordingly.
For example, the algorithm definition says:
if the token is a right paren (i.e. ")"), then:
while the operator at the top of the operator stack is not a left paren:
pop the operator from the operator stack onto the output queue.if there is a left paren at the top of the operator stack, then:
pop the operator from the operator stack and discard it
And that is exactly what the visit method for the ‘RightParenthesesToken’ is doing.
The last part, after all tokens are processed by the visitor, the stack and output queue should be ready for the final part of the algoritm that reads:
if there are no more tokens to read:
while there are still operator tokens on the stack:
pop the operator from the operator stack onto the output queue.
Which is what the getResult method does in the ‘ShuntingYardVisitor’ implementation.
public ArrayList<Token> getResult() {
while(!opStack.empty()) {
outputQueue.add(opStack.pop());
}
return outputQueue;
}What you get after this is a List<Token> but with a postfix order. If you want to transform this into a postfix string, you can just build a string asking each token for their literal value using the getLiteral method on the tokens.
On what I left out
First of all, this solution is limited. There are no operations other than the main four, but the idea is simple enough that you can easily add them. To add a new operation, you would need to add a new class extending the ‘Operator’ class.
There are of course 2 important parts of the exercise I also left out, the tokenization part and the postfix evaluation part.
For the tokenization part, you would need to transform a string into a List<Token> and to do that, there are quite a few ways. You could just iterate over the string creating and adding tokens to the list as you deem necessary, to name an easy solution.
For the evaluation part, the postfix evaluation algorithm is pretty simple. Since you would already have a List<Token> , one possible solution would be to use a visitor in the same fashion as I used before, but this time, the result would not be a List<Token> but a number instead.
Final thoughts
This exercise was really fun to think and to develop. It still amazes me how tricky it was to think of a solution for this domain. Even though it was a really well known one, a simple math expression. In retrospective, I think that because it was a well known domain, that it was so tricky. It is sometimes more difficult to investigate about something you think you know very well.
Now looking to this solution, there are a few things I would like to change. First of all the different conditions that trigger behavior in the visitor, would be extracted elsewhere to leave more readable visit methods. But overall I am pleased with what I was able to accomplish.
Finally I would like to thank everyone who participated in the mob programming challenge who inspired me to make this exercise by myself.
Thank you for reading and I hope you enjoyed it!
