3.2.5 典型例题解析
【例3-1】实现n!的递归算法与利用栈实现非递归算法。
【分析】通过利用栈模拟在n的阶乘递归实现中，递归过程中的工作记录的进栈过程与出栈过程，实现非递归算法。定义一个二维数组，数组的第一维用于存放本层参数n，第二维用于存放本层要返回的结果。
【例3-2】将十进制数d转换为八进制数。
【分析】可用辗转相除法，算法步骤如下：
（1）将d除以x，取其余数。
（2）判断商是否为零，如果为零，则结束程序，否则将商送d，转（1）继续执行。
上面算法所得到的余数序列正好与x进制数的数字序列相反，因此利用栈的后进先出特性，先把得到的余数序列放入栈保存，最后依次出栈得到x进制数字序列。
例如，（1568）10=（3040）8，其运算过程如下：
十进制数转换为八进制数的算法描述如下：
【例3-3】利用栈将中缀表达式（8*（15-9）+6）/3转换为后缀表达式，并计算后缀表达式的值。
【分析】通常情况下，运算符总是出现在两个操作数之间，这种算术表达式被称为中缀表达式。编译系统在求解算术表达式时，先将中缀表达式转换为后缀表达式，然后对后缀表达式进行计算。在后缀表达式中，算术运算符出现在操作数之后，并且不含任何括号等分界符。
设置两个字符数组str和exp，str用来存放中缀表达式的字符串，exp用来存放后缀表达式的字符串。将中缀表达式转换为后缀表达式的方法是：依次扫描中缀表达式，如果遇到数字，则将其存入数组exp中。如果遇到运算符，则将栈顶运算符与当前运算符比较；如果当前的运算符的优先级大于栈顶运算符的优先级，则将当前运算符进栈；如果栈顶运算符的优先级大于当前运算符的优先级，则将栈顶运算符出栈，并保存到数组exp中。
为了处理方便，在遇到数字字符时，需要在其后补一个空格，作为分隔符。在计算后缀表达式的值时，需要对两位数以上的字符进行处理，然后将处理后的数字入栈。
一个表达式由操作数（operand）、运算符（operator）和分界符（delimiter）组成。一般情况下，操作数可以是常数，也可以是变量；运算符可以是算术运算符、关系运算符和逻辑运算符；分界符包括左右括号和表达式的结束符等。为了简化问题的描述，我们假设表达式中只包含加、减、乘、除等4种运算符和左、右圆括号。
1．将中缀表达式转换为后缀表达式
中缀表达式与后缀表达式相比，具有以下两个特点：
（1）后缀表达式与中缀表达式的操作数出现顺序相同，只是运算符先后顺序改变了。
（2）后缀表达式不出现括号。
说 明
由于后缀表达式具有以上特点，所以，编译系统在处理时不必考虑运算符的优先关系。只要从左到右依次扫描后缀表达式的各个字符，当读到的字符为运算符时，对运算符前面的两个操作数利用该运算符运算，并将运算结果作为新的操作对象替换两个操作数和运算符，继续扫描后缀表达式，直至处理完毕。
综上，表达式的运算分为两步：
（1）将中缀表达式转换为后缀表达式。
（2）依据后缀表达式计算表达式的值。
将一个算术表达式的中缀形式转化为相应的后缀形式前，需要先了解算术四则运算的规则。算术四则运算的规则是：
（1）先计算乘除，后计算加减。
（2）先计算括号内的表达式，后计算括号外的表达式。
（3）同级别的运算从左到右进行计算。
如何将中缀表达式转换为后缀表达式呢？设置一个栈，用于存放运算符。依次读入表达式中的每个字符，如果是操作数，则直接输出。如果是运算符，则比较栈顶元素符与当前运算符的优先级，然后进行处理，直至整个表达式处理完毕。这里，约定#作为后缀表达式的结束标志，假设栈顶运算符为ө1，当前扫描的运算符为ө2。
中缀表达式转换为后缀表达式的算法如下：
（1）初始化栈，将#入栈。
（2）如果当前读入的字符是操作数，则将该操作数输出，并读入下一字符。
（3）如果当前字符是运算符，记作ө2，则将ө2与栈顶的运算符ө1比较。如果栈顶的运算符ө1优先级小于当前运算符ө2，则将当前运算符ө2进栈。如果栈顶的运算符ө1优先级大于当前运算符ө2，则将栈顶运算符ө1出栈并将其作为后缀表达式输出。然后继续比较新的栈顶运算符ө1与当前运算符ө2的优先级，如果栈顶运算符ө1的优先级与当前运算符ө2相等，且ө1为“（”，ө2为“）”，则将ө1出栈，继续读入下一个字符。
（4）如果当前运算符ө2的优先级与栈顶运算符ө1相等，且ө1和ө2都为“#”，将ө1出栈，栈为空，则中缀表达式转换为后缀表达式完成，算法结束。
运算符优先关系如表3-2所示。
表3-2 运算符优先关系表
中缀表达式（8*（15-9）+6）/3转换为后缀表达式的输出过程如表3-3所示。
表3-3 中缀表达式（8*（15-9）+6）/3转换为后缀表达式的过程
中缀表达式转换为后缀表达式的算法如下：
表达式（8*（15-9）+6）/3经过转换后，后缀表达式为8 15 9-*6+3/。
2．后缀表达式的计算
计算后缀表达式的值需要设置一个操作数栈：S栈，用于存放操作数和中间运算结果。依次读入后缀表达式中的每个字符，如果是操作数，则将操作数进入S栈。如果是运算符，则将操作数出栈两次，然后对操作数进行当前操作符的运算，直至整个表达式处理完毕。
后缀表达式的求值算法如下：
（1）初始化S栈。
（2）如果当前读入的字符是操作数，则将该操作数进入S栈。
（3）如果当前字符是运算符ө，则将S栈退栈两次，分别得到操作数x和y，对x和y进行ө运算，即y ө x，得到中间结果z，将z进S栈。
（4）重复执行步骤（2）和（3），直至读入后缀的表达式处理完毕。
计算后缀表达式的值算法如下：
