源码地址
关于解释器模式
解释器模式是行为型模式的一种，关于解释器模式的定义从网上摘抄了一段
给定一种语言，并定义代表其文法的相应解释器，并用该解释器来解析使用该语言的编写的内容
JAVA Design pattern
其中的关键字有，语言文法、解释器。
- 语言文法，如：下面要提到的
四则运算表达式、我们日常使用的各种编程语言、类英语语法的SQL语言、一些框架里面的特定语言（如Spring的SpEL）等等，都是具有固定文法的语言，这意味着这些语言均可以用解释器模式来解析。当然，除此之外你也可以根据你的需求自己创造一种语言。 - 解释器，用于让计算机『认识』这些语言的工具，需要由我们程序员编码实现。越复杂的语言文法，其相应的解释器实现难度越大，比如人类的『自然语言』。
UML图
其实并不算复杂（因为解释器模式最复杂的部分在于将语言解析为对象的过程，稍后的实践中可以看到），跟组合模式的UML图有点相像（同为树型数据结构），下面是两个比较重要的类：
NumberExpression: 数值表达式（也称终结点表达式，意为表达式解析的终结点，可以简单理解为树型结构的叶子节点），执行interpret()一般会得到一个常量供复合表达式计算
MultiplyExpression: 复合表达式（也称非终结点表达式，可以简单理解为树型结构的枝节点），一般包括一个或多个Expression类型的子节点，子节点数即代表该复合表达式的操作数数量，执行interpret()一般会得到其子节点互相作用后的结果
编码实践
为了节省篇幅，这里只贴出部分重要代码，完整代码可从开头的源码地址下载。
简单四则运算
单元测试类
cn.tac.test.interpreter.arithmetic.simple.SimpleCalculatorTest
实现效果
支持最简单的四则运算，不支持括弧运算，不支持优先级运算符。因为语言文法较简单，所以解析器较易实现，适合作为Hello World。
相关类
Node: 即Expression
public interface Node {
int interpret();
}
ValueNode: 即NumberExpression，代表操作数
public abstract class ValueNode implements Node{
protected int value;
public ValueNode(int value) {
this.value = value;
}
}
SymbolNode: 即MultiplyExpression，代表运算符（如+-*/），因为均为二元操作符，所以只有两个子节点
public abstract class SymbolNode implements Node {
protected Node left;
protected Node right;
public SymbolNode(Node left, Node right) {
this.left = left;
this.right = right;
}
}
SimpleValueNode: 简单地返回数值本身
public class SimpleValueNode extends ValueNode {
public SimpleValueNode(int value) {
super(value);
}
public int interpret() {
return value;
}
}
运算符节点: 代表+-*/
public class PlusNode extends SymbolNode {
public PlusNode(Node left, Node right) {
super(left, right);
}
public int interpret() {
return left.interpret() + right.interpret();
}
}
public class MinusNode extend SymbolNode{……}
public class MulNode extend SymbolNode{……}
public class DivNode extend SymbolNode{……}
Parser:
public class Parser {
public static final String SPLITTER = " "; //为了方便解析，用空格将表达式分隔开
public Node parse(String statement) {
String[] arr = statement.split(SPLITTER);
LinkedList<Node> nodeStack = new LinkedList<>();
boolean symbolFlag = false;
String symbol = "";
for (String item : arr) {
if (isSymbolNode(item)) {
symbol = item;
symbolFlag = true;
} else if (isValueNode(item)) {
nodeStack.push(new SimpleValueNode(Integer.parseInt(item)));
if (symbolFlag) {
Node right = nodeStack.pop(); //后入先出
Node left = nodeStack.pop();
nodeStack.push(mapSymbolNode(left, right, symbol));
symbolFlag = false;
}
} else {
throw new RuntimeException("表达式格式有误");
}
}
return nodeStack.pop();
}
……
}
Calculator:
public class SimpleCalculator {
public int calculate(String statement){
Parser parser = new Parser();
return parser.parse(statement).interpret();
}
}
Parser解析过程
- 将表达式分割为数组，并遍历
- 从数组中获取一个元素，若为数值，则直接转换为节点并入栈；若为运算符，则只进行标记，等待下一个节点入栈后，将其与上一个节点一同取出，并合并为一个复合表达式节点入栈；
- 反复执行步骤2，直到数组末尾
- 将栈中的元素pop并返回（如果表达式无误，最终栈中应该只有一个元素，否则应该在解析过程中抛出异常）
完整四则运算
单元测试类
cn.tac.test.interpreter.arithmetic.full.FullCalculatorTest
cn.tac.test.interpreter.arithmetic.full.ParserTest
实现效果
支持完整的四则运算，包括括弧运算，优先级运算。由于相较于上一个实践文法上复杂了许多，不能用同样的方式直接解析，而是应该先转换为后缀表达式再进行解析。
后缀表达式
// todo::
相关类
节点
值节点和运算符节点类仍采用和上个实践相同的类。
Parser
public class Parser {
public static final String SPLITTER = " ";
public Node parse(String statement) {
LinkedList<Node> stack = new LinkedList<>();
String[] segments = convert2Postfix(statement).split(SPLITTER);
for (String segment : segments) {
if (isValueNode(segment)) {
stack.push(new SimpleValueNode(Integer.parseInt(segment)));
} else if (isOperator(segment)) {
Node rightNode = stack.pop();
Node leftNode = stack.pop();
stack.push(doOperate(leftNode, rightNode, segment));
} else {
throw new RuntimeException();
}
}
return stack.pop();
}
public String convert2Postfix(String statement) {
LinkedList<String> symbolStack = new LinkedList<>(); //临时存放符号节点的栈
LinkedList<String> stack = new LinkedList<>();
String[] nodes = statement.split(SPLITTER);
for (String node : nodes) {
if (isSymbolNode(node)) {
if (symbolStack.size() == 0 || "(".equals(node)) {
symbolStack.push(node);
} else if (isOperator(node)) {
String topSymbol = symbolStack.peek();
if (priority(node) <= priority(topSymbol)) {
while (symbolStack.peek() != null) {
if (priority(symbolStack.peek()) < priority(node)) {
break;
} else {
stack.push(symbolStack.pop());
}
}
}
symbolStack.push(node);
} else if (")".equals(node)) {
while (!"(".equals(symbolStack.peek())) {
stack.push(symbolStack.pop());
}
symbolStack.pop();
} else {
throw new RuntimeException("不支持的运算符");
}
} else if (isValueNode(node)) {
stack.push(node);
} else {
throw new RuntimeException("不支持的运算符");
}
}
//到数组尾部后，还有一些符号在栈内
while (symbolStack.peek() != null) {
stack.push(symbolStack.pop());
}
StringBuilder sb = new StringBuilder();
String tmp;
while (isNull(tmp = stack.pollLast())) {
sb.append(tmp);
sb.append(SPLITTER);
}
return sb.toString().trim();
}
……
}
Calculator
public class FullCalculator {
public int calculate(String statement){
Parser parser = new Parser();
return parser.parse(statement).interpret();
}
}
Parser解析过程
主要分为两大步骤
一、将中缀表达式转换为后缀表达式
- 将表达式分割为数组，并遍历
- 从数组中获取一个元素
- 若为数值，则直接入存放结果的栈，以下简称
结果栈 - 若为符号，则判断
- 若符号栈目前为空，或该符号为左括弧”(“，则直接入临时存放符号的栈，以下简称
符号栈 - 若当前符号为操作符（+-*/，不包括括弧），则从符号栈peek（不是pop）一个符号，比如两者优先级，若 当前符号优先级<=从栈顶取出的符号优先级，则从符号栈pop一个符号并push至结果栈，直至 符号栈为空 or 栈顶符号优先级<=当前符号优先级，然后将当前符号入符号栈。这里需要注意的是，左右括弧也有优先级，且优先级应小于操作符，否则在这里需要单独处理pop时遇到左括弧的问题
- 若为右括弧”)”，则将符号栈pop符号并push至结果栈，直到遇到左括弧（遇到后pop并丢弃）
- 若符号栈目前为空，或该符号为左括弧”(“，则直接入临时存放符号的栈，以下简称
- 若为数值，则直接入存放结果的栈，以下简称
- 反复执行步骤2，直到数组末尾
- 到数组尾部后，多数情况都会有一些符号还留在符号栈内，应将其取出并push至结果栈
- 将结果栈构建为字符串，并返回
二、将后缀解析为java对象
- 将表达式分割为数组，并遍历
- 从数组中获取一个元素，若为数值，则直接转换成数值节点并入栈；若为操作符（转换成后缀表达式后已经没有括弧了），则从栈顶取出两个节点，并合并为一个复合表达式节点并入栈
- 反复执行步骤2，直到数组末尾
- 将栈中的元素pop并返回（如果表达式无误，最终栈中应该只有一个元素，否则应该在解析过程中抛出异常）
当然，你也可以将这两个步骤合二为一，在转换的同时将其转换为java对象，但非实际应用中个人还是建议将两个步骤分离，原因有二：
- 降低编码的复杂度
- 方便进行单元测试（尤其是将后缀表达式转换为中缀表达式的步骤，比较容易出错）