Interpreter pattern is used for defining a grammar together with a mechanism that understands it.
This pattern can help to parse and understand any kind of statements or expressions like SQL statements, regular expressions, all sorts of languages and so on.
In the Interpreter pattern, a context object and an interface are defined. The context object holds the information that needs to be interpreted. The interface is implemented by objects, and these objects are composed into a structure or into a tree. The context is passed to these object for getting interpreted.
The above mentioned interface defines an interpret(context)
method.
The objects those implement it can be one of two kinds: terminal or non-terminal expression.
Terminal expression has no children interpreter objects, it processes the context itself. Non-terminal expression has children interpreter objects, and it cannot process the context entirely by itself, so it passes it to its children for further processing.
Interpreter is a behavioral pattern.
The next Java example is about an interpreter that receives a mathematical expression and calculates its result. The expression can contain the four basic arithmetic operations. For example: 1 + 2.5 * 4.
The Expression
interface defines the interpret
method
that receives the context
objects.
Now the type of the context
is List<String>
,
but this could be any other type.
The list contains the expression like this: [1, +, 2.5, *, 4]
.
Also worth to mention that, the interpret
method does not have a return type in this example.
package com.programcodex.designpatterns.interpreter;
import java.util.List;
public interface Expression {
public void interpret(List<String> context);
}
The Operation
class implements the Expression
interface.
This abstract class is the base class of the four basic arithmetic operations:
addition, subtraction, multiplication and division.
This and its subclasses are terminal expressions.
It has two abstract methods, those are implemented by its subclasses.
The getOperation
method has to return with an operation symbol that can be:
+
, -
, *
or /
.
The calculate
method gets two numbers and executes the concrete operation with them.
The interpret
method receives the context as a list that contains the expression,
for example: [1, +, 2, +, 3]
.
When an addition happens the getOperation
method returns with the + symbol.
The idx
variable is the index of the first plus symbol in the list.
The a
and b
variables are the numbers before and after the operation symbol.
The calculate
method executes the addition and the result replaces the operation symbol in the list.
Finally the two numbers are removed from the list. Firstly the right one and after the left one.
This order matters because the list getting shorter, so its index positions changing.
package com.programcodex.designpatterns.interpreter;
import java.util.List;
public abstract class Operation implements Expression {
@Override
public void interpret(List<String> context) {
int idx = context.indexOf(getOperation());
float a = Float.parseFloat(context.get(idx - 1));
float b = Float.parseFloat(context.get(idx + 1));
float result = calculate(a, b);
context.set(idx, String.valueOf(result));
context.remove(idx + 1);
context.remove(idx - 1);
}
protected abstract String getOperation();
protected abstract float calculate(float a, float b);
@Override
public String toString() {
return getOperation();
}
}
The next classes are the four basic arithmetic operations.
They are the subclasses of the Operation
class.
The AdditionExpr
class arranges the addition operations.
package com.programcodex.designpatterns.interpreter;
public class AdditionExpr extends Operation {
@Override
protected String getOperation() {
return "+";
}
@Override
protected float calculate(float a, float b) {
return a + b;
}
}
The SubtractionExpr
class arranges the subtraction operations.
package com.programcodex.designpatterns.interpreter;
public class SubtractionExpr extends Operation {
@Override
protected String getOperation() {
return "-";
}
@Override
protected float calculate(float a, float b) {
return a - b;
}
}
The MultiplicationExpr
class arranges the multiplication operations.
package com.programcodex.designpatterns.interpreter;
public class MultiplicationExpr extends Operation {
@Override
protected String getOperation() {
return "*";
}
@Override
protected float calculate(float a, float b) {
return a * b;
}
}
The DivisionExpr
class arranges the division operations.
package com.programcodex.designpatterns.interpreter;
public class DivisionExpr extends Operation {
@Override
protected String getOperation() {
return "/";
}
@Override
protected float calculate(float a, float b) {
return a / b;
}
}
The CalculatorExpr
class also implements the Expression
interface.
This class is a non-terminal expression because it calls other expressions.
It has four Expression
fields for the four operations.
In the interpret
method, it iterates through the context and builds two operation expression lists.
The hiPrecOperations
list contains the higher precedence operations (multiplication and division).
The loPrecOperations
list contains the lower precedence operations (addition and subtraction).
After the for
loop, the lower precedence operations are added to the higher precedence operations,
and the hiPrecOperations
list contains all operations in the right order.
Finally, all interpret
methods of the operation expressions are called.
package com.programcodex.designpatterns.interpreter;
import java.util.ArrayList;
import java.util.List;
public class CalculatorExpr implements Expression {
private final Expression addition = new AdditionExpr();
private final Expression subtraction = new SubtractionExpr();
private final Expression multiplication = new MultiplicationExpr();
private final Expression division = new DivisionExpr();
@Override
public void interpret(List<String> context) {
// Higher precedence operations: * and /
List<Expression> hiPrecOperations = new ArrayList<>();
// Lower precedence operations: + and -
List<Expression> loPrecOperations = new ArrayList<>();
for (String elem : context) {
switch (elem) {
case "+":
loPrecOperations.add(addition);
break;
case "-":
loPrecOperations.add(subtraction);
break;
case "*":
hiPrecOperations.add(multiplication);
break;
case "/":
hiPrecOperations.add(division);
break;
}
}
hiPrecOperations.addAll(loPrecOperations);
System.out.println("Order of the operations: " + hiPrecOperations);
hiPrecOperations.forEach(e -> e.interpret(context));
}
}
And we are done. It’s time to run these things.
The evaluate
method splits the String
mathematical expression at the spaces
and creates the context
object of them.
(More precisely the \s+ means one or more whitespace characters.)
After that, a CalculatorExpr
class is instantiated and
its interpret
method is called with the context
list.
When the interpret
method is done,
the length of the context
list is decremented to one, and that will be the result.
package com.programcodex.designpatterns.interpreter;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class TestInterpreter {
private static final DecimalFormat df = new DecimalFormat("#.##");
public static void main(String[] args) {
evaluate("1 + 2 + 3 + 4"); // 10
evaluate("5 * 5"); // 25
evaluate("0 - 5 / 2"); // -2,5
evaluate("2 * 5 / 3"); // 3,33
evaluate("11 + 3 - 2 * 3 + 9 / 3"); // 11
evaluate("1 + 5 * 5 - 3 * 3 + 1 * 2 * 6 / 4"); // 20
evaluate("3.4 + 2.2 * 3"); // 10
}
private static void evaluate(String mathExpr) {
System.out.println("\nMath expression: " + mathExpr);
List<String> context = Arrays.stream(mathExpr.split("\\s+"))
.collect(Collectors.toList());
Expression calculator = new CalculatorExpr();
calculator.interpret(context);
System.out.println("Result: "
+ df.format(Float.valueOf(context.get(0))));
}
}
The output of the above test class:
The next interpreter takes a list of animals and determines whether they are in ascending order by size.
For example:
- the ant, rabbit, elephant order is valid, but
- the horse, whale, elephant order is invalid.
The Expression
interface defines the interpret
method
that receives a list of animals and returns with a boolean
value.
It returns with true
if the animals are in ascending order;
otherwise, it returns with false
.
package com.programcodex.designpatterns.interpreter2;
import java.util.List;
public interface Expression {
public boolean interpret(List<String> context);
}
There are three implementations for the Expression
interface in this example, and they form a chain.
The first is the ValidationExp
, which is a non-terminal expression.
The interpret
method gets a list of animals and checks the size of it.
At least two elements needed for a valid comparison; otherwise, the result is false
.
If there are enough animals in the list, the next expression is called.
package com.programcodex.designpatterns.interpreter2;
import java.util.List;
public class ValidationExp implements Expression {
private Expression nextExpression;
public ValidationExp(Expression nextExp) {
this.nextExpression = nextExp;
}
@Override
public boolean interpret(List<String> context) {
// At least two animal needed for comparison.
if (context == null || context.size() < 2) {
return false;
}
return nextExpression.interpret(context);
}
}
The RemoveExp
is also a non-terminal expression.
There will be as many instances from this class as animals exist in this example.
It takes an animal and a next expression in its constructor.
The next expression is the next larger animal.
In the interpret
method, it removes the first element from the list
if that is the same animal as the one in the animal
field.
After that, it calls the next expression.
The nextExpression
is also a RemoveExp
instance, and
that removes the next animal from the list if exists and so on.
package com.programcodex.designpatterns.interpreter2;
import java.util.List;
public class RemoveExp implements Expression {
private String animal;
private Expression nextExpression;
public RemoveExp(String animal, Expression nextExp) {
this.animal = animal;
this.nextExpression = nextExp;
}
@Override
public boolean interpret(List<String> context) {
if (!context.isEmpty()
&& animal.equalsIgnoreCase(context.get(0))) {
context.remove(0);
}
return nextExpression.interpret(context);
}
}
If the animals are in ascending order, the list will be empty at the end of the call chain. In all other cases, it will remain one or more animals in the list.
When the list contains an elephant and after a mouse, the elephant is the first element in the list.
When the elephant is removed by the elephant’s instance,
the RemoveExp
of the mouse will have been done, so the mouse remains in the list.
The ResultExp
is the terminal expression in this example.
Finally this receives the list, and if that is empty, then the animals are in ascending order.
package com.programcodex.designpatterns.interpreter2;
import java.util.List;
public class ResultExp implements Expression {
@Override
public boolean interpret(List<String> context) {
return context.isEmpty();
}
}
And we are done. It’s time to run these things.
The expression
field is instantiated in the static
block.
The evaluate
method splits the animal String
at the spaces,
creates the context object of them and
passes it to the interpret
method of the expression
.
At the end of the main
method, there are some invalid test values.
One of them can be arguable.
The mouse horse horse elephant
list is considered to
false
in this implementation, but it can be modified to true
by replacing one keyword in ResultExp
class.
In the interpret
method, the if
has to be replaced with while
.
That’s all.
package com.programcodex.designpatterns.interpreter2;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class TestInterpreter {
private static Expression expression;
static {
// flea ant mouse rabbit horse elephant whale
Expression whale = new RemoveExp("whale", new ResultExp());
Expression elephant = new RemoveExp("elephant", whale);
Expression horse = new RemoveExp("horse", elephant);
Expression rabbit = new RemoveExp("rabbit", horse);
Expression mouse = new RemoveExp("mouse", rabbit);
Expression ant = new RemoveExp("ant", mouse);
Expression flea = new RemoveExp("flea", ant);
Expression validation = new ValidationExp(flea);
expression = validation;
}
public static void main(String[] args) {
System.out.println("Animals in ascending order");
System.out.println("\n###### True cases ##########\n");
evaluate("flea ant mouse rabbit horse elephant whale");
evaluate("ant rabbit elephant");
evaluate("flea whale");
System.out.println("\n###### False cases #########\n");
evaluate("flea ant mouse horse rabbit elephant whale");
evaluate("horse whale elephant");
evaluate("whale flea");
System.out.println("\n###### Invalid values ######\n");
// Zoo is not an animal and has no interpreter.
evaluate("rabbit elephant zoo");
// Each value has to be unique.
evaluate("mouse horse horse elephant");
// At least two animal needed for comparison.
evaluate("horse");
evaluate("");
}
private static void evaluate(String animals) {
List<String> context = Arrays.stream(animals.split("\\s+"))
.collect(Collectors.toList());
boolean result = expression.interpret(context);
System.out.format("%s >> %b%n", animals, result);
}
}
The output of the above test class: