xyZGHio

本是青灯不归客,却因浊酒恋风尘

0%

GoF设计模式(十五):Interpreter Pattern 解释器模式

Interpreter Pattern解释器模式,其是一种在日常开发很少会用到的行为型设计模式

abstract.jpeg

模式思想

有的时候,我们可能需要自己创建一个新的编程语言或表达式,同时针对这个新语言或表达式也会有一些特定的文法规则。这个时候我们就可以通过解释器模式,来解释、执行这个新的语言或表达式。故该模式常见的应用场景:正则表达式、SQL解析、XML解析等等。在本文的例子中,我们将会通过解释器模式来实现四则运算(加、减、乘、除)

在解释器模式中,其有以下几个角色:

  • 抽象表达式:其是一个抽象角色,定义了具体的表达式角色需要实现的interpreter方法,该方法通常被称为解释方法。即本文的Expression接口
  • 非终止符表达式角色:其是抽象表达式的具体实现,其通过实现interpreter方法来描述文法规则。比如对于表达式a+b而言,其中的+加号即是一个非终止符。该符号表示对左右两边的操作数执行相加操作,故在解释器模式下,这个相加的语法规则即可通过一个非终止符表达式角色来表示、实现、解释。具体地在本文中,即是我们的AddOperator加法操作符。类似地还有,SubOperator减法操作符、MulOperator乘法操作符、DivOperator除法操作符类
  • 终止符表达式角色:终结符表达式同样是抽象表达式的实现类。比如对于表达式a+b而言,这里a、b变量即是一个终止符,相应的在本文中可通过终止符表达式角色Variable类来实现。一般地,我们可将变量的值存储在环境角色中。这样变量即通过实现interpreter方法来获取其所代表的数值
  • 环境角色:也被称之为上下文角色。其用于存储在解释的过程中所需的一些全局信息。具体地,即本文的Context上下文类。在本文的例子中,我们通过其来存储变量所代表的值

基于中缀表达式的加、减法

其实仅仅依靠上面的介绍,一般还是很难彻底的理解所谓的解释器模式。所以下面我们来通过具体的例子实现来帮助大家更好的理解。这里,我们先来实现一个基于中缀表达式的支持加法、减法的解释器。所谓中缀表达式,其是一种我们日常见到最多的算术或逻辑公式表示方法。即操作符是以中缀形式处于操作数的中间(例如,3 + 4)

首先,我们定义一个抽象表达式角色,可以看到其只有一个interpreter方法

1
2
3
4
5
6
7
8
9
10
11
/**
* 抽象表达式角色
*/
public interface Expression {
/**
* 解释方法
* @param context
* @return
*/
int interpreter(Context context);
}

然后,我们通过两个具体的非终止符表达式角色——AddOperator、SubOperator类,来实现加法、减法两个文法规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* 非终止符表达式角色:加法操作符
*/
public class AddOperator implements Expression {
/**
* 第一个操作数
*/
private Expression num1;

/**
* 第二个操作数
*/
private Expression num2;

public AddOperator(Expression num1, Expression num2) {
this.num1 = num1;
this.num2 = num2;
}

/**
* 语法规则解释: 加法
* @param context
* @return
*/
@Override
public int interpreter(Context context) {
int result = num1.interpreter(context) + num2.interpreter(context);
return result;
}
}
...
/**
* 非终止符表达式角色:减法操作符
*/
public class SubOperator implements Expression {
/**
* 第一个操作数
*/
private Expression num1;

/**
* 第二个操作数
*/
private Expression num2;

public SubOperator(Expression num1, Expression num2) {
this.num1 = num1;
this.num2 = num2;
}

/**
* 语法规则解释: 减法
* @param context
* @return
*/
@Override
public int interpreter(Context context) {
int result = num1.interpreter(context) - num2.interpreter(context);
return result;
}
}

在本文的例子中,终止符表达式角色只有一个,即我们的计算表达式中的变量。其通过context上下文中来获取变量所代表的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 终止符表达式角色:变量
*/
public class Variable implements Expression {

/**
* 变量名
*/
private String varName;

public Variable(String varName) {
this.varName = varName;
}

/**
* 语法规则解释: 从context上下文中获取变量的值
* @param context
* @return
*/
@Override
public int interpreter(Context context) {
return context.getVarValue(varName);
}
}

最后,为了保存各变量所表示的值。我们直接通过HashMap来实现Context类即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 上下文角色
*/
public class Context {
private Map<String, Integer> map = new HashMap<>();

/**
* 定义变量的值
* @param varName
* @param varValue
*/
public void define(String varName, Integer varValue) {
map.put(varName, varValue);
}

/**
* 获取变量的值
* @param varName
* @return
*/
public int getVarValue(String varName) {
return map.get(varName);
}
}

现在,就让我们用这个解释器来计算加、减法吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 基于中缀表达式的加、减法的 Interpreter Pattern 解释器模式Demo
*/
public class Demo1 {
public static void main(String[] args) {
// 定义上下文,即定义变量的值
Context context = new Context();
context.define("a",3);
context.define("b",5);
context.define("c",7);

Expression a = new Variable("a");
Expression b = new Variable("b");
Expression c = new Variable("c");

System.out.println("------------ Test 1 ------------");
// 计算表达式 a+b
Expression aAddb = new AddOperator(a,b);
Integer result1 = aAddb.interpreter(context);
System.out.println("a+b = " + result1);

System.out.println("------------ Test 2 ------------");
// 计算表达式 a+b-c
Expression aAddbSubc = new SubOperator( aAddb, c ); // client 客户端负责组装 AST抽象语法树
Integer result2 = aAddbSubc.interpreter(context);
System.out.println("a+b-c = " + result2);
}
}

