解析算术表达式

到现在为止，本章已经介绍了三种不同的数据存储结构。现在，转换一下，把注意力集中到一个实际应用问题上来。这个应用是解析（也可以说是分析）算术表达式，例如2+3，或者2*(3+4)，或者((2+4)*7)+3*(9-5)等。它用到的存储结构是栈。brackets.java程序(清单4.3)已经演示了怎样应用栈来检查分隔符是否正确匹配的问题。这和应用栈解析算术表达式的方法类似，尽管后者更为复杂。

从某种意义上来说本节内容应作为选学内容。它不是本书后面章节的必修内容，并且除非是专门编写编译器或者是要设计便携式计算器的程序员，人们不会每天编写代码来解析算术表达式。另外，此应用的详细代码也比前面的程序复杂得多。但是这个重要的应用对于学习栈很有意义，而且这个应用本身引起的问题也非常有意思。

事实上，至少对计算机的算法来说如果要直接求算术表示式的值，还是相当困难的。因此分两步实现算法会更容易：

1. 将算术表达式转换成另一种形式：后缀表达式。
2. 计算后缀表示式的值。

第一个步骤比较难，但是第二步很简单。但是不管怎么说，这种分两步的算法比直接解析算术表达式的方法容易。当然，对人类来说，还是解析普通的算术表达式容易。稍后将会再讨论人类和计算机的方法的差别。

在研究步骤1和步骤2的具体实现之前，先来介绍后缀表达式。

后缀表达式

日常算术表示式是将操作符(operator)(+，-，*，/)放在两个操作数(operands)(数字，或代表数字的字母)之间的。因为操作符写在操作数的中间，所以把这种写法称为中缀表达法。于是，日常我们写的算术表示式就形如2+2，4/7，或者用字母代替数字，如A+B和A/B等。

在后缀表达式中[也称作波兰逆序表达式(Reverse Polish Notation)]，或者RPN，它是由一位波兰的数学家发明的]，操作符跟在两个操作数的后面。这样，A+B就成为AB+，A/B成为AB/。更复杂的中缀表达式同样可以转换成后缀表达式，如表4.2所示。稍后会解释后缀表达式是如何产生的。

表4.2 中缀表达式和后缀表达式

中缀表达式	后缀表达式
A+B-C	AB+C-
A*B/C	AB*C/
A+B*C	ABC*+
A*B+C	AB*C+
A*(B+C)	ABC+*
A*B+C*D	AB*CD*+
(A+B)*(C-D)	AB+CD-*
((A+B)*C)-D	AB+C*D-
A+B*(C-D/(E+F))	ABCDEF+/-*+

有些计算机语言也用一个操作符表示乘方(通常，用‘^’符号)，但在这里暂不讨论这种表示。

除了中缀和后缀表达法，还有一种前缀表达法，操作符写在两个操作数的前面：用+AB代替AB+。这种表达法与后缀表达法功能类似，但是很少使用。

把中缀表达式转换成后缀表达式

下面的内容解释怎样把中缀表达的算术表达式转换成后缀表达式。这个算法时相当难的，因此刚开始要是没有完全明白也不必担心。如果很难理解这一部分，可以先跳到“求后缀表达式的值”这一节。为了理解怎样创建后缀表达式，先看怎么计算后缀表达式的值会有所帮助；