解释器模式浅析

孟君

发布于 2020-06-19 16:11:53

3590

发布于 2020-06-19 16:11:53

说到解释器模式，映入脑海中的便是编程语言中的语法树，以及规则解析相关的内容。

在平时编码中，其实我们或多或少的已经接触到这个解释器设计模式了。比如：使用正则表达式提取相关内容，或者判断是否符合某种格式；

 boolean result = Pattern.matches("[a-z0-9]+", "12345678abc");
 System.out.println(result);//true

又如，Spring中的EL对四则运算进行计算：

// import org.springframework.expression.ExpressionParser;
  //  import org.springframework.expression.spel.standard.SpelExpressionParser;
      ExpressionParser parser = new SpelExpressionParser();
      int i = (Integer)parser.parseExpression("3*6+2 -7*5 +9").getValue();
      System.out.println(i);//-6

如果一种特定类型的问题发生的频率足够高，那么可能就值得将该问题的各个实例表述为一个简单语言中的句子。这样就可以构建一个解释器，该解释器通过解释这些句子来解决该问题。这种场景就是我们今天要讲的解释器模式所适用的。

一. 解释器模式的基本介绍

意图

给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。

结构

解释器模式的基本结构如下：

这里涉及到的参与者有如下几种：

AbstractExpression（抽象表达式）
- 声明一个所有的从具体表达式角色都需要实现的抽象接口。这个接口主要是一个interprete（）方法，称作解释操作。
TerminatalExpression（终结表达式）
- 实现了抽象表达式角色所要求的接口，主要是一个interprete（）
- 文法中的每一个终结符都有一个具体终结表达式与之对应
NonterminatalExpression（非终结表达式）
- 对文法中的每一条规则R=R1R2....Rn都需要一个具体的非终结符表达式类
- 对每一个R1R2....Rn中的符号都维护一个AbstractExpression类型的实例变量
- 为文法中的非终结符实现解释（Interprete）操作。解释（Interprete）一般要递归地调用表示R1到Rn的那些对象的操作。
Context（上下文）
- 包含解释器之外的一些全局信息。
Client（客户端）
- 构建（或被给定）表示该文法定义的语言中的一个特定的句子的抽象语法树。该抽象语法树由NonterminalExpression和TerminalExpression的实例装配而成
- 调用解释操作interprete()

参与者如何协作？

1、Client构建（或被给定）一个句子，它是NonterminalExpression和TerminalExpression的实例的一个抽象语法树，然后初始化上下文并调用解释操作。

2、每一个非终结符表达式节点定义相应子表达式的解释操作。而各终结符号表达式的解释操作构成了递归的基础。

3、每一个节点的解释操作用上下文来存储和访问解释器的状态。

二. 解释器模式的示例

接下来以一个计算算术运算表达式的实例来说明解释器模式，主要包含如下几个步骤：

将算术表达式转换成后序表达，如3+2*5转成后序表达式为325*+，其中为了方便，本示例算术表达式中的数字为0-9小于10的数进行计算，运算符号包含加减乘除（+-*/）
使用栈来操作后序表达式的计算。
- 如果是数字，直接入栈，数字表达式为终结符表达式
- 如果是运算符，则需要从栈弹出两个数字表达式，根据运算符计算两个数字表达式的值，将计算后的值，压入栈。
- 最后栈中的元素就是计算后的值
抽象表达式

package com.wangmengjun.tutorial.designpattern.interprete;

public interface Expression {

   int interpret();
   
}

数字表达式（终结符表达式）

package com.wangmengjun.tutorial.designpattern.interprete;

public class NumberExpression implements Expression{

  private int value;
   
  public NumberExpression(int value){
        this.value=value;
  }
      
  @Override
  public int interpret() {
    return this.value;
  }

}

运算符表达式（非终结符表达式），包括加减乘除四个

package com.wangmengjun.tutorial.designpattern.interprete;

public class AdditionExpression implements Expression{

  private Expression leftExpression;
  
  private Expression rightExpression;
  
