Interpreter pattern for design pattern

It belongs to the behavioral pattern.

Definition of interpreter schema

Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

Given a language, define a representation of its grammar and define an interpreter that uses that representation to interpret sentences in the language.

Structure of the interpreter schema

• AbstractExpression: The abstract interpreter declares an abstract interpretation operation, and this interface is shared by all nodes in the abstract syntax tree.

• TerminalExpression: The terminating interpreter implements the interpretive operation associated with terminators ina grammar. Each terminator in a sentence requires an instance of the class.

• NonterminalExpression: The interpretation operation of a rule ina grammar by a non-terminating interpreter.

• Context: The environment role contains some global information outside of the interpreter.

• Client: The Client builds an abstract syntax tree representing a particular sentence in the language in which the syntax is defined and invokes the explain operation.

  Implementation of the interpreter pattern

  Polish Notation

• Infix expression

  In infix expressions, binary operators are always placed between the two related operators, and the order of operations is determined according to the precedence of the operators, and the parenthesis rule is taken into account. For example: 2 + 5 * (1-4)

• Prefix expression

  Polish logician J.Lukasiewicz in 1929 proposed a Notation that did not require parentheses, writing the operators before the objects, known as prefix expressions, the Polish Notation (PN). For example, 2 + 5 * (1-4) is prefixed with + 2 * 5-1 4.

• Postfix expression

Suffix expressions, also known as Reverse Polish Notation (RPN), are the Reverse of prefix expressions by placing the operation Notation after the operation object. For example, 2 + 5 * (1-4) is expressed in the inverse Polish form: 2 5 1 4 – * +.

Next we implement postfix expressions.

• Expression Abstract Expression class

public interface Expression {
    int interpret(Map<String, Expression> variables);
}Copy the code

• TerminalExpression TerminalExpression: numbers and variables

public class Number implements Expression { private int number; public Number(int number) { this.number = number; } public int interpret(Map<String, Expression> variables) { return number; }}Copy the code

public class Variable implements Expression { private String name; public Variable(String name) { this.name = name; } public int interpret(Map<String, Expression> variables) { if (null == variables.get(name)) return 0; // Either return new Number(0). return variables.get(name).interpret(variables); }}Copy the code

• NonterminalExpression
  
  Non-terminal expressions:+ -operation

public class Minus implements Expression { Expression leftOperand; Expression rightOperand; public Minus(Expression left, Expression right) { leftOperand = left; rightOperand = right; } public int interpret(Map<String, Expression> variables) { return leftOperand.interpret(variables) - rightOperand.interpret(variables); }}Copy the code

public class Plus implements Expression { Expression leftOperand; Expression rightOperand; public Plus(Expression left, Expression right) { leftOperand = left; rightOperand = right; } public int interpret(Map<String, Expression> variables) { return leftOperand.interpret(variables) + rightOperand.interpret(variables); }}Copy the code

public class Evaluator implements Expression {
    private Expression syntaxTree;
    public Evaluator(String expression) {
        Stack<Expression> expressionStack = new Stack<Expression>();
        for (String token : expression.split(" ")) {
            if (token.equals("+")) {
                Expression subExpression = new Plus(expressionStack.pop(), expressionStack.pop());
                expressionStack.push(subExpression);
            } else if (token.equals("-")) {
                // it's necessary remove first the right operand from the stack
                Expression right = expressionStack.pop();
                // ..and after the left one
                Expression left = expressionStack.pop();
                Expression subExpression = new Minus(left, right);
                expressionStack.push(subExpression);
            } else
                expressionStack.push(new Variable(token));
        }
        syntaxTree = expressionStack.pop();
    }
    public int interpret(Map<String, Expression> context) {
        return syntaxTree.interpret(context);
    }
}Copy the code

• The client

public class InterpreterExample { public static void main(final String[] args) { final String expression = "w x z - +"; final Evaluator sentence = new Evaluator(expression); final Map<String, Expression> variables = new HashMap<String, Expression>(); variables.put("w", new Number(5)); variables.put("x", new Number(10)); variables.put("z", new Number(42)); final int result = sentence.interpret(variables); System.out.println(result); }}Copy the code

Context is also defined on the client side, defines expressions, assembles them into the interpreter, passes the Context as a parameter, and the interpreter outputs the result.

conclusion

reference

1. 23 Design patterns (14) : Interpreter patterns
2. wikipedia-Interpreter_pattern