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
trait Expression {
def interpret(): Int
}
Lets code the non terminal concrete implementation of expression
class Addition(right: Expression, left: Expression) extends Expression {
override def interpret(): Int=
{
left.interpret()+right.interpret()
}
}
class Multiplication(right: Expression, left: Expression) extends Expression {
override def interpret(): Int=
{
left.interpret()*right.interpret()
}
}
class Substraction(right: Expression, left: Expression) extends Expression {
override def interpret(): Int=
{
left.interpret()-right.interpret()
}
}
Lets code the terminal concrete implementation
class Number(n: Int) extends Expression {
override def interpret(): Int = n
}
Lets code a factory which based on a token creates an expression and returns the same. As we can see in the below code we are using the by-name parameters which is a scala feature. Here we are declaring a parameter as left: => Expression which tells scala to evaluate left only when it is used.
object ExpressionFactory {
def apply(operator: String, left: => Expression, right: => Expression): Option[Expression] =
operator match {
case "+" => Some(new Addition(right, left))
case "-" => Some(new Substraction(right, left))
case "*" => Some(new Multiplication(right, left))
case i if i.matches("\\d+") => Some(new Number(i.toInt))
case _ => None
}
}
Lets code an interpreter class that just gets an expression and calls the interpret method on it
class Interpreter {
def interpret(expression: Expression): Int = expression.interpret()
}
Lets code the parser 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 and pass it as a parameter to our factory class. As we are using by-name feature of scala the pop will be only called on the non terminal expression and it will not be called on terminal expression.
class Parser {
// val expr1 = "1 2 3 4 5 * * - +" // 1 + 2 - 3 * 4 * 5 = -57
def parse(expression: String): Expression =
{
var tokenizer = expression.split(" ")
tokenizer.foldLeft(scala.collection.mutable.Stack[Expression]()) {
case (result, token) =>
val item = ExpressionFactory(token.toString, result.pop(), result.pop())
item.foreach(result.push)
result
}.pop()
}
}
Finally lets code the test class
object Test extends App{
val expr1 = "1 2 3 4 5 * * - +" // 1 + 2 - 3 * 4 * 5 = -57
val parser = new Parser
val interpreter = new Interpreter
println(interpreter.interpret(parser.parse(expr1)))
}