The interpreter pattern is a behavioural design pattern that specifies how to evaluate sentences in a language. The basic idea is to have a class for each symbol (terminal or nonterminal) in a specialized computer language. The syntax tree of a sentence in the language is an instance of the composite pattern and is used to evaluate (interpret) the sentence for a client.

In this pattern there is terminal expression and nonterminal expression. Terminal expression is an expression which when building the syntax tree of an expression, it will have no other children and will be the leaf node. Non terminal expression will have children expressions and this is how the entire syntax tree is built. In our example below Number class is a terminal expression and Addition,Multiplication and Substraction are the nonterminal expression

Below is the class diagram for this pattern

Lets take an example of postfix evaluation where 1 + 2 will be represented as 1 2 +. We will add support for addition, subtraction and multiplication.

Below is class diagram which want to achieve . If we look closely we are using composite pattern is also used in interpreter pattern.

Lets code the example

Expression interface

public interface Expression {
public int interpret();
}

Lets code the non terminal concrete implementation of expression

public class Addition implements Expression{

private Expression left;

private Expression rignt;

public Addition(Expression left, Expression rignt) {
super();
this.left = left;
this.rignt = rignt;
}

@Override
public int interpret() {
// TODO Auto-generated method stub
return left.interpret()+rignt.interpret();
}

}

public class Multiplication implements Expression {
private Expression left;

private Expression rignt;

public Multiplication(Expression left, Expression rignt) {
super();
this.left = left;
this.rignt = rignt;
}

@Override
public int interpret() {
// TODO Auto-generated method stub
return left.interpret() * rignt.interpret();
}

}

public class Substraction implements Expression{

private Expression left;

private Expression rignt;

public Substraction(Expression left, Expression rignt) {
super();
this.left = left;
this.rignt = rignt;
}

@Override
public int interpret() {
// TODO Auto-generated method stub
return left.interpret() - rignt.interpret();
}
}

Lets code the terminal concrete implementation

public class Number implements Expression {

private int number;

public Number(int number) {
super();
this.number = number;
}

public int getNumber() {
return number;
}

public void setNumber(int number) {
this.number = number;
}

@Override
public int interpret() {
// TODO Auto-generated method stub
return getNumber();
}

}

Lets code our interpreter which takes the postfix expression and evaluates the same.Here we are reading the token one by one and loop till end of expression . We check whether the element is a number if it is a number then we push it to a stack or else we pop two elements from stack apply the operator push the result back to stack

import java.util.Stack;

public class Parser {
public static void main(String args[]) {
String tokenString = "1 2 3 4 5 * * - +"; // 1 + 2 - 3 * 4 * 5 = -57
Stack<Expression> stack = new Stack<Expression>();

String[] tokenList = tokenString.split(" ");
for (String s : tokenList)

{
if (isOperator(s)) {
Expression rightExpression = stack.pop();
Expression leftExpression = stack.pop();
Expression operator = getOperatorInstance(s, leftExpression, rightExpression);
int result = operator.interpret();
stack.push(new Number(result));
} else {
Expression i = new Number(Integer.parseInt(s));
stack.push(i);
}
}
System.out.println("Result: " + stack.pop().interpret());

}

public static boolean isOperator(String s) {
if (s.equals("+") || s.equals("-") || s.equals("*"))
return true;
else
return false;
}

public static Expression getOperatorInstance(String s, Expression left, Expression right) {

if (s.equals("+")) {
return new Addition(left, right);
} else if (s.equals("-")) {
return new Substraction(left, right);
} else if (s.equals("*")) {
return new Multiplication(left, right);
}
return null;
}
}