说到解释器模式,映入脑海中的便是编程语言中的语法树,以及规则解析相关的内容。
在平时编码中,其实我们或多或少的已经接触到这个解释器设计模式了。比如:使用正则表达式提取相关内容,或者判断是否符合某种格式;
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
如果一种特定类型的问题发生的频率足够高,那么可能就值得将该问题的各个实例表述为一个简单语言中的句子。这样就可以构建一个解释器,该解释器通过解释这些句子来解决该问题。这种场景就是我们今天要讲的解释器模式所适用的。
意图
给定一个语言,定义它的文法的一种表示,并定义一个解释器,这个解释器使用该表示来解释语言中的句子。
结构
解释器模式的基本结构如下:
这里涉及到的参与者有如下几种:
参与者如何协作?
1、Client构建(或被给定)一个句子,它是NonterminalExpression和TerminalExpression的实例的一个抽象语法树,然后初始化上下文并调用解释操作。
2、每一个非终结符表达式节点定义相应子表达式的解释操作。而各终结符号表达式的解释操作构成了递归的基础。
3、每一个节点的解释操作用上下文来存储和访问解释器的状态。
接下来以一个计算算术运算表达式的实例来说明解释器模式,主要包含如下几个步骤:
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表达式的解析逻辑,一定会对解释器模式有更深入的了解的。