测试结果如下所示,符合预期

figure 1.png

基于后缀表达式(逆波兰式)的四则运算(加、减、乘、除法)

前面我们介绍了中缀表达式,下面我们来介绍另外两种算术或逻辑公式表示方法

前缀表达式

又被称作波兰式(PN) ,操作符是以前缀形式处于操作数的前面(例如,+ 3 4)。前缀表达式的计算方法如下:

  1. 从右往左扫描表达式
  2. 遇到数字直接入栈
  3. 遇到运算符,先从栈中弹出两个数作为操作数,然后执行相应的运算,最后将运算的结果压入栈中
  4. 当表达式扫描完毕,则此时栈顶元素即为计算结果

后缀表达式

又被称作逆波兰式(RPN) ,操作符是以后缀形式处于操作数的后面(例如,3 4 +)。后缀表达式的计算方法如下:

  1. 从左往右扫描表达式
  2. 遇到数字直接入栈
  3. 遇到运算符,先从栈中弹出两个数作为操作数,然后执行相应的运算,最后将运算的结果压入栈中
  4. 当表达式扫描完毕,则此时栈顶元素即为计算结果

在上面的例子中,我们只实现了加、减法这两种文法规则,原因就在于乘、除法的优先级比加、减法高。虽然中缀表达式更符合人类的直觉习惯,但对于计算机来说却并不便于解析、计算。而在前缀、后缀表达式中,一方面其不存在括号,另一方面更重要的是其在计算过程中无需考虑各运算符的优先级,只需顺序计算即可。故非常适合计算机来处理求值。所以这里我们来实现一个基于后缀表达式(逆波兰式)的四则运算(加、减、乘、除法)的解释器模式

由于加、减法的文法规则在上文示例中已经实现过可以直接复用,故这里给出乘、除法的文法规则的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* 非终止符表达式角色:乘法操作符
*/
public class MulOperator implements Expression {
/**
* 第一个操作数
*/
private Expression num1;

/**
* 第二个操作数
*/
private Expression num2;

public MulOperator(Expression num1, Expression num2) {
this.num1 = num1;
this.num2 = num2;
}

/**
* 语法规则解释: 乘法
* @param context
* @return
*/
@Override
public int interpreter(Context context) {
int result = num1.interpreter(context) * num2.interpreter(context);
return result;
}
}
...
/**
* 非终止符表达式角色:除法操作符
*/
public class DivOperator implements Expression {
/**
* 第一个操作数
*/
private Expression num1;

/**
* 第二个操作数
*/
private Expression num2;

public DivOperator(Expression num1, Expression num2) {
this.num1 = num1;
this.num2 = num2;
}

/**
* 语法规则解释: 除法
* @param context
* @return
*/
@Override
public int interpreter(Context context) {
int result = num1.interpreter(context) / num2.interpreter(context);
return result;
}
}

值得一提的是,解释器模式并不负责AST抽象语法树的生成构建工作。在上面的例子中大家可以看到,AST抽象语法树是交由client客户端直接组装完成的。这里我们利用后缀表达式的求值计算规则来直接解析表达式并构建AST抽象语法树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
* AST抽象语法树工具
*/
public class ASTUtil {
/**
* 构建AST抽象语法树
* @param str
* @return
*/
public static Expression build(String str) {
Stack<Expression> stack = new Stack<>();
// 使用空格作为分隔符进行切分
String[] strArray = str.split(" ");

// 按从左到右的顺序依次扫描
for( String element : strArray ) {
switch (element) {
case "+": // 遇到操作符
case "-":
case "*":
case "/":
// 1. 先从栈中弹出两个操作数
Expression num1 = stack.pop(); // 获取第一个操作数
Expression num2 = stack.pop(); // 获取第二个操作数
// 2. 构造结果表达式
Expression result = null;
switch (element) {
case "+":
result = new AddOperator(num1, num2);
break;
case "-":
result = new SubOperator(num1, num2);
break;
case "*":
result = new MulOperator(num1, num2);
break;
case "/":
result = new DivOperator(num1, num2);
break;
}
// 3. 将结果压入栈中
stack.push(result);
break;
default: // 遇到操作数
// 构造变量表达式, 直接入栈
Expression var = new Variable(element);
stack.push( var );
}
}
return stack.pop();
}
}

剩余部分的实现,可以直接复用我们上面那个例子的代码。现在让我们来看看效果如何

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 基于后缀表达式(逆波兰式)的四则运算(加、减、乘、除法)的 Interpreter Pattern 解释器模式Demo
*/
public class Demo2 {
public static void main(String[] args) {
// 定义上下文,即定义变量的值
Context context = new Context();
context.define("a",8);
context.define("b",1);
context.define("c",2);
context.define("d",4);
context.define("e",5);

// 计算中缀表达式 b - a + e * d / c 值,即计算后缀表达式(逆波兰式) a b c d e * / + - 结果
String str = "a b c d e * / + -";

// 构建AST抽象语法树
Expression expression = ASTUtil.build(str);
Integer result = expression.interpreter(context);
System.out.println("期望值: 3 实际值: " + result);
}
}

测试结果如下,符合预期

figure 2.png

参考文献

  1. Head First 设计模式 弗里曼著
请我喝杯咖啡捏~

欢迎关注我的微信公众号:青灯抽丝