We’ll start slowly, only dealing with the four binary basic operations: addition, subtraction, multiplication and division. Even though we defined a concise set of operations, I need to be even more humble in order to achieve our goals, and that’s why I’ll choose one of these operations to get started with the fun.
How about we begin with the addition operation? Sounds easy good to me. Doing that will lead the way to the remainder operations (I mean subtraction, multiplication and division operations). We can represent our math expression with a limited context-free grammar like this:
MathExp -> VariableExp | Constant | AddExp | '(' MathExp ')'
AddExp -> MathExp + MathExp
VariableExp -> a | b | ... | z
Constant -> 0 | 1 | ... | 9
Let’s write a test first (using JUnit 4): if an ordinary ‘a + b’ expression with ‘a = 2’ and ‘b = 4’ must be solved, one could think in the following API (specially if you read about the GoF Interpreter pattern):
@Test
public void testAddExpression() {
final VariableExp a = new VariableExp("a");
final VariableExp b = new VariableExp("b");
final AdditionExp add = new AdditionExp(a, b);
final Context context = new Context();
context.assign(a, 2);
context.assign(b, 4);
final Integer result = add.evaluate(context);
Assert.assertSame(6, result);
}
This code will not work, since VariableExp, AdditionExp and Constant classes doesn’t even exist yet. The next step is to create these classes with its constructors and methods, and hence compile the source without errors. After that let’s implement this code with help of the tests we have written and the Interpreter pattern.
“The Interpreter pattern uses a class to represent each grammar rule. Symbols on the right-side of the rule are instance variables of these classes” (Gamma et al, 1995, p. 243).
public class VariableExp {
private final String name;
public VariableExp(String name) {
this.name = name;
}
public Integer evaluate(Context context) {
return context.lookup(name);
}
String getName() {
return name;
}
}
public class Context {
private final Map map = new HashMap();
public void assign(VariableExp var, int value) {
map.put(var.getName(), value);
}
public Integer lookup(String varName) {
return map.get(varName);
}
}
public class AdditionExp {
private final VariableExp operand1;
private final VariableExp operand2;
public AdditionExp(VariableExp operand1, VariableExp operand2) {
this.operand1 = operand1;
this.operand2 = operand2;
}
public Integer evaluate(Context context) {
return operand1.evaluate(context) + operand2.evaluate(context);
}
}
This is a very simple implementation of such a thing with a fancy name like an “interpreter to math expression” (that maybe sounds like an Einstein thing), but we got it: the test runs smoothly. It happens that often we deal with constants besides variables in expressions, like ‘a + (-5) = -3’. This thing of writing tests before implementing code seems just fine, so I will stick with it.
@Test
public void testAddExpressionWithConstant() {
final VariableExp a = new VariableExp("a");
final AdditionExp add = new AdditionExp(a, new Constant(-5));
final Context context = new Context();
context.assign(a, 2);
final Integer result = add.evaluate(context);
Assert.assertSame(-3, result);
}
Again we need first to make the code compile and, to do that, create the class Constant. But this time only creating a class doesn’t solve all our problems. The AdditionExp constructor demands a VariableExp and Constant isn’t one. In fact, the Interpreter pattern ask for us to define an interface representing the expressions, something we have not done yet. We proceed creating the MathExp interface.
public interface MathExp {
Integer evaluate(Context context);
}
The MathExp interface defines the evaluate method, an API already part of VariableExp and AddExp, what makes sense whereas both are expressions.
public class VariableExp implements MathExp {
private final String name;
public VariableExp(String name) {
this.name = name;
}
@Override
public Integer evaluate(Context context) {
return context.lookup(name);
}
String getName() {
return name;
}
}
public class AdditionExp implements MathExp {
private final MathExp operand1;
private final MathExp operand2;
public AdditionExp(MathExp operand1, MathExp operand2) {
this.operand1 = operand1;
this.operand2 = operand2;
}
@Override
public Integer evaluate(Context context) {
return operand1.evaluate(context) + operand2.evaluate(context);
}
}
The Constant implementation is also straightforward:
public class Constant implements MathExp {
private final Integer value;
public Constant(Integer value) {
this.value = value; }
@Override
public Integer evaluate(Context context) {
return value;
}
}
That’s enough to make the testAddExpressionWithConstant succeed. Until now, we saw only the simplest forms of addition expressions, hence let’s try something more evolved. How difficult would be implemented ‘a + b + c’, given ‘a = 2, b = 4, c = 10’? The test below shows what we want to do.
@Test
public void testCompositeAddExpression() {
final VariableExp a = new VariableExp("a");
final VariableExp b = new VariableExp("b");
final VariableExp c = new VariableExp("c");
final AdditionExp add = new AdditionExp(a, new AdditionExp(b, c));
final Context context = new Context();
context.assign(a, 2);
context.assign(b, 4);
context.assign(c, 10);
final Integer result = add.evaluate(context);
Assert.assertSame(16, result);
}
Now we run the test, which already works without additional implementation! That’s because “the abstract syntax tree is an instance of the Composite pattern” (Gamma et al, p. 255).
new AdditionExp(a, new AdditionExp(b, c))
At this point we achieved the basis for the math expressions. And enough of addition operations! Following the same steps that brought us here should lead us very easily to subtraction, multiplication and division interpreters (although a division operation returning only Integer‘s is not useful at all, something we’ll have to get along for now). Simply replace the plus sign (‘+’) in the evaluate method by the subtraction sign (‘-‘) to implement the SubtractionExp class and so on. Now, we are able to play with a more complex expression like ‘((a * c) + (b – c))’:
AdditionExp moreComplexExpression = new AdditionExp(new MultiplicationExp(a, c), new SubtractionExp(b, c));
In that case it’s also necessary to expand the grammar definition for the math expressions:
MathExp -> VariableExp | Constant | AddExp | SubtractionExp |
MultiplicationExp | DivisionExp | '(' MathExp ')'
AddExp -> MathExp + MathExp
SubtractionExp -> MathExp - MathExp
MultiplicationExp -> MathExp * MathExp
DivisionExp -> MathExp / MathExp
VariableExp -> a | b | ... | z
Constant -> 0 | 1 | ... | 9
Currently we have a simple interpreter to the simplest math expressions. However we are responsible for creating the abstract syntax tree, what on the other hand can be done with a table-driven parser (as LL or LR parser).
That’s it for the time being.
Bibliography
Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995. ISBN: 0201633612.
Kent Back. Test-Driven Development by Example. Addison-Wesley, 2003. ISBN: 0321146530.
