Click here to Skip to main content
Click here to Skip to main content
Go to top

Interpreter Design Pattern

, 4 May 2011
Rate this:
Please Sign up or sign in to vote.
Interpreter Design Pattern clearly explained with example

You can see this and other great articles on design patterns here.

The Interpreter Design Pattern allows you to build the rules as classes. This design pattern is very powerful in building the rules in a very logical manner. Most of the examples you see uses a programming language grammar as the rules because it's the easiest to demonstrate. However, once you realize the essence of the interpreter pattern you will see that you can apply the rules to any streams of inputs or objects.

The easiest way to understand how the interpreter pattern works is by looking at an example that will lead us to the UML of the interpreter pattern.

There are 2 concepts to understand in the interpreter pattern. The first concept is the Depth First Search. In a depth first search you start off from the top of the tree, and you always go for the leftmost element as you go down the tree. You will gradually finish the left part of the tree first before you do the right part of the tree. 

Below is the diagram of the tree and the order to visit the nodes (from 1 to 7) using Depth First Search:

The second concept is the expression constructs of a language, they are simply the rules of the language. For example we can have the following rules in a programming language:

  • AddExpression = Expression + Expression
  • SubtractExpression = Expression - Expression
  • Expression = NumberExpression | AddExpression | SubtractExpression

We can use these rules to give us a variety of ways to evaluate a statement:

  • Example 1:
    •     Expression = (10 - 2) + 3 = (SubtractExpression) + NumberExpression = Expression + Expression = AddExpression = 11
  • Example 2:
    •     Expression = (10 + 5) - (8 - 2) = (AddExpression) - (SubtractExpression) = Expression - Expression = SubtractExpression = 9

With the understanding of the Depth First Search and the rules of a language, we can build trees that represent the rules. The AddExpression tree will be:

Similarly, the SubtractExpression tree will be:

Taking Example1 as an example, the tree will be:

and if we traverse the tree above using Depth First Search, it will be: +  -  10  2  3

The tree for Example2 will be:

and if we traverse the tree above using Depth First Search, it will be:  -  +  10  5  -  8  2

The depth first search strings are the Reverse Polish Notations, and are commonly used in devices such as the financial calculators. The strings are the user inputs that will be evaluated using the rules of the language to calculate the results.

The interpreter design pattern allow us to take the rules of a language and build them as classes. In the example we have the following classes:

  • AddExpression
  • SubtractExpression
  • NumberExpression

We can then build the UML for the example as shown below:

  • The IExpression interface requires all expression classes to have the Interpret method, which means that all expressions can be interpreted.
  • The NumberExpression class implements the IExpression interface, and since it's just a representation of a number it does not contain other expressions. Expressions that does not contain other expressions are called the TerminalExpressions. 
  • The AddExpression and SubtractExpression class implements the IExpression interface and contains other expressions. Expressions that contains other expressions are called the NonTerminalExpressions. 

Now we can look at the UML of the Interpreter Design Pattern, which is the same as what we have in our example:

Below are the implementation code and the output of the Interpreter Design Pattern. Notice that when given the string input of the Reverse Polish Notation it will interpret the input and produce the correct answer automatically:

class Program
{
    static void Main(string[] args)
    {
        string tokenString = "+ - 10 2 3";
        List<string> tokenList = new List<string>(tokenString.Split(' '));

        IExpression expression = new TokenReader().ReadToken(tokenList);
        Console.WriteLine(expression.Interpret());    // (10 - 2) + 3 = 11

        tokenString = "- + 10 5 - 8 2";
        tokenList = new List<string>(tokenString.Split(' '));

        expression = new TokenReader().ReadToken(tokenList);
        Console.WriteLine(expression.Interpret());   // (10 + 5) - (8 - 2) = 9
    }
}

public interface IExpression
{
    int Interpret();
}

//terminal expression
public class NumberExpression : IExpression
{
    int number;
    public NumberExpression(int i)
    {
        number = i;
    }

    int IExpression.Interpret()
    {
        return number;
    }
}

//nonterminal expression, contains left and right expressions below it
public class AddExpression : IExpression
{
    IExpression leftExpression;
    IExpression rightExpression;

    public AddExpression(IExpression left, IExpression right)
    {
        leftExpression = left;
        rightExpression = right;
    }

    int IExpression.Interpret()
    {
        return leftExpression.Interpret() + rightExpression.Interpret();
    }
}

//nonterminal expression, contains left and right expressions below it
public class SubtractExpression : IExpression
{
    IExpression leftExpression;
    IExpression rightExpression;

    public SubtractExpression(IExpression left, IExpression right)
    {
        leftExpression = left;
        rightExpression = right;
    }

    int IExpression.Interpret()
    {
        return leftExpression.Interpret() - rightExpression.Interpret();
    }
}

public class TokenReader
{
    public IExpression ReadToken(List<string> tokenList)
    {
        return ReadNextToken(tokenList);
    }

    private IExpression ReadNextToken(List<string> tokenList)
    {
        int i;
        if (int.TryParse(tokenList.First(), out i))  //if the token is integer (terminal)
        {
            tokenList.RemoveAt(0);   //process terminal expression
            return new NumberExpression(i);
        }
        else
        {
            return ReadNonTerminal(tokenList);  //process nonTerminal expression
        }
    }

    private IExpression ReadNonTerminal(List<string> tokenList)
    {
        string token = tokenList.First();
        tokenList.RemoveAt(0);   //read the symbol
        IExpression left = ReadNextToken(tokenList); //read left expression
        IExpression right = ReadNextToken(tokenList);  //read right expression

        if (token == "+")
            return new AddExpression(left, right);
        else if (token == "-")
            return new SubtractExpression(left, right);
        return null;
    }
}

Liked this article? You can see this and other great articles on design patterns here.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

DevLake

United States United States
No Biography provided

Comments and Discussions

 
GeneralMy vote of 5 Pinmembersaitmemis11-Nov-11 2:44 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140922.1 | Last Updated 4 May 2011
Article Copyright 2011 by DevLake
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid