后缀表达式

假设我们有一个便携式计算器并想要计算一趟外出购物的花费。为此，我们将一列数据相加并将结果乘以1.06；它是所购物品的价格以及附加的地方税。如果购物各项花销为4.99，5.99和6.99，那么输入这些数据的自然方式将是
4.99+5.99+6.991.06=
随着计算器的不同这个结果或者是所要的答案19.05，或者是科学答案18.39。最简单的四功能计算器给出第一个答案，但是很多先进的计算器知道乘法的优先级是高于加法的。
另一方面，有些项是需要上税的，而有些则不需要，因此，如果只有第一项和最后一项是需要上税的，那么
4.99 1.06 + 5.99 + 6.99 1.06 =
将在科学计算器上得到正确的答案（18.69）而在简单的计算器上则得到（19.37）。科学计算器一般包含括号，因此我们总可以通过加括号得到正确的答案，但是使用简单的计算器我们需要记住中间结果。
该例的典型计算顺序可以是将4.99和1.06相乘并存为A1，然后将5.99和A1相加，再将结果存入A1。我们再将6.99和1.06相乘的结果存入A2，最后A1和A2相加并将最后的结果存入A1。我们可以将这种操作顺序书写如下：
4.99 1.06 5.99 + 6.99 1.06 +
这种记法叫做后缀（postfix）或逆波兰（reverse Polish）记法，其求值过程恰好就是我们上面所描述的过程。计算这个问题最容易的方法就是使用一个栈，当见到一个数时就把它推入栈中；在遇到一个运算符时该运算符就作用于从该栈弹出的两个数（符号）上，将所得结果推入栈中。例如，后缀表达式
6 5 2 3 + 8 + 3 +
计算如下：前四个字符放入栈中，此时栈变成

下面读到一个“+”号所以3和2从栈中弹出，并且它们的和5被压入栈中。

接着，8进栈。

现在见到一个号，因此8和5弹出，并且5 8 = 40进栈。

接着又见到一个“+”号，因此40和5被弹出，并且40 + 5 = 45进栈。

现在将3压入栈中。

然后“+”使得3和45从栈中弹出，并将45 + 3 = 48压入栈中。

最后，遇到一个“”号，从栈中弹出48和6，并将结果6 * 48 = 288 压进栈中。