中缀表达式（用栈进行表达式求值）

我们今天继续看一下，如何使用栈完成标准的四则混合运算表达式求值。

中缀表达式（用栈进行表达式求值）

不同于后缀表达式，遇到一个运算符就可以直接从栈里取两个数进行运算。在标准的四则混合运算表达式中（或者我们称之为中缀表达式），遇到一个操作符是不能直接计算的，因为计算的顺序要取决于后面的运算符。多举几个例子，大家就能明白了。由于加和减是相同的运算优先级，乘和除是相同的运算优先级，我们就只用加和乘来举例就可以了。

我们像计算后缀表达式一样，引入一个操作数栈。由于后缀表达式不用缓存 +-*/ 这些操作符，所以一个操作数栈就够了。但是，中缀表达式的计算是要用到操作符的缓存的，所以，我们还要再引入一个操作符栈，专门存储各个操作符。

第一个例子：a + b * c，我们从前向后扫描，遇到a，压到操作数栈里，遇到 + ，压到操作符栈里，下一个是 b，此时，我们是不能像后缀表达式求值那样，直接计算 a + b，然后压栈的。因为我们不确定，b 是否会先参与后面的运算，所以我们只能把 b 先压栈，继续向后扫描。看到 * 以后，再把 * 压到操作符栈里；看到 c 以后，也要把 c 先压栈，理由与 b 压栈相同。接下来，再往下扫描，就发现已经到了末尾了。那我们就可以放心地从操作符栈里取出顶上的操作符，在这个例子中，就是 *，然后再从操作数栈里取出两个操作数，就是 b 和 c，然后把b和c的积，不妨记为d，放到操作数栈里。接下来，再去看操作符栈里，还有一个 +，那就把 + 取出来，然后去操作数栈里取出 a 和 d，计算它们的和，这就是最终的结果了。

第二个例子：a + b + c，我们从前向后扫描，遇到a，压到操作数栈里，遇到 + ，压到操作符栈里，下一个是 b，压到操作数栈里。再下一个，又是 + ，由于加法的结合律，我们知道，先把a + b 的结果计算出来，或者后计算，都不会影响最终的结果。所以我们就把能做的化简先做掉。就是说，在扫描到第二个操作符是 + 以后，我们就把第一个操作符取出来，再把两个操作数取出来，求和并且把和送到操作数栈里。接下来的过程与第一个例子是相同的，不再赘述了。

通过这两个例子，我们看到，一个操作符究竟什么时候进行运算，并不取决于它前面的那个操作符是什么，而是取决于它后面的那个操作符是什么。更具体一点讲：如果后面的操作符的运算优化级比前面的操作符高，那么前面的操作符就必须延迟计算；如果后面的操作符优化级比前面的低或者相等，那么前面的操作符就可以进行计算了。上面这句话，非常重要，是我们这节课的核心。请多读几遍，结合上面的两个例子，务必想明白它。

好了，理解了这个，就可以上代码了。

先看 Stack的完整定义：

class Stack<T> { private ArrayList<T> list; public Stack(int size) { this.list = new ArrayList<T>(size); } public T getTop() { if (isEmpty()) return null; return list.get(list.size() - 1); } public void push(T t) { this.list.add(t); } public T pop() { if (isEmpty()) return null; return list.remove(list.size() - 1); } public boolean isEmpty() { return list.isEmpty(); } }

然后我们创建两个栈，一个是操作数栈，一个是操作符栈：

其中，TokenStream 是这节课里的课后作业：适配器模式

按照上面分析的算法，如果遇到数字，就压栈到numbers里，如果遇到操作符，就要看前面一个的操作符的优先级是否比当前操作符高，如果前一个操作符高，那么执行前一个操作符的操作，如果是后面的高，那就只要把后面的操作符压栈即可：

public class StackExpression { public static void main(String args[]) throws IOException { TokenStream ts = new ExpressionTokenStream(System.in); Stack<Integer> numbers = new Stack<>(100); Stack<Token> operators = new Stack<>(100); while (ts.getToken().tokenType != Token.TokenType.NONE) { if (ts.getToken().tokenType == Token.TokenType.INT) { numbers.push((Integer)ts.getToken().value); ts.consumeToken(); } else { if (operators.getTop() == null || preOrder( operators.getTop().tokenType, ts.getToken().tokenType) < 0) { operators.push(ts.getToken()); ts.consumeToken(); } else { binaryCalc(numbers, operators); operators.push(ts.getToken()); ts.consumeToken(); } } } while (!operators.isEmpty()) { binaryCalc(numbers, operators); } System.out.println("result is " + numbers.getTop()); } private static void binaryCalc(Stack<Integer> numbers, Stack<Token> operators) { int a = numbers.pop(); int b = numbers.pop(); Token oprt = operators.pop(); int d = 0; if (oprt.tokenType == Token.TokenType.PLUS) d = b + a; else if (oprt.tokenType == Token.TokenType.MULT) d = a * b; else if (oprt.tokenType == Token.TokenType.MINUS) d = b - a; else if (oprt.tokenType == Token.TokenType.DIV) d = b / a; numbers.push(d); } private static int preOrder(Token.TokenType left, Token.TokenType right) { if (left == Token.TokenType.PLUS || left == Token.TokenType.MINUS) { if (right == Token.TokenType.MULT || right == Token.TokenType.DIV) return -1; else return 1; } else return 1; } }

好了。我们的这个程序已经可以处理类似 a + b - c * d + e / f 这样的算式了。

为了让大家看得更清楚，我用图把 a + b * c / d 的过程画一遍。

首先，遇到 a ，把 a 送到操作数栈，遇到 + ，送到操作符栈：

遇到 b，压栈

遇到乘，由于乘的优先级高于加，所以，现在就什么也不做，只把乘号进栈：

同样，遇到 c 把 c 进栈（此图略，请自己补上），再遇到 / ，由于除的优先级与 * 的优先级相同，所以，乘就可以先做了。这个动作是把乘号出栈，把c 和 b出栈，求 c * b的值，并且把这个值入栈。即：

然后把 / 入栈，把 d 入栈：

现在到了运算的结尾了。我们只需要把现在的栈里的内容从顶向下计算起来即可，先算除法：

再算加法：

但是，括号怎么办？

可以这样想，在遇到形如 a * (b + c) 这样的形式的时候，左边的乘法是一定不能做的，我们只需要将左括号进栈即可。所以，我们可以把TokenStream里取得的左括号看做是一个优先级无穷大的运算符，它使得左方的运算符都不能提前进行计算。

遇到右括号时，b + c 这个加法是可以进行运算的了，所以可以把右括号看作是一个优先级无穷小的运算符，它会使得操作符栈上的所有运算符都出栈并执行计算，直到遇到左括号。遇到左括号以后，只需要把左括号从栈里弹出来，然后让它和右括号一起狗带即可（这就是括号匹配啊，同学们~）。由于括号内的计算都已经完成了，结果是一个整数，我们已经在计算的过程中把这个整数放到操作数栈里了。所以整个括号内的求值就完成了。

好了。今天的课程很短，但是比较难理解，尤其是，今天的程序都依赖于本周前边的课程。请务必先完成本周前边的课程再来看这节课。

演示一下，我的完整版的效果：