设计模式学习笔记(11)解释器

本文实例代码:https://github.com/JamesZBL/java_design_patterns

解释器(Interpreter)模式提供了校验语言的语法或表达式的途径,它属于行为型模式的一种。这种模式通常会提供一个表达式接口,通过这个接口可以解释对应特定环境的上下文。

解释器模式在日常开发的过程中不是很常用,但它在 SQL 解析、符号处理引擎、编译程序等场景中使用非常广泛。

实例

给定一个语言,解释器模式可以定义出其文法的一种表示,并定义一个解释器,该解释器使用该表示来解释语言中的句子。举个简单的例子,在某种计算器中输入 5+1-3*2,每输入一个字符,屏幕上都会显示当前的结果,和这种计算器不同的是另外一种,即一次性输入 5+1-3*2 然后点击 =,直接得出最终结果,后面这种计算器就用到了解释器。

我们输入的这一系列符号可以用二叉树的形式来表示,比如 5+1-3*2

这个二叉树就是一个简单的语法树,在一般的计算机程序设计语言的编译过程中,通常都包含类似的语法树生成的过程。

图中的 5132 都叫做 终结符表达式,所谓终结符就是本身不能再推导出其他符号了,图中的 +-* 这些四则运算符号就是 非终结符表达式 了,因为可以由这些符号分别展开,形成各自的子表达式。对于四则运算表达式,解析的结果就是运算结果,所以运算符号可以抽象出一个接口,包含一个返回值为整数(假设只有整数参与运算)的 interpret() 方法。

Expression.java

ublic abstract class Expression {

  public abstract int interpret() throws Exception;

  @Override
  public abstract String toString();
}

由于加减乘除解释的出来的运算结果显然是不同的,所以分别实现这个接口形成四个类,四则运算符号需要左右两个操作数才能进行解释运算,所以每个运算符都持有两个符号的引用,分别作为其左运算数和右运算数:

加号,PlusExpression.java:

public class PlusExpression extends Expression {

  private Expression expressionLeft;
  private Expression expressionRight;

  public PlusExpression(Expression expressionLeft, Expression expressionRight) {
    this.expressionLeft = expressionLeft;
    this.expressionRight = expressionRight;
  }

  @Override
  public int interpret() throws Exception {
    return expressionLeft.interpret() + expressionRight.interpret();
  }

  @Override
  public String toString() {
    return "+";
  }
}

减号,MinusExpression.java:

public class MinusExpression extends Expression {

  private Expression expressionLeft;
  private Expression expressionRight;

  public MinusExpression(Expression expressionLeft, Expression expressionRight) {
    this.expressionLeft = expressionLeft;
    this.expressionRight = expressionRight;
  }

  @Override
  public int interpret() throws Exception {
    return expressionLeft.interpret() - expressionRight.interpret();
  }

  @Override
  public String toString() {
    return "-";
  }
}

乘号,MultipleExpression.java:

public class MultipleExpression extends Expression {

  private Expression expressionLeft;
  private Expression expressionRight;

  public MultipleExpression(Expression expressionLeft, Expression expressionRight) {
    this.expressionLeft = expressionLeft;
    this.expressionRight = expressionRight;
  }

  @Override
  public int interpret() throws Exception {
    return expressionLeft.interpret() * expressionRight.interpret();
  }

  @Override
  public String toString() {
    return "*";
  }
}

除号,DivisionExpression.java:

public class DivisionExpression extends Expression {

  private Expression expressionLeft;
  private Expression expressionRight;

  public DivisionExpression(Expression expressionLeft, Expression expressionRight) {
    this.expressionLeft = expressionLeft;
    this.expressionRight = expressionRight;
  }

  @Override
  public int interpret() throws Exception{
    return expressionLeft.interpret() / expressionRight.interpret();
  }

  @Override
  public String toString() {
    return "/";
  }
}

对于一个四则运算的算式,除了这四个四则运算符号,就是数字了,所以将数字抽象出一个数字符号类:

NumberExpression.java

public class NumberExpression extends Expression {

  private int number;

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

  public NumberExpression(String numberString) {
    this.number = Integer.parseInt(numberString);
  }

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

  @Override
  public String toString() {
    return "数字";
  }
}

将上文中的算式用二叉树的形式表示,按顺序展开为一个字符序列,即 - + * 5 1 3 2,现在模仿计算器对其进行解释,这里用到了一点数据结构的知识,遍历二叉树通常采用 堆栈 (Stack) 结构来实现:

App.java

public class Application {

  private static final Logger LOGGER = LoggerFactory.getLogger(Application.class);

  public static void main(String[] args) {
    try {
      String tokenString = "- + * 5 1 3 2";
      Stack<Expression> stack = new Stack<>();

      String[] stringList = tokenString.split(" ");
      for (String s : stringList) {
        if (isOperator(s)) {
          Expression expressionRight = stack.pop();
          Expression expressionLeft = stack.pop();
          LOGGER.info("左操作数:{},右操作数:{}", expressionLeft.interpret(), expressionRight.interpret());
          Expression expression = getExpressionInstance(s, expressionLeft, expressionRight);
          LOGGER.info("操作符:{}", expression);
          Expression result;
          if (expression != null) {
            result = new NumberExpression(expression.interpret());
            LOGGER.info("运算结果为:{}", result.interpret());
            stack.push(result);
          }
        } else {
          NumberExpression expression = new NumberExpression(s);
          stack.push(expression);
          LOGGER.info("数字入栈:{}", expression.interpret());
        }
      }
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

  /**
   * 判断字符串是否为四则运算的操作符
   *
   * @param s 待判断的字符串
   *
   * @return 是否为操作符
   */
  public static boolean isOperator(String s) {
    return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
  }

  /**
   * 根据字符串生成四则运算表达式
   *
   * @param s               字符串
   * @param expressionLeft  左表达式
   * @param expressionRight 右表达式
   *
   * @return 四则运算表达式
   */
  public static Expression getExpressionInstance(String s, Expression expressionLeft, Expression expressionRight) {
    if (isOperator(s)) {
      switch (s) {
        case "+": {
          return new PlusExpression(expressionLeft, expressionRight);
        }
        case "-": {
          return new MinusExpression(expressionLeft, expressionRight);
        }
        case "*": {
          return new MultipleExpression(expressionLeft, expressionRight);
        }
        case "/": {
          return new DivisionExpression(expressionLeft, expressionRight);
        }
      }
    }
    return null;
  }
}

总结

解释器主要运用方式就是解释语法树的节点,它将语法解释规则和实现结构,将复杂的解释工作指派到不同的解释器对象中,是什么语法就由什么解释器来解释。对于一棵生成好的语法树,通常由根节点开始解释,不断递归,依次选择适合子节点的解释器来进行解释。

解释器的应用场景:

  • 当一个语言需要解释执行,并可以将该语言中的句子表示为一个抽象语法树的时候,例如 XML 文件或正则表达式
  • 一些重复出现的问题可以用一种简单的语言来进行表达
  • 一个语言的文法较为简单,比如四则运算
  • 当执行效率不是关键和主要关心的问题时可考虑解释器模式,因为大量使用递归循环调用,随着语法的复杂程度加剧,解释器的执行效率会非常低

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.