四则运算表达式
一种不需要括号的后缀表达法，我们把它称为逆波兰（Reverse Polish Notation ， RPN）表示。它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式，解决了四则运算中括号改变运算符优先级的问题。
我们先来看看，对于"9+(3-1)×3+10÷2"，如果要用后缀表示法应该是什么样子：“9 3 1 - 3 * + 10 2 / +” ，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。
一.后缀表达式计算结果
为了解释后缀表达式的好处，我们先来看看，计算机如何应用后缀表达式计算出最终的结果20的。
后缀表达式：9 3 1 - 3 * + 10 2 / +
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
1.初始化一个空栈。此栈用来对要运算的数字进行使用。如图1左图所示。
2.后缀表达式中前三个都是数字，所以9、3、1进栈，如图1右图所示。
图1
3.接下来是“-” ， 所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈，如图2左图所示。
4.接着是数字3进栈，如图2右图所示。
图2
5.后面是“*” ， 也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈，如图3左图所示。
6.下面是“+” ， 所以栈中6和9出栈，9与6相加，得到15，将15出栈，如图3右图所示。
图3
7.接着是10与2两数字进栈，如图4左图所示。
8.接下来是符号“/” ， 因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈，如图4右图所示。
图4
9.最后一个是符号“+” ， 所以将15与5出栈并相加，得到20，将20进栈，如图5左图所示。
10.结果是20出栈，栈变为空，如图5右图所示。
图5
果然，后缀表达式可以很顺利解决计算的问题。
二.中缀表达式转后缀表达式
我们把平时所用的标准四则运算表达式，即“9+(3-1)×3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间。
中缀表达式 “9+(3-1)×3+10÷2” 转化为后缀表达式 “9 3 1 - 3 * + 10 2 / +” 。
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
1.初始化一空栈，用来对符号进出栈使用。如图6左图所示。
2.第一个字符是数字9，输出9，后面是符号“+”，进栈。如图6的右图所示。
图6
3.第三个字符时“（” ， 依然是符号，因其只是左括号，还没配对，故进栈。如图7左图所示。
4.第四个字符是数字3，输出，总表达式为9 3，接着是“—”，进栈。如图7右图所示。
图7
5.接下来是数字1，输出，总表达式为9 3 1，后面是符号“)” ， 此时，我们需要去匹配此前的“(” ， 所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“—” ， 因此输出“—”。总的输出表达式为9 3 1 — 。如图8左图所示。
6.紧接着是符号“×” ，因为此时的栈顶符号为“+”号，优先级低于“×” ，因此不输出，“*”进栈。接着是数字3，输出，总的表达式为 9 3 1 — 3 。 如图8右图所示。
图8
7.之后是符号“+” ，此时当前栈顶元素“*”比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总输出表达式为9 3 1 — 3 * + 。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+” ，而图9左图中的栈底（也是栈顶）的“+”是指“9+(3-1)×3+”中的最后一个“+”。
8.紧接着数字10，输出，总表达式变为9 3 1 — 3 * + 10 。 后是符号“÷” ，所以“/”进栈。如图9右图所示。
图9
9.最后一个数字2，输出，总的表达式为9 3 1 — 3 * + 10 2 。如图10左图所示。
10.因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1 — 3 * + 10 2 / + 。如图10右图所示。
图10
从刚才的推导中会发现，要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步：
- 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
- 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。
转载请注明链接：http://www.cnblogs.com/heyonggang/p/3359565.html
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3359565.html，如需转载请自行联系原作者
