说到解释器模式，映入脑海中的便是编程语言中的语法树，以及规则解析相关的内容。
在平时编码中，其实我们或多或少的已经接触到这个解释器设计模式了。比如：使用正则表达式提取相关内容，或者判断是否符合某种格式；
代码语言：javascript复制 boolean result = Pattern.matches("[a-z0-9] ", "12345678abc");
System.out.println(result);//true又如，Spring中的EL对四则运算进行计算：
代码语言：javascript复制// 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();
}
}
}
输出结果
代码语言：javascript复制中序表达式为：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表达式的解析逻辑，一定会对解释器模式有更深入的了解的。
