栈的应用举例

上传人:cl****1 文档编号:578441729 上传时间:2024-08-24 格式:PPT 页数:40 大小:625.51KB
返回 下载 相关 举报
栈的应用举例_第1页
第1页 / 共40页
栈的应用举例_第2页
第2页 / 共40页
栈的应用举例_第3页
第3页 / 共40页
栈的应用举例_第4页
第4页 / 共40页
栈的应用举例_第5页
第5页 / 共40页
点击查看更多>>
资源描述

《栈的应用举例》由会员分享,可在线阅读,更多相关《栈的应用举例(40页珍藏版)》请在金锄头文库上搜索。

1、例二、例二、 数制转换数制转换例三、例三、 括号匹配的检验括号匹配的检验例四、例四、 迷宫求解迷宫求解例五、例五、 表达式求值表达式求值例一、例一、 大整数相加大整数相加大整数相加大整数相加相加从低位开始,输出从高位开始用两个栈保存操作数(大整数)结果保存到结果栈数制转换的原理为: 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 ( ) / 显示和输入的十进制数对

2、应的八进制数显示和输入的十进制数对应的八进制数值值 InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion检验含两种括弧的表达式中括弧匹配的正确性。如表达式中 ()()或或( )等为正确的匹配, ()()或或()() 或或 ( ) )均为不正确的匹配。检验括弧匹配的方法可用“按期待的急迫程度进行处理”描述之 。 例如例如 考虑下列括号序列:( ( )可见,括弧匹配也遵循“后进先出”的规律。如何表示下列

3、“不匹配不匹配” 的情况?到来的右括弧非是所“期待”的;来了一个“不速之客”;直到结束,也没有等到“期待”的匹配;算法的设计思想:算法的设计思想:1)凡出现左括弧左括弧,则进栈进栈;2)凡出现右括弧右括弧,首先检查栈是否空? 若栈空栈空,则表明该“右括弧右括弧”多余多余 否则和栈顶元素和栈顶元素比较, 若相匹配相匹配,则“左括弧出栈左括弧出栈” 否则表明不匹配不匹配3)表达式表达式检验结束时结束时, 若栈空栈空,则表明表达式中匹配正确匹配正确 否则表明“左括弧左括弧”有余。有余。bool matching(char exp, int n) / 检测长度为检测长度为 n 的字符序列的字符序列 e

4、xp 中的括弧是否匹配中的括弧是否匹配 int i = 0; mat = true; InitStack(S); while ( i=opj=opk,因此中缀式里的任一操作符须等到另一个优先级小于或等于它的操作符出现,才可输出到后缀式。分析 “原表达式” 和 “后缀式”中的运算符:原表达式: a + b c - d 后缀式: a b c + d -如何从原表达式求得后缀式?如何从原表达式求得后缀式?从原表达式求得后缀式的规律为:从原表达式求得后缀式的规律为:1) 设立暂存运算符的栈栈;2) 设表达式的结束符为“#”, 予设运算符栈的栈底为“#”3) 若当前字符是操作数, 则直接发送给后缀式;4

5、) 若当前运算符的优先数高于栈顶运算符,则进栈;5) 否则,退出栈顶运算符发送给后缀式; 6) “(” 对它之前后的运算符起隔离作用,“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为:从原表达式求得后缀式的规律为:利用栈将中缀表示转换为后缀表示l使使用用栈栈可可将将表表达达式式的的中中缀缀表表示示转转换换成成它它的的前前缀缀表示和后缀表示。表示和后缀表示。l为了实现这种转换,为了实现这种转换,需要考虑各操作符需要考虑各操作符的优先级。的优先级。 优先级优先级 操作符操作符 1 单目单目- -、!、! 2 *、/、% 3 +、- - 4 、= 5 =、!= 6 & 7

6、| 各个算术操作符的优先级lisp叫做栈内叫做栈内(in stack priority)优先数优先数licp叫做栈外叫做栈外(in coming priority)优先数。优先数。l操操作作符符优优先先数数相相等等的的情情况况只只出出现现在在括括号号配配对对或或栈底的栈底的“;”号与输入流最后的号与输入流最后的“;”号配对号配对时。时。中缀表达式转换为后缀表达式的算法l操操作作符符栈栈初初始始化化,将将结结束束符符#进进栈栈。然然后后读入中缀表达式字符流的首字符读入中缀表达式字符流的首字符ch。l重重复复执执行行以以下下步步骤骤,直直到到ch = #,同同时时栈栈顶顶的的操作符也是操作符也是#

7、,停止循环。,停止循环。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

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 资格认证/考试 > 自考

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号