这次没有小明，我们来做加减乘除
现在我们要计算6*(5+(25+15)/8+22)这个表达式的值，大家应该觉得很简单，写一个方法，一步一步计算就是了，这样是可以计算出来这个表达式的结果，那如果换了一个另外一个表达式，我们又要写一个方法去单独计算这另外一个表达式，所以我们应该想一种办法，用一个算法，可以计算出所有加减乘除带括号的表达式
注意，我们说的是算法，还没有涉及到模式，那么什么算法可以解决这个问题呢？让我们现在请出它，它叫做逆波兰算法，什么是逆波兰算法呢？我们先模拟分步计算上面的表达式
- 最先计算25+15，得到40
- 再用40/8，得到5
- 计算5+5，得到10
- 计算10+22，得到32
- 最后计算6*32，得到192
逆波兰算法的作用就是将我们的表达式装换一下，装换成什么样呢？比如上面的表达式，通过逆波兰算法装换后，我们的表达式是这样的：
6 5 25 15 + 8 / + 22 + *
那么它和我们的计算步骤有什么联系呢，逆波兰表达式又叫做后缀表达式，上面的逆波兰表达式可以很明显体现我们的运算步骤，从左向右遍历，遇到运算符，就将此运算符用于此运算符前面两个数，比如上面的逆波兰表达式，第一个遇到的运算符号是加号，将它作用于25和15，计算得出40，一次类推，我们可以发现，和我们上面列出的1-5步骤是一毛一样的！接下来我们用代码实现，将普通表达式转化为逆波兰表达式
首先，写一个方法，将我们的表达式转换为中序表达式，就是一个存储运算符和数字的List
public static List<String> stringToList(String str) {
List<String> numberAndOperators = new ArrayList<>();
char[] chars = str.toCharArray();
int i = 0;
char c;
String number;
while (i < chars.length) {
c = chars[i];
if (c < '0' || c > '9') {
numberAndOperators.add(String.valueOf(c));
i++;
} else {
number = "";
while (i < chars.length && c >= '0' && c <= '9') {
number += c;
i++;
c = chars[i];
}
numberAndOperators.add(number);
}
}
return numberAndOperators;
}
此方法很简单，遍历字符串中的字符，如果是运算符直接放进List，如果是数字，继续先前遍历，直到不是数字，将这些数字字符拼接，例如上面的25，先遍历到2，再遍历到5，组成字符串25，放进List。进过这个算法，我们的字符串表达式被装换为
6 * ( 5 + ( 25 + 15 ) / 8 + 22 )
接下来遍历上面的List，生成逆波兰表达式，同样用List保存这个字符序列
public static List<String> listToNBLList(List<String> list) {
List<String> numberAndOperatorsNBL = new ArrayList<>();
Stack<String> stackNPL = new Stack<>();
for (String s : list) {
if (s.matches("\\d+")) numberAndOperatorsNBL.add(s);
else if (s.equals("(")) stackNPL.push(s);
else if (s.equals(")")) {
while (!stackNPL.peek().equals("(")) numberAndOperatorsNBL.add(stackNPL.pop());
stackNPL.pop();
} else {
while (stackNPL.size() != 0 && getValue(stackNPL.peek()) >= getValue(s)) numberAndOperatorsNBL.add(stackNPL.pop());
stackNPL.push(s);
}
}
while (stackNPL.size() != 0) numberAndOperatorsNBL.add(stackNPL.pop());
return numberAndOperatorsNBL;
}
/**
* 获取运算符优先级
* +,-为1 *,/为2 ()为0
*/
public static int getValue(String s) {
if (s.equals("+")) {
return 1;
} else if (s.equals("-")) {
return 1;
} else if (s.equals("*")) {
return 2;
} else if (s.equals("/")) {
return 2;
}
return 0;
}
解释一下这个方法：
- 读到操作数，直接放入List
- 读到(，直接压入Stack栈顶
- 读到)，则弹出离Stack栈顶最近的到左括号(的所有操作符放入Lis,之后弹出该(
- 读到非括号操作符，则按照优先级操作。如果操作符比Stack栈顶操作符优先级高，则直接压入Stack；如果操作符不比Stack栈顶操作符优先级高，则弹出Stack栈顶并放入List，直到当前操作符高于Stack栈顶或者Stack为空，然后将当前操作符压入Stack
- 当中缀表达式读取完毕，将Stack内剩余的操作符逐个弹出并放入List
- List中即为逆波兰表达式
通过此方法，可以将上面的6 * ( 5 + ( 25 + 15 ) / 8 + 22 )转化为我们的逆波兰表达式：6 5 25 15 + 8 / + 22 + *，那么怎么计算呢，大家可能会发现，到现在我们都还没提到解释器模式，不过现在，我们可以用到他了，我们要用解释器模式来计算我们转化为逆波兰表达式的值。现在先来看看解释器模式的定义
定义
定义一个语言的文法，并且建立一个解释器来解释该语言中的句子，这里的“语言”是指使用规定格式和语法的代码
角色
- 抽象表达式
- 终结符表达式
- 非终结符表达式
- 环境类
什么是表达式
表达式就是就是代表我们上面的表达式，不过，具体的表达式会根据表达式的规则和语法来定义成最小单元的表达式，例如对于上面的整个表达式，里面的操作数是一个表达式，25+15是一个表达式，( 25 + 15 ) / 8是一个复合表达式，复合表达式是由简单表达式共同组合成的。根据表达式的不同，可以分为终结表达式和非终结符表达式。终结表达式很简单，比如上面的例子，每一个操作数就是终结表达式。非终结符表达式就是对非终结表达式和终结表达式的解释，比如25+15、( 25 + 15 ) / 8，非终结表达式中可以包含终结表达式和非终结表达式，终结表达式和非终结表达式都继承至抽象表达式。环境类我们稍后解释，现在我们就用解释器来计算我们上面的逆波兰表达式
抽象表达式：
public abstract class AbstractExpression {
public abstract int interpret();
}
数字表达式：
// 终结表达式
public class NumberExpression extends AbstractExpression {
private int number;
public NumberExpression(int number) {
this.number = number;
}
@Override
public int interpret() {
return number;
}
}
加法表达式：
public class PlusExpression extends AbstractExpression {
private AbstractExpression left;
private AbstractExpression right;
public PlusExpression(AbstractExpression left, AbstractExpression right) {
this.left = left;
this.right = right;
}
@Override
public int interpret() {
return left.interpret() + right.interpret();
}
}
减法表达式：
public class MinusExpression extends AbstractExpression {
private AbstractExpression left;
private AbstractExpression right;
public MinusExpression(AbstractExpression left, AbstractExpression right) {
this.left = left;
this.right = right;
}
@Override
public int interpret() {
return left.interpret() - right.interpret();
}
}
乘法表达式：
public class MultiplyExpression extends AbstractExpression {
private AbstractExpression left;
private AbstractExpression right;
public MultiplyExpression(AbstractExpression left, AbstractExpression right) {
this.left = left;
this.right = right;
}
@Override
public int interpret() {
return left.interpret() * right.interpret();
}
}
除法表达式：
public class DivideExpression extends AbstractExpression {
private AbstractExpression left;
private AbstractExpression right;
public DivideExpression(AbstractExpression left, AbstractExpression right) {
this.left = left;
this.right = right;
}
@Override
public int interpret() {
return left.interpret() / right.interpret();
}
}
除了数字表达式是终结表达式以外，加、乘、除都是非终结表达式，他们的实现方法用了递归的方式计算。接下来是我们的环境类，他一般就是用来计算我们的表达式，里面有一些方法和变量，方便客户端调用，类似一个工具类
public class Context {
public int NBL(String expression) {
List<String> numberAndOperators = stringToList(expression);
List<String> NBLList = listToNBLList(numberAndOperators);
Stack<AbstractExpression> stackCalculateNPL = new Stack<>();
for (String s : NBLList) {
System.out.print(s + " ");
if (s.matches("\\d+")) {
stackCalculateNPL.push(new NumberExpression(Integer.valueOf(s)));
} else {
AbstractExpression right = stackCalculateNPL.pop();
AbstractExpression left = stackCalculateNPL.pop();
AbstractExpression nonterminalExpression = null;
if (s.equals("+")) nonterminalExpression = new PlusExpression(right,left);
else if (s.equals("-")) nonterminalExpression = new MinusExpression(right,left);
else if (s.equals("*")) nonterminalExpression = new MultiplyExpression(right,left);
else if (s.equals("/")) nonterminalExpression = new DivideExpression(right,left);
stackCalculateNPL.push(nonterminalExpression);
}
}
return stackCalculateNPL.pop().interpret();
}
/**
* 获取运算符优先级
* +,-为1 *,/为2 ()为0
*/
private int getValue(String s) {
if (s.equals("+")) {
return 1;
} else if (s.equals("-")) {
return 1;
} else if (s.equals("*")) {
return 2;
} else if (s.equals("/")) {
return 2;
}
return 0;
}
private List<String> stringToList(String str) {
List<String> numberAndOperators = new ArrayList<>();
char[] chars = str.toCharArray();
int i = 0;
char c;
String number;
while (i < chars.length) {
c = chars[i];
if (c < '0' || c > '9') {
numberAndOperators.add(String.valueOf(c));
i++;
} else {
number = "";
while (i < chars.length && c >= '0' && c <= '9') {
number += c;
i++;
c = chars[i];
}
numberAndOperators.add(number);
}
}
return numberAndOperators;
}
private List<String> listToNBLList(List<String> list) {
List<String> numberAndOperatorsNBL = new ArrayList<>();
Stack<String> stackNPL = new Stack<>();
for (String s : list) {
if (s.matches("\\d+")) numberAndOperatorsNBL.add(s);
else if (s.equals("(")) stackNPL.push(s);
else if (s.equals(")")) {
while (!stackNPL.peek().equals("(")) numberAndOperatorsNBL.add(stackNPL.pop());
stackNPL.pop();
} else {
while (stackNPL.size() != 0 && getValue(stackNPL.peek()) >= getValue(s))
numberAndOperatorsNBL.add(stackNPL.pop());
stackNPL.push(s);
}
}
while (stackNPL.size() != 0) numberAndOperatorsNBL.add(stackNPL.pop());
return numberAndOperatorsNBL;
}
}
这个类里面除了NBL方法外，其他三个方法都是我们上面讲NBL算法时讲解了的，可以看到NBL方法，里面就用了各种实现AbstractExpression的表达式解释出了我们的算术表达式的值。有了这个方法，不管我们什么形式的四则运算都可以计算出来，而且只用了一个方法，最后我们来使用一下，计算一个新的表达式6*(5+(3+2)/5+22)，如果正确，应该得到的结果为168
public class Client {
public static void main(String[] args) {
Context context = new Context();
int result = context.NBL("6*(5+(3+2)/5+22)");
System.out.println();
System.out.println(result);
}
}
结果：
6 5 3 2 + 5 / + 22 + *
168
解释器模式的用处
在平时的编程中，解释器模式用得比较少，但是它的作用非常明显，比如在一些对大型数据做统计的程序中，可能我们数据是固定的，而不同的计算都是通过统一的语法，但是计算形式不同，有的是加两个数据，有的是两个数据相乘等等，这时候我们可以实现对这个同一语法的解释器，来计算经过统一语法构成的不同表达式。一般的，在这些情况下我们需要使用解释器
- 可以将一个需要解释执行的语言中的句子表示为一个抽象语法树。
- 一些重复出现的问题可以用一种简单的语言来进行表达。
- 一个语言的文法较为简单。
- 执行效率不是关键问题
解释器模式的优缺点
优点
- 易于改变和扩展文法。由于在解释器模式中使用类来表示语言的文法规则，因此可以通过继承等机制来改变或扩展文法
- 每一条文法规则都可以表示为一个类，因此可以方便地实现一个简单的语言
- 实现文法较为容易。在抽象语法树中每一个表达式节点类的实现方式都是相似的，这些类的代码编写都不会特别复杂，还可以通过一些工具自动生成节点类代码
- 增加新的解释表达式较为方便。如果用户需要增加新的解释表达式只需要对应增加一个新的终结符表达式或非终结符表达式类，原有表达式类代码无须修改，符合“开闭原则”
缺点
- 对于复杂文法难以维护。在解释器模式中，每一条规则至少需要定义一个类，因此如果一个语言包含太多文法规则，类的个数将会急剧增加，导致系统难以管理和维护，此时可以考虑使用语法分析程序等方式来取代解释器模式。
- 执行效率较低。由于在解释器模式中使用了大量的循环和递归调用，因此在解释较为复杂的句子时其速度很慢，而且代码的调试过程也比较麻烦。
