Implementation

The interpreter pattern uses the composite pattern to define the internal representation of the object structure. In addition to that, it adds the implementation to interpret an expression and to convert it to the internal structure. For this reason, the interpreter pattern falls within the behavioral patterns category. The class diagram is as follows:

The interpreter pattern is composed of the following classes:

• Context: This is used to encapsulate the information that is global to the interpreter and needs to be accessed by all concrete interpreters.
• AbstractExpression: An abstract class or interface that declares the interpret method executed, which should be implemented by all the concrete interpreters.
• TerminalExpression: An interpreter class which implements the operations associated with the terminal symbols of the grammar. This class must always be implemented and instantiated, as it signals the end of the expression.
• NonTerminalExpression: These are classes that implement different rules or symbols of the grammar. For each one, there should be one class created.

The interpreter pattern is used in practice to interpret regular expressions. It's a good exercise to implement the interpreter pattern for such a scenario; however, we'll choose a simple grammar for our example. We are going to apply it to parse a simple function with one variable: f(x).

To make it even simpler, we are going to choose the Reverse Polish notation. This is a notation in which the operands are added at the end of the operators. The 1 + 2 becomes 1 2 +; (1+2)*3 becomes 1 2 + 3 *. The advantage is that we no longer need parentheses, so it simplifies our task.

The following code creates an interface for expressions:

public interface Expression 
{
  public float interpret();
}

Now we need to implement the concrete classes. We need the following elements:

• Number: This will interpret the numbers
• Operator classes (+,-,*,/): For the following example, we will use plus (+) and minus (-):

public class Number implements Expression 
{
  private float number;
  public Number(float number) 
  {
    this.number = number; 
  }
  public float interpret() 
  {
    return number;
  }
}

Now we reach the difficult part. We need to implement the operators. The operators are composite expressions, which are composed of two expressions:

public class Plus implements Expression 
{
  Expression left;
  Expression right;
  public Plus(Expression left, Expression right) 
  {
    this.left = left;
    this.right = right; 
  }
  public float interpret() 
  {
    return left.interpret() + right.interpret();
  }
}

Similarly, we have a minus implementation as follows:

public class Minus implements Expression 
{
  Expression left;
  Expression right;
  public Minus(Expression left, Expression right) 
  {
    this.left = left;
    this.right = right;
  }
  public float interpret() 
  {
    return right.interpret() - left.interpret();
  }
}

We can see now that we've created the classes that allow us to build a tree in which operations are nodes, and variables and numbers are leaves. The structure can be quite complex and can be used to interpret an expression.

Now we have to write the code to build the tree using the classes we've created:

public class Evaluator
{ 
  public float evaluate(String expression) 
  { 
    Stack<Expression> stack = new Stack<Expression>(); 
    float result =0; 
    for (String token : expression.split(" ")) 
    { 
      if  (isOperator(token)) 
      { 
        Expression exp = null; 
        if(token.equals("+")) 
        exp = stack.push(new Plus(stack.pop(), stack.pop())); 
        else if (token.equals("-")) 
        exp = stack.push(new Minus(stack.pop(), stack.pop())); 
        if(null!=exp) 
        { 
          result = exp.interpret(); 
          stack.push(new Number(result)); 
        } 
      } 
      if  (isNumber(token)) 
      { 
        stack.push(new Number(Float.parseFloat(token))); 
      } 
    } 
    return result; 
  } 
  private boolean isNumber(String token) 
  { 
    try 
    { 
      Float.parseFloat(token); 
      return true; 
    } 
    catch(NumberFormatException nan) 
    { 
      return false; 
    } 
  } 
  private boolean isOperator(String token) 
  { 
    if(token.equals("+") || token.equals("-")) 
    return true; 
    return false; 
  } 
  public static void main(String s[]) 
  { 
    Evaluator eval = new Evaluator(); 
    System.out.println(eval.evaluate("2 3 +")); 
    System.out.println(eval.evaluate("4 3 -")); 
    System.out.println(eval.evaluate("4 3 - 2 +")); 
  } 
}