①i进栈,i出栈,j进栈,j出栈,k进栈,k出栈。此时具有最小值的排在最前面p位置,具有中间 值的排在其后P位置,具有最大值的排在pk位置,有p<P<p,不可能出现P<Pk<P的情形 ②i进栈,i出栈,j进栈,k进栈,k出栈,j出栈。此时具有最小值的排在最前面p位置,具有最大 值的排在P位置,具有中间值的排在最后pk位置,有p<P<P,不可能出现P<pk<P的情形; ③i进栈,j进栈,j出栈,i出栈,k进栈,k出栈。此时具有中间值的排在最前面p位置,具有最小 值的排在其后P位置,有P<p<Pk不可能出现P<Pk<P的情形; ④i进栈,j进栈,j出栈,k进栈,k出栈,i出栈。此时具有中间值的排在最前面p位置,具有最大 值的排在其后P位置,具有最小值的排在pk位置,有pk<p<P,也不可能出现P<pk<P的情形; ⑤i进栈,j进栈,k进栈,k出栈,j出栈,i出栈。此时具有最大值的排在最前面p位置,具有中间 值的排在其后P位置,具有最小值的排在pk位置,有pk<P<p,也不可能出现p<pk<p的情形 4-5写出下列中缀表达式的后缀形式: (1)A*B*C (2)-A+B-C+D (3)A*-B+C (4)(A+B)*D+E/(F+A*D)+C (5)A&&B||!(E>F)体注:按C+的优先级* (6)!(A&&!((B<C)|(C>D))C<E) 【解答】 (AB+C+ (2)A-B+C-D+ (3)AB-*C (4)AB+D*EFAD*+/+C+ (5)AB&&EF>!|1 6ABC<CD>I!&&ICE<Il 4-7设表达式的中缀表示为a*x-b/x↑2,试利用栈将它改为后缀表示ax*bx2↑/-。写出转换过程中栈 的变化。 【解答】 步序扫描项项类型 栈的变化 输出 操作数 直接输出,读下一符号 操作符sp('#')<lp(*'),进栈,读下一符号# 梁作数 直接输出,读下一符号 xspC*')>i2(=),退栈输 σ卹sp("#')<ip(-'),进栈,读下一符号 操作数 直接输出,读下一符号 /操作符p('-')<ip(")进栈,读下一符号#- 7 操作数 直接输出,读下一符号 #-/ 操作符 (/)<igp(↑'),进栈,读下一符号#-/↑ #-/↑ 10#操作符wsp("↑')>ic('#'),退栈输出 ax*bx2↑① i 进栈，i 出栈，j 进栈，j 出栈，k 进栈，k 出栈。此时具有最小值的排在最前面 pi 位置，具有中间 值的排在其后 pj 位置，具有最大值的排在 pk 位置，有 pi < pj < pk, 不可能出现 pj < pk < pi 的情形； ② i 进栈，i 出栈，j 进栈，k 进栈，k 出栈，j 出栈。此时具有最小值的排在最前面 pi 位置，具有最大 值的排在 pj 位置，具有中间值的排在最后 pk 位置，有 pi < pk < pj , 不可能出现 pj < pk < pi 的情形； ③ i 进栈，j 进栈，j 出栈，i 出栈，k 进栈，k 出栈。此时具有中间值的排在最前面 pi 位置，具有最小 值的排在其后 pj 位置，有 pj < pi < pk, 不可能出现 pj < pk < pi 的情形； ④ i 进栈，j 进栈，j 出栈，k 进栈，k 出栈，i 出栈。此时具有中间值的排在最前面 pi 位置，具有最大 值的排在其后 pj 位置，具有最小值的排在 pk 位置，有 pk < pi < pj, 也不可能出现 pj < pk < pi 的情形； ⑤ i 进栈，j 进栈，k 进栈，k 出栈，j 出栈，i 出栈。此时具有最大值的排在最前面 pi 位置，具有中间 值的排在其后 pj 位置，具有最小值的排在 pk 位置，有 pk < pj < pi, 也不可能出现 pj < pk < pi 的情形； 4-5 写出下列中缀表达式的后缀形式： (1) A * B * C (2) - A + B - C + D (3) A* - B + C (4) (A + B) * D + E / (F + A * D) + C (5) A && B|| ! (E > F) /*注：按 C++的优先级*/ (6) !(A && !( (B < C)||(C > D) ) )||(C < E) 【解答】 (1) A B * C * (2) A - B + C - D + (3) A B - * C + (4) A B + D * E F A D * + / + C + (5) A B && E F > ! || (6) A B C < C D > || ! && ! C E < || 4-7 设表达式的中缀表示为 a * x - b / x↑2，试利用栈将它改为后缀表示 ax * bx2↑/ -。写出转换过程中栈 的变化。 【解答】 步序 扫描项 项类型 动 作 栈的变化 输 出 0  '#' 进栈, 读下一符号 # 1 a 操作数  直接输出, 读下一符号 # a 2 * 操作符  isp ( ' # ' ) < icp ( ' * ' ), 进栈, 读下一符号 # * a 3 x 操作数  直接输出, 读下一符号 # * a x 4 - 操作符  isp ( ' * ' ) > icp ( ' - ' ), 退栈输出 # a x *  isp ( ' # ' ) < icp ( ' - ' ), 进栈, 读下一符号 # - a x * 5 b 操作数  直接输出, 读下一符号 # - a x * b 6 / 操作符  isp ( ' - ' ) < icp ( '/' ), 进栈, 读下一符号 # -/ a x * b 7 x 操作数  直接输出, 读下一符号 # -/ a x * b x 8 ↑ 操作符  isp ( ' / ' ) < icp ( '↑' ), 进栈, 读下一符号 # -/↑ a x * b x 9 2 操作数  直接输出, 读下一符号 # -/↑ a x * b x 2 10 # 操作符  isp ( '↑' ) > icp ( ' # ' ), 退栈输出 # -/ a x * b x 2↑  isp ( ' / ' ) > icp ( ' # ' ), 退栈输出 # - a x * b x 2↑/  isp ( ' - ' ) > icp ( ' # ' ), 退栈输出 # a x * b x 2↑/ -