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)