  public AdditionExpression(Expression leftExpression, Expression rightExpression) {
    super();
    this.leftExpression = leftExpression;
    this.rightExpression = rightExpression;
  }

  @Override
  public int interpret() {
    return leftExpression.interpret() + rightExpression.interpret();
  }
  
  @Override
  public String toString() {
    return "+";
  }

}

package com.wangmengjun.tutorial.designpattern.interprete;

public class SubtractionExpression implements Expression{

  private Expression leftExpression;
  
  private Expression rightExpression;
  
  public SubtractionExpression(Expression leftExpression, Expression rightExpression) {
    super();
    this.leftExpression = leftExpression;
    this.rightExpression = rightExpression;
  }

  @Override
  public int interpret() {
    return leftExpression.interpret() - rightExpression.interpret();
  }
  
  @Override
  public String toString() {
    return "-";
  }

}

package com.wangmengjun.tutorial.designpattern.interprete;

public class MultiplicationExpression implements Expression {

  private Expression leftExpression;
  
  private Expression rightExpression;
  
  public MultiplicationExpression(Expression leftExpression, Expression rightExpression) {
    super();
    this.leftExpression = leftExpression;
    this.rightExpression = rightExpression;
  }

  @Override
  public int interpret() {
    return leftExpression.interpret() * rightExpression.interpret();
  }

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

}

package com.wangmengjun.tutorial.designpattern.interprete;

public class DivisionExpression implements Expression {

  private Expression leftExpression;
  
  private Expression rightExpression;
  
  public DivisionExpression(Expression leftExpression, Expression rightExpression) {
    super();
    this.leftExpression = leftExpression;
    this.rightExpression = rightExpression;
  }

  @Override
  public int interpret() {
    return leftExpression.interpret() / rightExpression.interpret();
  }

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

}

中序转后序表达式工具类
- 初始化一个运算符栈
- 左到右依次读取中缀表达式字符串的每一个字符
- 如果是左括号，直接入栈
- 如果是操作数，送到后缀表达式
- 如果是运算符，则：
  - 若栈为空，入栈
  - 若栈非空。如果运算符优先级高于栈顶运算符，入栈；否则，反复弹出栈顶优先级低的运算符送到后缀表达式，最后将当前运算符入栈。
- 如果是右括号，反复将栈顶运算符弹出送到后缀表达式直到遇左括号，弹出左括号
- 重复以上步骤直到字符读取完毕。若运算符栈非空，则将栈中剩余所有运算符送到后缀表达式中

package com.wangmengjun.tutorial.designpattern.interprete;

import java.util.Stack;

public final class CalculatorUtil {

  private static final String OPERATORS = "+-*/";

  private CalculatorUtil() {
  }

  public static String convert2Postfix(String infixExpr) {
    char[] chars = infixExpr.toCharArray();
    Stack<Character> stack = new Stack<Character>();
    StringBuilder out = new StringBuilder(infixExpr.length());

    for (char c : chars) {
      if (isOperator(c)) {
        while (!stack.isEmpty() && stack.peek() != '(') {
          if (operatorGreaterOrEqual(stack.peek(), c)) {
            out.append(stack.pop());
          } else {
            break;
          }
        }
        stack.push(c);
      } else if (c == '(') {
        stack.push(c);
      } else if (c == ')') {
        while (!stack.isEmpty() && stack.peek() != '(') {
          out.append(stack.pop());
        }
        if (!stack.isEmpty()) {
          stack.pop();
        }
      } else if (Character.isDigit(c)) {
        out.append(c);
      }
    }
    while (!stack.empty()) {
      out.append(stack.pop());
    }
    return out.toString();
  }

  private static int getPrecedence(char operator) {
    int ret = 0;
    if (operator == '-' || operator == '+') {
      ret = 1;
    } else if (operator == '*' || operator == '/') {
      ret = 2;
    }
    return ret;
  }

  private static boolean operatorGreaterOrEqual(char op1, char op2) {
    return getPrecedence(op1) >= getPrecedence(op2);
  }

  public static boolean isOperator(char val) {
    return OPERATORS.indexOf(val) >= 0;
  }

}

客户端类

