栈的应用举例

例二、例二、 数制转换数制转换例三、例三、 括号匹配的检验括号匹配的检验例四、例四、 迷宫求解迷宫求解例五、例五、 表达式求值表达式求值例一、例一、 大整数相加大整数相加大整数相加大整数相加 相加从低位开始,输出从高位开始 用两个栈保存操作数（大整数） 结果保存到结果栈数制转换的原理为： N = (N div d)d + N mod d例如：例如：（1348)10 转换成 (2504)8 的运算过程如下： N N div 8 N mod 8计算顺序输出顺序1348 168 4 168 21 0 21 2 5 2 0 2数制转换数制转换void conversion ( ) / 显示和输入的十进制数对应的八进制数值显示和输入的十进制数对应的八进制数值 InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion检验含两种括弧的表达式中括弧匹配的正确性。如表达式中 （）（）或或（ ）等为正确的匹配， （）（）或或（）（） 或或 ( ) )均为不正确的匹配。检验括弧匹配的方法可用“按期待的急迫程度进行处理”描述之 。 例如例如 考虑下列括号序列：( ( )可见，括弧匹配也遵循“后进先出”的规律。如何表示下列“不匹配不匹配” 的情况？ 到来的右括弧非是所“期待”的; 来了一个“不速之客”; 直到结束，也没有等到“期待”的匹配;算法的设计思想：算法的设计思想：1）凡出现左括弧左括弧，则进栈进栈；2）凡出现右括弧右括弧，首先检查栈是否空？ 若栈空栈空，则表明该“右括弧右括弧”多余多余 否则和栈顶元素和栈顶元素比较， 若相匹配相匹配，则“左括弧出栈左括弧出栈” 否则表明不匹配不匹配3）表达式表达式检验结束时结束时， 若栈空栈空，则表明表达式中匹配正确匹配正确 否则表明“左括弧左括弧”有余。有余。bool matching(char exp, int n) / 检测长度为检测长度为 n 的字符序列的字符序列 exp 中的括弧是否匹配中的括弧是否匹配 int i = 0; mat = true; InitStack(S); while ( i=opj=opk，因此中缀式里的任一操作符须等到另一个优先级小于或等于它的操作符出现，才可输出到后缀式。分析 “原表达式” 和 “后缀式”中的运算符:原表达式: a + b c - d 后缀式: a b c + d -如何从原表达式求得后缀式？如何从原表达式求得后缀式？从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：1) 设立暂存运算符的栈栈;2) 设表达式的结束符为“#”, 予设运算符栈的栈底为“#”3) 若当前字符是操作数， 则直接发送给后缀式;4) 若当前运算符的优先数高于栈顶运算符，则进栈;5) 否则，退出栈顶运算符发送给后缀式; 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：利用栈将中缀表示转换为后缀表示l使用栈可将表达式的中缀表示转换成它的前缀使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。表示和后缀表示。l为了实现这种转换，为了实现这种转换，需要考虑各操作符需要考虑各操作符的优先级。的优先级。优先级优先级 操作符操作符 1 单目单目- -、！、！ 2 *、/、% 3 +、- - 4 、= 5 =、!= 6 & 7 | 各个算术操作符的优先级lisp叫做栈内叫做栈内(in stack priority)优先数优先数licp叫做栈外叫做栈外(in coming priority)优先数。优先数。l操作符优先数相等的情况只出现在操作符优先数相等的情况只出现在括号配对括号配对或或栈底的栈底的“;”号与输入流最后的号与输入流最后的“;”号配对号配对时。时。中缀表达式转换为后缀表达式的算法l操作符栈初始化，将结束符操作符栈初始化，将结束符#进栈。然后读进栈。然后读入中缀表达式字符流的首字符入中缀表达式字符流的首字符ch。l重复执行以下步骤，直到重复执行以下步骤，直到ch = #，同时栈顶，同时栈顶的操作符也是的操作符也是#，停止循环。，停止循环。u若若ch是操作数直接输出，读入下一个字符是操作数直接输出，读入下一个字符ch。u若若ch是操作符是操作符，判断，判断ch的优先级的优先级icp和和位于位于栈顶栈顶的的操作符操作符op的优先级的优先级isp：u若若 icp(ch) isp(op)，令，令ch进栈，读入下一个进栈，读入下一个字符字符ch。u若若 icp(ch) isp(op)，退栈并输出。，退栈并输出。u若若 icp(ch) = isp(op)，退栈但不输出，若退，退栈但不输出，若退出的是出的是“(”号读入下一个字符号读入下一个字符ch。l算法结束，输出序列即为所需的后缀表达式。算法结束，输出序列即为所需的后缀表达式。a ( b ( c + d / e ) - f ) #a (b (c+d /e / /+ -f - #另一个例子：A+B*(C-D)-E/F另一个例子： A+B*(C-D)-E/F表达式计算的算法表达式计算的算法l中缀转后缀算法见课本120l后缀表达式计算的算法见课本118