Interpreter Design Pattern

The Interpreter Design Pattern is used to model a grammar of a language using a set of classes along with an interpreter that uses the representation to interpret sentences in the language. The definitions of a language grammar is represented as hierarchical representation of Expression classes, where each expression class is cable of interpreting and evaluating itself.

Let's take an example of an algebraic expression 2 + 3. To model this expression we need ConstantExpression that represents the constant operands(2 and 3) and then AndExpression that takes two ConstantExpression expressions operands and performs addition operation. All Expression classes must implement a common interface 'Expression'.

Above expression can Modelled as :
AndExpression(ConstantExpression(2), ConstantExpression(3))

Similarly, (2 + 6) + (1 + 9) can be modelled as:
AndExpression(AndExpression(ConstantExpression(2), ConstantExpression(6)), AndExpression(ConstantExpression(1), ConstantExpression(9)))

Advantages of Interpreter Pattern

  • It defines a class bases hierarchical representation of language grammar.
  • We can represent each language grammar rules(semantics) as a class implementing a common evaluate interface. It becomes easy to implement the language because parser treats each rule identically.
  • It helps in segregating the ownership of a each grammar rule to a particular class.
  • Each expression class hides it's specific evaluation logic from language parser.
  • We can extend the language by adding more expressions or change the evaluation logic of any expression without modifying language parser code.

When we should use Interpreter Pattern

  • It is not suitable for building a whole large interpreter for a language. It can be used when the grammar of the language is simple.
  • When we want to model a simple a recursive grammar.
  • When simple implementation is high priority then than efficiency.

Implementation of Interpreter Design Pattern

The Expression interface requires all expression classes to have common 'evaluate' method which ensure all expressions can be handled equally.

Expression.java
public interface Expression {
    public int evaluate();
}

The WholeNumber class implements the Expression interface and it represents a number operand. Inside evaluate method, it just returns the numerical value. In the arithmetic expression tree, it is known as TerminalExpressions and represents the leaf node.

WholeNumber.java
public class WholeNumber implements Expression {
    int number;

    public WholeNumber(int number) {
        this.number = number;
    }

    public WholeNumber(String str) {
        this.number = Integer.parseInt(str);
    }

    @Override
    public int evaluate() {
        return number;
    }
}

Now we will create concrete implementation of Expression interface to represent Addition, Subtraction, Multiply and Division binary operations. It contains two Expressions as operands and represents the internal nodes of expression tree also known as NonTerminalExpressions.

Addition.java
public class Addition implements Expression {
    Expression leftOperand;
    Expression rightOperand;
 
    public Addition(Expression leftOp, Expression rightOp){
        this.leftOperand = leftOp;
        this.rightOperand = rightOp;
    }
 
    @Override
    public int evaluate(){
        return leftOperand.evaluate() + rightOperand.evaluate();
    }
}

Subtraction.java
public class Subtraction implements Expression {
    Expression leftOperand;
    Expression rightOperand;
 
    public Subtraction(Expression leftOp, Expression rightOp){
        this.leftOperand = leftOp;
        this.rightOperand = rightOp;
    }
 
    @Override
    public int evaluate(){
        return leftOperand.evaluate() - rightOperand.evaluate();
    }
}

Multiply.java
public class Multiply implements Expression {
    Expression leftOperand;
    Expression rightOperand;
 
    public Multiply(Expression leftOp, Expression rightOp){
        this.leftOperand = leftOp;
        this.rightOperand = rightOp;
    }
 
    @Override
    public int evaluate(){
        return leftOperand.evaluate() * rightOperand.evaluate();
    }
}

Divide.java
public class Divide implements Expression {
    Expression numerator;
    Expression denominator;
 
    public Divide(Expression numerator, Expression denominator){
        this.numerator = numerator;
        this.denominator = denominator;
    }
 
    @Override
    public int evaluate(){
        try {
            return numerator.evaluate() / denominator.evaluate();
        } catch (ArithmeticException e) {
            System.out.println("Division by Zero Exception");
            throw e;
        }
    }
}

InterpreterPatternExample is the arithmetic expression parser that takes a postfix expression and evaluate it using above expression classes. In postfix representation of an expression the operator comes after the operand. Example (1 2 +) is the postfix representation of (1 + 2)

InterpreterPatternExample.java
import java.util.Stack;

public class InterpreterPatternExample {
    public static void main(String args[]) {
 Stack stack = new Stack();
 String postFix = "5 3 * 2 + 1 - 4 /"; // (5 * 3 + 2 - 1)/4

 String[] tokenList = postFix.split(" ");
 for (String s : tokenList) {
     if (isOperatorString(s)) {
  Expression rightOp = (Expression)stack.pop();
  Expression leftOp = (Expression)stack.pop();
  Expression operator = getOperatorHandler(s, leftOp,
   rightOp);
  int result = operator.evaluate();
  stack.push(new WholeNumber(result));
     } else {
  Expression num = new WholeNumber(s);
  stack.push(num);
     }
 }
 System.out.println(((Expression)stack.pop()).evaluate());
    }

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

    public static Expression getOperatorHandler(String str, Expression left,
     Expression right) {
 switch (str) {
     case "+":
  return new Addition(left, right);
     case "-":
  return new Subtraction(left, right);
     case "*":
  return new Multiply(left, right);
     case "/":
  return new Divide(left, right);
     default:
  return null;
 }
    }
}

Output

4

Important points about Interpreter pattern
  • Interpreter can be used to implement a simple language grammar.
  • This pattern comes under behavioral design pattern.

Related Topics
Mediator Design Pattern
Bridge Design Pattern
Prototype Design Pattern
Builder Design Pattern
Factory Design Pattern
Strategy Design Pattern
Memento Design Pattern
State Design Pattern
Filter Design Pattern
Composite Design Pattern
List of Design Patterns