package com.wangmengjun.tutorial.designpattern.interprete;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Client {

  public static void main(String[] args) {
    
    List<String> candidates = new ArrayList<>();
    candidates.add("3 + 2 * 5");
    candidates.add("3 + 6 / 2 * 4 / 2");
    candidates.add("3 + 6 / 2 * 4 + 3 * 5 + 9");
    candidates.add("3 * 9 + 7 / 2 -8 + 3 * 6");
    Client client = new Client();
    for(String infixExpr : candidates) {
      System.out.println("中序表达式为：" + infixExpr);
      String postfixExpr = CalculatorUtil.convert2Postfix(infixExpr);
      System.out.println("后序表达式为：" + postfixExpr);
      
      int result = client.doInterprete(postfixExpr);
      System.out.println(infixExpr+" = " + result);
      System.out.println();
    }
    
  }
  
  public int doInterprete(String postfixExpr) {
    Stack<Expression> expressionStack = new Stack<>();
    char[] chars = postfixExpr.toCharArray();
    for(char c : chars) {
        if(Character.isDigit(c)) {
          expressionStack.push(new NumberExpression( c-'0'));
        }else if(CalculatorUtil.isOperator(c)) {
        Expression rightExpression = expressionStack.pop();
        Expression leftExpression = expressionStack.pop();
        Expression operatorExpression = this.getExpressionByOperator(c, leftExpression, rightExpression);
        expressionStack.push(new NumberExpression(operatorExpression.interpret()));
      }
    }
    return expressionStack.pop().interpret();
  }
  
  private Expression getExpressionByOperator(char c,  Expression leftExpression, Expression rightExpression ) {
    switch(c) {
      case '+' :
        return new AdditionExpression(leftExpression, rightExpression);
      case '-' :
        return new SubtractionExpression(leftExpression, rightExpression);
      case '*' :
        return new MultiplicationExpression(leftExpression, rightExpression);
      case '/' :
        return new DivisionExpression(leftExpression, rightExpression);
      default:
        throw new IllegalArgumentException();
    }
  }
  

}

输出结果

中序表达式为：3 + 2 * 5
后序表达式为：325*+
3 + 2 * 5 = 13

中序表达式为：3 + 6 / 2 * 4 / 2
后序表达式为：362/4*2/+
3 + 6 / 2 * 4 / 2 = 9

中序表达式为：3 + 6 / 2 * 4 + 3 * 5 + 9
后序表达式为：362/4*+35*+9+
3 + 6 / 2 * 4 + 3 * 5 + 9 = 39

中序表达式为：3 * 9 + 7 / 2 -8 + 3 * 6
后序表达式为：39*72/+8-36*+
3 * 9 + 7 / 2 -8 + 3 * 6 = 40

就这样，一个简单的根据后缀表达式语法，使用解释器模式计算结果的示例就完成了。

三. 小结

解释器模式的优缺点：

优点：

（1）：易于改变和扩展语法。因为该模式使用类来表示文法规则，你可以使用继承来改变或扩展该文法。已有的表达式可被增量式地改变，而新的表达式可被定义为旧表达式的变体。

（2）：也易于实现文法。定义抽象语法树中各节点的类的实现大体类似。这些类易于直接编写，通常它们也可用一个编译器或语法分析程序生成器自动生成。

缺点：

（1）：复杂的文法难以维护。解释器模式为文法中的每一条规则至少定义一个类。因此包含许多规则的文法可能难以维护。

适应性

如果一种特定类型的问题发生的频率足够高，那么可能就值得将该问题的各个实例表述为一个简单语言中的句子。这样就可以构建一个解释器，该解释器通过解释这些句子来解决该问题。例如，使用正则表达式来匹配字符串集合。

有兴趣的读者，可以去研读一下Spring EL表达式的解析逻辑，一定会对解释器模式有更深入的了解的。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-06-13，如有侵权请联系 cloudcommunity@tencent.com 删除

正则表达式

编程算法

express

本文分享自孟君的编程札记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

正则表达式

编程算法

express

登录后参与评论

0 条评论

热度