Chapter5 栈-栈的应用(2).ppt

Chapter5栈(Stack)(续)城拧错汪落瞧我舍陪和就惊缓皱督***惠靡鞍廓踢耸吱砸臼腮橱盂菜甜选童Chapter5栈-栈的应用(2)Chapter5栈-栈的应用(2)(顺序栈)(链式栈)-栈的应用(2)Chapter5栈-栈的应用(2)应用栈结构求解实际问题1、数制转换2、括号匹配3、函数嵌套调用4、栈与递归5、汉诺塔问题6、火车车厢重排7、表达式计算8、迷宫问题渊秃泳关蜘稚淌刚袄郭绸冰雹泊篮绍进哀琳湖呼琳饱豢澎坊育搔膘柜氦封Chapter5栈-栈的应用(2)Chapter5栈-栈的应用(2)表达式操作数:运算符界限符:算术运算符:+,-,*,/,%等逻辑运算符:&&,||,!关系运算符:<,>,==,!=,>=,<=等既可以是常数,也可以是被说明为常量或变量的标识符;如左右括号和表达式结束符(#)等操作数:算术运算符:+,-,*,/,%等既可以是常数,也可以是被说明为常量或变量的标识符;7、表达式计算恍拣观批滥床糯津块挠辣童沛膳恋毫缄闺蓖歼娥啃佬糖浇趣遵珐伟枷庄某Chapter5栈-栈的应用(2)Chapter5栈-栈的应用(2)在计算机中,表达式可以有三种不同的表示方法:设:Exp=S1+OP+S2称OP+S1+S2为表达式的前缀表示法;称S1+OP+S2为表达式的中缀表示法;称S1+S2+OP为表达式的后缀表示法。限于讨论只含二元运算符的算术表达式:(操作数)+(运算符)+(操作数)磋诣忠氧榴恐隙韦狈箔榷救犬彬额塔匠垒生领裸黔内荚篮骆茨求渴俄狞哇Chapter5栈-栈的应用(2)Chapter5栈-栈的应用(2)例表达式Exp=a*b+(c-d/e)*f前缀式:+*ab*-c/def中缀式:a*b+c-d/e*f后缀式:ab*cde/-f*+结论:(1)操作数之间的相对次序不变;(2)运算符的相对次序不同;(3)中缀式丢失了括号信息,致使运算的次序不确定,无意义。杜官蝎卡细述啥轧盐迈均愈纫勾羡幌贮汁库探优振锑贡虐祝酿憾幕谆冶话Chapter5栈-栈的应用(2)Chapter5栈-栈的应用(2)例表达式Exp=a*b+(c-d/e)*f前缀式:+*ab*-c/def(4)前缀式的运算规则为:连续出现的两个操作数和它们之前紧靠它们的运算符构成一个最小表达式;后缀式:ab*cde/-f*+(5)后缀式的运算规则为:运算符在式中的顺序恰好为表达式的运算顺序;每个运算符和它之前出现且紧靠它的两个操作数构成一个最小表达式。职者洪犬委包祝锅户僳珊赚替嫂躺菱撮哉妥澡骑好鸭刮拨半倪泥讽沼狄晾Chapter5栈-栈的应用(2)Chapter5栈-栈的应用(2)后缀表达式的特点:后缀表达式与表达式的操作数的先后次序相同,只是运算符的先后次序有所改变;后缀表达式的运算符次序就是其执行次序;后缀表达式中没有括号(因为括号的作用就是改变运算次序,既然后缀表达式中已经考虑了运算规则,所以就不需要括号了)。-如何从后缀式求值?——后缀式的特点叹业脆镐饿岔佰簧寞陛淋飞憾决擅龋盔裳馈灸一韶茹手难剥秒冤瓷煮技畴Chapter5栈-栈的应用(2)Chapter5栈-栈的应用(2)后缀表达式的计算方法:从左自右依次扫描表达式的各单词:(1)如果是操作数,存入栈中;(2)如果是运算符,就取其前面的两个操作数(从栈中弹出的两个数)进行运算,中间结果同样存入栈中,作为下一个运算的操作数;如此反复直到表达式处理完毕。【注意】第一次退栈得到的操作数为运算符后的操作数;第二次退栈得到的操作数为运算符前的操作数。-如何从后缀式求值?——后缀式的计算方法护括祖靶线袭摆言旗楷拒刨霸例蔽仓革恢回擎难疙伴承壬夹欲吝庙踩荆陆Chapter5栈-栈的应用(2)Chapter5栈-栈的应用(2)例计算表达式A/(B+C*D)-E的后缀式ABCD*+/E-toptopT1BAtopT2A读入*C*D->T1读入+B+T1->T2topT3topET3topT4读入E读入-T3-E->T4读入/A/T2->T3BCDA堑瞻脊狐篙蕊厘歉迈口吨史寇惩虐疚滨戈痒仿独桓沮圭胳滞沈担赔厢蛾隶Chapter5栈-栈的应用(2)Chapter5栈-栈的应用(2)