Tags

, , , , , , , , ,

Some days ago I was surfing on a friend’s blog and reading his last post about Reverse Polish Notation I recalled the first time when I’ve heard about RPN. It was during the Software Engineering B.Sc class, held by prof. Libero Nigro, one of the best teacher I’ve ever had during my university career.

One of the final project for that exam was an EBNF Arithmetic Expression Interpreter. Long story short: we had to build a calculator starting from EBNF language specifications and apply some good Software Design Patterns as the Interpreter, Visitor and Iterator Pattern.

What has this to do with RPN? In Computer Science, the Reverse Polish Notation is also known as Postfix Notation and it can be adopted also as Tree traversal. The Interpreter pattern is used to build what is known as syntax tree of a sentence in a (EBNF) language. So one of the project goal was to interpret instances of the Arithmetic Expression language and build the syntax tree, adding also a Visitor hierarchy in order to allow different tree traversals, including, of course, the postfix (RPN) one.

What a shame: I couldn’t find the code I wrote that time!
I decided, then, to quickly re-write it.

Interpreter Structure

Let’s start from the Interpreter structure where the basic idea is to have a class for each symbol of the language. The syntax tree of a sentence in the language is an instance of the composite pattern and is used to evaluate the sentence. So, let’s have a look at the class diagram of this part of the project:

UML class Diagram Interpreter Arithmetic Expression

As we can see, in order to implement a composite, a common interface (ExpressionNode) is defined, which imposes two methods to its subclasses: evaluate(), which accepts a Context (a Context is a simple HashMap<VariableName, VariableValue> which allows to evaluate the Expression with different variable values) and calculates recursively the expression result. The second method: accept(), is part of the Visitor Pattern, and we’ll cover it soon. For now let’s see how the evaluate() works.

Evaluate() compute the Expression value recursively, which allows us to write very elegant code. For example, the following is how the Constant class implements evaluate():

public class Constant implements ExpressionNode {

	private double value;

	@Override
	public double evaluate(Context c) {
		return this.value;
	}
}

Simple? Isn’t it? A Constant has only to return its value. Let’s see the other two implementations:

public class Variable implements ExpressionNode {

	private String name;

	@Override
	public double evaluate(Context c) {
		return c.lookup(this.name);
	}
}

A Variable has to perform a lookup on the Context in order to return its double value. But it’s in the Operator class that the magic happens:

public class Operator implements ExpressionNode {

	private Operators operator;
	private ExpressionNode left, right;

	@Override
	public double evaluate(Context c) {
		switch(this.operator){
		case DIV:
			return this.left.evaluate(c) / this.right.evaluate(c);
		case MUL:
			return this.left.evaluate(c) * this.right.evaluate(c);
		case ADD:
			return this.left.evaluate(c) + this.right.evaluate(c);
		default:
			return this.left.evaluate(c) - this.right.evaluate(c);
		}
	}
}

As we can see, in this Class we find the recursive calls (The switch on the Operators Enumeration is used to understand which math operation the method has to use). A simple main method to test this code could be:

public static void main(String args[]){

	// 3+x * 5-y
	Operator add = new Operator(new Constant(3), new Variable("x"), Operator.Operators.ADD);
	Operator min = new Operator(new Constant(5), new Variable("y"), Operator.Operators.MINUS);
	Operator mul = new Operator(add, min, Operator.Operators.MUL);

	// x, y = 1
	Context c = new Context();
	c.assign("x", 1);
	c.assign("y", 1);

	assert mul.evaluate(c) == 16;
	System.out.println("Result: ["+mul.evaluate(c)+"]");

	c.assign("x", 4);
	c.assign("y", 5);

	assert mul.evaluate(c) == 0;
	System.out.println("Result: ["+mul.evaluate(c)+"]");
}

Visitor Structure

Now, in order to visit and print the expression in different ways (postfix, infix, etc.) we need to allow different tree traversals, and the Visitor Pattern is exactly what we need. In essence, the visitor allows one to add new virtual functions to a family of classes (in our case the ExpressionNode classes) without modifying the classes themselves.The visitor takes the instance reference as input, and implements the goal through double dispatch.

UML Class Diagram Visitor Postfix Infix

The double dispatch occurs inside the accept() method, which every NodeExpression subclass will implement with a simple call to the visit() method of the Visitor Object they get as parameter. To the visit() method they will pass their own instance (this), allowing, so doing, to call the right visit method at Run-time.

@Override
public void accept(ExpressionVisitor visitor) {
	visitor.visit(this);
}

Let’s have a look at the Visitor class family:

public abstract class ExpressionVisitor {

	public abstract void visit(Operator operator);

	public void visit(Variable variable) {
		System.out.print(variable.getName());
	}

	public void visit(Constant constant) {
		System.out.print(constant.getValue());
	}
}

public class InfixVisitor extends ExpressionVisitor {

	@Override
	public void visit(Operator operator) {
		operator.getLeft().accept(this);
		System.out.print(operator.getOperator());
		operator.getRight().accept(this);
	}
}

public class PostfixVisitor extends ExpressionVisitor {

	@Override
	public void visit(Operator operator) {
		operator.getLeft().accept(this);
		operator.getRight().accept(this);
		System.out.print(operator.getOperator());
	}
}

As we can see, changing in visit(Operator) the order in which nodes are visited, it changes the entire tree traversals. For example, a postfix visit has to visit first the left child of a node, after the right one and finally itself. Whereas, a infix visit has to visit first the left child, after itself and finally the right child.

A simple main method to see how the visitor works could be the following:

public static void main(String args[]){
	// 3+x * 5-y
	Operator add = new Operator(new Constant(3), new Variable("x"), Operator.Operators.ADD);
	Operator min = new Operator(new Constant(5), new Variable("y"), Operator.Operators.MINUS);
	Operator mul = new Operator(add, min, Operator.Operators.MUL);

	// Postfix Print
	System.out.print("Postfix: ");
	mul.accept(new PostfixVisitor());

	// Infix Print
	System.out.print("Infix: ");
	mul.accept(new InfixVisitor());
}

This code will print:

Postfix: 3.0x+5.0y-*
Infix: 3.0+x*5.0-y

You can find the entire code on github. Anyway, what’s still missing is a parser able to build the syntax tree (what, now, we’re doing into the main method) starting from a plain input string. If I’ll find some free time, I’ll add it. See you guys 😉

Advertisements