a进栈顺序为(1,23),出栈顺序能否为(3,1,2)? 口不能,3出栈时,说明2和1都在栈里,而且2必须 先于仙出栈 top→ 321 作业: 1,2,3,4,5,6依次进栈,若出栈顺序为2,3,4,6,5,1 则栈大小至少为多少?
栈 ◼ 进栈顺序为(1,2,3)，出栈顺序能否为(3,1,2)? 不能，3出栈时，说明2和1都在栈里，而且2必须 先于1出栈 6 3 2 1 top 作业： 1，2，3，4，5，6依次进栈，若出栈顺序为2，3，4，6，5，1 则栈大小至少为多少？
桤的应用:表达式求值 个表达式由操作数亦称运算对象)、操作符 亦称运算符)和分界符组成。 算术表达式三种表示 a中缀(nfx表示 <操作数><操作符><操作数>,如A+B; 前缀( prefix)表示 <操作符><操作数><操作数>,如+AB 后缀( postfix表示 <操作数><操作数><操作符>,如AB+;
栈的应用：表达式求值 ◼ 一个表达式由操作数(亦称运算对象)、操作符 (亦称运算符) 和分界符组成。 ◼ 算术表达式三种表示 中缀(infix)表示 ➢ <操作数> <操作符> <操作数>，如 A+B； 前缀(prefix)表示 ➢ <操作符> <操作数> <操作数>，如 +AB； 后缀(postfix)表示 ➢ <操作数> <操作数> <操作符>，如 AB+； 7
桤的应用:表达式求值 n中缀表达式:A+B*(c-D)-E/F n后缀表达式:ABcD-*+EF|- 表达式中相邻两个操作符的计算次序为: 口优先级高的先计算; 优先级相同的自左向右计算; 口当使用括号时从最内层括号开始计算。 前缀和中缀表达式求值需要两个栈;后缀表达 式求值只需一个栈,相对简单些
栈的应用：表达式求值 ◼ 中缀表达式：A + B * ( C - D ) - E / F ◼ 后缀表达式：A B C D - * + E F / - ◼ 表达式中相邻两个操作符的计算次序为： 优先级高的先计算； 优先级相同的自左向右计算； 当使用括号时从最内层括号开始计算。 ◼ 前缀和中缀表达式求值需要两个栈；后缀表达 式求值只需一个栈，相对简单些。 8
栈的应用:表达式求值 从左向右扫描表达式,用一个栈暂存扫描到的 操作数或计算结果。 后缀表达式的计算顺序中已隐含了加括号的优 先次序,括号在后缀表达式中不出现 中缀表达式: 后缀表达式: A+B(C-D)-E/F ABCD一+EF/ R1 R R R R
栈的应用：表达式求值 ◼ 从左向右扫描表达式，用一个栈暂存扫描到的 操作数或计算结果。 ◼ 后缀表达式的计算顺序中已隐含了加括号的优 先次序，括号在后缀表达式中不出现 9 R1 R2 R3 R4 R5 A B C D - * + E F / - R1 R2 R3 R4 R5 A+B*(C-D)-E/F 中缀表达式： 后缀表达式：
作业: 写出下列中缀表达式的后缀表达式 1. AB*C 2. -A+B-C+D 3.A(B)+C 4.(A+B D+E/(F+AD)+C 5.A&&B‖(E>F) 6.!(A&&!(B<C)‖!(c>D))‖!(C<E) 10
10 作业： 写出下列中缀表达式的后缀表达式 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)