桤的应用:表达式求值 后缀表达式求值过程 步输入类型 动作 栈中内容 ABCD-*+EF/ 置空栈 2A操作数进栈 3B操作数进栈 AB C操作数进栈 ABC 5D操作数进栈 ABCD 操作符D、C退栈,计算R=C-D进栈ABR1 操作符R1、B退栈,计算R2=BR进栈AR2 8+操作符R2、A退栈,计算R3=A+R2进栈R3 9E操作数进栈 top→ F RE 10F操作数进栈 REF toD→→E 11/操作符F、E退栈,计算R:E/F进栈R3R top→|R3=A+R2 12 操作符R4、R退栈,计算R=R3-R进栈R 16
栈的应用：表达式求值 16 步 输入 类型 动作 栈中内容 1 置空栈 2 A 操作数 进栈 A 3 B 操作数 进栈 A B 4 C 操作数 进栈 A B C 5 D 操作数 进栈 A B C D 6 - 操作符 D、C退栈，计算R1=C-D进栈 A B R1 7 * 操作符 R1、B退栈，计算R2=B*R1进栈 A R2 8 + 操作符 R2、A退栈，计算R3=A+R2进栈 R3 9 E 操作数 进栈 R3 E 10 F 操作数 进栈 R3 E F 11 / 操作符 F、E退栈，计算R4=E / F进栈 R3 R4 12 - 操作符 R4、R3退栈，计算R5=R3-R4进栈 R5 top top A B C D - * + E F / - R3=A+R2 E top F 后缀表达式求值过程：
桤的应用:表达式求值 后缀表达式求值过程 步输入类型 动作 栈中内容 ABCD-*+ E 置空栈 2A操作数进栈 3B操作数进栈 AB C操作数进栈 ABC 5D操作数进栈 ABCD 操作符D、C退栈,计算R=C-D进栈ABR1 R4=E/F 操作符R1、B退栈,计算R2=BR进栈AR2 8+操作符R2、A退栈,计算R3=A+R2进栈R3 9E操作数进栈 top→ F R3E 10F操作数进栈 REF p E 操作符F、E退栈,计算R=E/F进栈R3R top→|R3=A+R2 12 操作符R4、R退栈,计算R=R3-R进栈R 17
栈的应用：表达式求值 17 步 输入 类型 动作 栈中内容 1 置空栈 2 A 操作数 进栈 A 3 B 操作数 进栈 A B 4 C 操作数 进栈 A B C 5 D 操作数 进栈 A B C D 6 - 操作符 D、C退栈，计算R1=C-D进栈 A B R1 7 * 操作符 R1、B退栈，计算R2=B*R1进栈 A R2 8 + 操作符 R2、A退栈，计算R3=A+R2进栈 R3 9 E 操作数 进栈 R3 E 10 F 操作数 进栈 R3 E F 11 / 操作符 F、E退栈，计算R4=E / F进栈 R3 R4 12 - 操作符 R4、R3退栈，计算R5=R3-R4进栈 R5 A B C D - * + E F / - R3=A+R2 E top F R4=E/F top top 后缀表达式求值过程：
桤的应用:表达式求值 后缀表达式求值过程 步输入类型 动作 栈中内容 ABCD-*+ EF 置空栈 2A操作数进栈 3B操作数进栈 AB C操作数进栈 ABC 5D操作数进栈 ABCD 操作符D、C退栈,计算R=C-D进栈ABR1 操作符R1、B退栈,计算R2=BR进栈AR2 R5=R3-R4 8+操作符R2、A退栈,计算R=A+R进栈R 9E操作数进栈 R3E 10F操作数进栈 REF top→|R=E/F 11/操作符F、E退栈,计算R:E/F进栈R3R top→|R3=A+R2 操作符R4、R3退栈,计算R=R3-R进栈R p→空栈 18
栈的应用：表达式求值 18 步 输入 类型 动作 栈中内容 1 置空栈 2 A 操作数 进栈 A 3 B 操作数 进栈 A B 4 C 操作数 进栈 A B C 5 D 操作数 进栈 A B C D 6 - 操作符 D、C退栈，计算R1=C-D进栈 A B R1 7 * 操作符 R1、B退栈，计算R2=B*R1进栈 A R2 8 + 操作符 R2、A退栈，计算R3=A+R2进栈 R3 9 E 操作数 进栈 R3 E 10 F 操作数 进栈 R3 E F 11 / 操作符 F、E退栈，计算R4=E / F进栈 R3 R4 12 - 操作符 R4、R3退栈，计算R5=R3-R4进栈 R5 A B C D - * + E F / - R3=A+R2 R4=E/F top top R5=R3-R4 top 空栈 后缀表达式求值过程：
桤的应用:表达式求值 n中缀表达式转换为后缀表达式 口使用栈将中缀表达式转换成前缀或后缀表达式。 口为了实现转换,需要考虑各操作符的优先级。 结束符“#”优先级最低 左括号“(”栈外优先级最高,进栈后极低 右括号“)”栈外优先级极低 >其他进栈后优先级加1,这可满足自左向右计算要求 各个算术操作符的优先级 操作符 # isp(栈内优先级)0 icp(栈外优先级)0 (16 /54 3 )61 19
栈的应用：表达式求值 ◼ 中缀表达式转换为后缀表达式 使用栈将中缀表达式转换成前缀或后缀表达式。 为了实现转换，需要考虑各操作符的优先级。 ➢ 结束符“#”优先级最低 ➢ 左括号“(”栈外优先级最高，进栈后极低 ➢ 右括号“)”栈外优先级极低 ➢ 其他进栈后优先级加1，这可满足自左向右计算要求 19 各个算术操作符的优先级 操作符 # ( * / % + - ) isp(栈内优先级) 0 1 5 3 6 icp(栈外优先级) 0 6 4 2 1