数据结构与算法课件c语言表述chapter5栈-栈的应用（2）

《数据结构与算法课件c语言表述chapter5栈-栈的应用（2）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法2010年秋季授课教师：张剑波授课班级：111091-2、114091-2班1Chapter5栈（Stack）2本章教学内容5.1栈的结构特点5.2栈的抽象数据类型5.3栈的公式化描述（顺序栈）5.4栈的链表描述（链式栈）5.5栈的应用3应用栈结构求解实际问题1、数制转换2、括号匹配3、函数嵌套调用4、栈与递归5、汉诺塔问题6、火车车厢重排7、表达式计算8、迷宫问题4表达式操作数：运算符界限符：算术运算符：+，-，*，/，%等逻辑运算符：&&，

2、

3、，！关系运算符：<，>，==，!=，>=，<=等既可以是常数，也可以是被说明为常量或变量的标识符；如左右括号和表达式结束符（#）

4、等操作数：算术运算符：+，-，*，/，%等既可以是常数，也可以是被说明为常量或变量的标识符；7、表达式计算5在计算机中，表达式可以有三种不同的表示方法：设：Exp＝S1＋OP＋S2称OP＋S1＋S2为表达式的前缀表示法；称S1＋OP＋S2为表达式的中缀表示法；称S1＋S2＋OP为表达式的后缀表示法。限于讨论只含二元运算符的算术表达式：（操作数）＋（运算符）＋（操作数）6例表达式Exp=a*b+(c-d/e)*f前缀式：+*ab*-c/def中缀式：a*b+c-d/e*f后缀式：ab*cde/-f*+结论：（1）操作数之间的相对次序不变；（2）运算符的相对次序不同；（3）中缀式丢失了括号信

5、息，致使运算的次序不确定，无意义。7例表达式Exp=a*b+(c-d/e)*f前缀式：+*ab*-c/def（4）前缀式的运算规则为：连续出现的两个操作数和它们之前紧靠它们的运算符构成一个最小表达式；后缀式：ab*cde/-f*+（5）后缀式的运算规则为：运算符在式中的顺序恰好为表达式的运算顺序；每个运算符和它之前出现且紧靠它的两个操作数构成一个最小表达式。8对一个表达式的计算可以通过两个步骤来实现：（1）先把表达式变换为相应的后缀表达式；（2）根据后缀表达式计算表达式的值。后缀表达式与表达式的操作数的排列次序完全相同，只是运算符改变了次序，因此，实现时，编译系统从左至右依次扫描表达式。

6、（1）若读到一个操作数，就把它作为后缀表达式的一部分输出；（2）对于运算符的处理，系统需设置一个存放运算符的栈。1、如何把表达式变换为相应的后缀表达式？9初始时，栈顶设置一个界限符#（与表达式结束符#配成一对）每当读到一个运算符时，就将其优先级与栈顶位置运算符优先级进行比较，以决定是把所读到的运算符进栈，还是将栈顶位置的运算符作为后缀表达式的一部分输出。运算符之间的优先关系对于任意两个相继出现的运算符θ1θ2，它们之间的优先关系至多是下面三种关系之一：θ1<θ2，θ1的优先级低于θ2；θ1=θ2，θ1的优先级等于θ2；θ1>θ2，θ1的优先级高于θ2。算法思想10对于+，-，*，/，(，

7、)，#，这几种运算符来说，其优先关系可以由算术四则运算规则得到。（1）先乘除，后加减；（2）从左到右算；（3）先括号内，后括号外。A、由（1）*，/>+，-；B、由（2）*>/，/>*，+>-，->+；C、由（2）对于+，-，*，/，当θ1=θ2时，令θ1>θ2，即+>+，->-，*>*，/>/；D、由（3）+，-，*，/的优先级均低于“(”，但高于“)”；运算符优先级11E、由（3）“(”的优先级均低于+，-，*，/，(；“)”的优先级均高于+，-，*，/，)；F、“(”=“)”，表示当左右括号相遇时，括号内的运算已经完成；G、“＃”是表达式的结束符，为了算法简洁，在表达式的最左边也需

8、设一个“＃”，构成整个表达式的一对括号；左“＃”的优先级低于+，-，*，/，(；+，-，*，/，)的优先级高于“＃”（结束符）；“＃”=“＃”表示整个表达式处理完毕。H、注意：“)”与“(”，“#”与“)”以及“(”与“#”之间无优先关系，因为表达式中不允许它们相继出现（若出现，则表达式有错），一旦遇见，则可以认为出现了语法错误。运算符优先级（续1）12建议：构造一张算符优先顺序表+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<≒)>>>>>>#<<<<<=13构造后缀表达式的算法（1）置运算符栈s为空栈，然后将表达式的起始符“#”入栈；（2）循

9、环：依次读入中缀表达式中一个单词；A、若是操作数，就将其输出，接着读下一个字符；B、若是运算符，就赋予x2，比较x2与栈顶运算符x1的优先级；若x2的优先级高于x1，则将x2进栈，读下一个单词；若x2的优先级低于x1，x1退栈，并作为后缀表达式的一个单词输出，再转B（即继续比较x2与新的栈顶运算符x1）；若x2的优先级等于x1，且x1为“(”，x2为“)”，则x1退栈，然后继续读下一个单词；若x2的优先级等于x1，且x1为“＃”，x