数据结构 课件 栈的应用举例.ppt

大整数相加 相加从低位开始,输出从高位开始 用两个栈保存操作数（大整数） 结果保存到结果栈 四周加墙 八个方向移动表 表达式计算问题 中缀表示→转后缀表示 先对中缀表达式按运算优先次序加上括号，再把操作符后移到右括号的后面并以就近移动为原则，最后将所有括号消去。 如中缀表示 (A+B)*D-E/(F+A*D)+C，其转换为后缀表达式的过程如下： 利用栈将中缀表示转换为后缀表示 使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。 为了实现这种转换， 需要考虑各操作符 的优先级。 各个算术操作符的优先级 isp叫做栈内(in stack priority)优先数 icp叫做栈外(in coming priority)优先数。 操作符优先数相等的情况只出现在括号配对或栈底的“;”号与输入流最后的“;”号配对时。 中缀表达式转换为后缀表达式的算法 操作符栈初始化，将结束符‘#’进栈。然后读入中缀表达式字符流的首字符ch。 重复执行以下步骤，直到ch = ‘#’，同时栈顶的操作符也是‘#’，停止循环。 若ch是操作数直接输出，读入下一个字符ch。 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp： 若 icp(ch) isp(op)，令ch进栈，读入下一个字符ch。 若 icp(ch) isp(op)，退栈并输出。 若 icp(ch) == isp(op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。 算法结束，输出序列即为所需的后缀表达式。 表达式计算的算法 中缀转后缀算法见课本120 后缀表达式计算的算法见课本118 如何从后缀式求值？ 1 2 ? 3 4 2 / ? 6 ? + 1 1 2 2 2 3 2 3 4 2 3 4 2 2 3 2 1 1 1 1 6 1 6 从左到右扫描表达式 1.碰到操作数则入栈 2.碰到操作符则，从栈中弹出两个操作数加以计算，计算结果入栈 在后缀式中，优先权高的运算符领先于优先数权的运算符出现。也即任意三个相对位置紧邻的操作符opi opj opk, 优先级顺序： opi=opj=opk，因此中缀式里的任一操作符须等到另一个优先级小于或等于它的操作符出现，才可输出到后缀式。 分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a + b ? c - d 后缀式: a b c ? + d - 如何从原表达式求得后缀式？ 从原表达式求得后缀式的规律为： 1) 设立暂存运算符的栈; 2) 设表达式的结束符为“#”, 予设运算符栈的栈底为“#” 3) 若当前字符是操作数， 则直接发送给后缀式; 4) 若当前运算符的优先数高于栈顶运算符，则进栈; 5) 否则，退出栈顶运算符发送给后缀式; 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。 从原表达式求得后缀式的规律为： 优先级 操作符 1 单目-、！ 2 *、/、% 3 +、- 4 、=、、= 5 ==、!= 6 7 || * * * * 例二、 数制转换 例三、 括号匹配的检验 例四、 迷宫求解 例五、 表达式求值 例一、 大整数相加 数制转换的原理为： 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 检验含两种括弧的表