桤的应用:表达式求值 后缓表达式求值过程 a顺序扫描后缀表达式每一项 口若该项是操作数,则进栈 口若该项是操作符<op>, >若是单目运算符,则出栈一个操作数X,并将计算结 果<op>X进栈 若是双目运算符,则连续出栈两个操作数X和Y,并将 计算结果X<op>Y进栈 当表达式的所有项都扫描并处理完后,栈顶存放的 就是最后的计算结果。 11
栈的应用：表达式求值 ◼ 后缀表达式求值过程 顺序扫描后缀表达式每一项 若该项是操作数，则进栈 若该项是操作符<op>， ➢ 若是单目运算符，则出栈一个操作数X，并将计算结 果<op>X进栈 ➢ 若是双目运算符，则连续出栈两个操作数X和Y，并将 计算结果X <op> Y进栈 当表达式的所有项都扫描并处理完后，栈顶存放的 就是最后的计算结果。 11
桤的应用:表达式求值 后缀表达式求值过程: 步输入类型 动作 栈中内容 BCD-*+EF/ 置空栈 2A操作数进栈 A 3B操作数进栈 AB C操作数进栈 ABC 5D操作数进栈 ABCD 操作符D、C退栈,计算R=C-D进栈ABR1 操作符R1、B退栈,计算R2=BR进栈AR2 8+操作符R2、A退栈,计算R3=A+R2进栈R3 top→|D 9E操作数进栈 R3E p 10F操作数进栈 REF toD→B 11/操作符F、E退栈,计算R:E/F进栈R3R p→A 2 操作符R4、R退栈,计算R=R3-R进栈R p→空栈 12
栈的应用：表达式求值 12 步 输入 类型 动作 栈中内容 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 空栈 B A C D top top top A B C D - * + E F / - 后缀表达式求值过程：
桤的应用:表达式求值 后缀表达式求值过程: 步输入类型 动作 栈中内容 ABC D-*+EF/ 置空栈 2A操作数进栈 3B操作数进栈 AB C操作数进栈 ABC 5D操作数进栈 ABCD R1=C-D 操作符D、C退栈,计算R=C-D进栈ABR1 7 操作符R1、B退栈,计算R2=BR进栈AR2 8+操作符R2、A退栈,计算R3=A+R2进栈R3 top→|D 9E操作数进栈 R3E p 10F操作数进栈 REF toD→B 11/操作符F、E退栈,计算R:E/F进栈R3R A 12 操作符R4、R退栈,计算R=R3-R进栈R 13
栈的应用：表达式求值 13 步 输入 类型 动作 栈中内容 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 B A C D top top top R1=C-D A B C D - * + E F / - 后缀表达式求值过程：
桤的应用:表达式求值 后缀表达式求值过程 步输入类型 动作 栈中内容 ABCD-*+E F/ 置空栈 2A操作数进栈 3B操作数进栈 AB C操作数进栈 ABC 5D操作数进栈 ABCD R2=B R1 操作符D、C退栈,计算R=C-D进栈BR1 7 操作符R1、B退栈,计算R2=B=R进栈AR2 8+操作符R2、A退栈,计算R3=A+R2进栈R3 9E操作数进栈 R3E top→R=C-D 10F操作数进栈 REF t0D→B 11/操作符F、E退栈,计算R:E/F进栈R3R p→A 2 操作符R4、R退栈,计算R=R3-R进栈R 14
栈的应用：表达式求值 14 步 输入 类型 动作 栈中内容 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 B A top R1=C-D top top A B C D - * + E F / - R2=B*R1 后缀表达式求值过程：
桤的应用:表达式求值 后缀表达式求值过程 步输入类型 动作 栈中内容 ABCD-*+E F/ 置空栈 2A操作数进栈 3B操作数进栈 AB C操作数进栈 ABC 5D操作数进栈 ABCD 操作符D、C退栈,计算R=C-D进栈ABR1 R3=A+R2 操作符R1、B退栈,计算R2=BR进栈AR2 操作符R2、A退栈,计算R3=A+R2进栈R3 9E操作数进栈 R3E 10F操作数进栈 REF top→|R2=BR1 11/操作符F、E退栈,计算R:E/F进栈R3R p→A 12 操作符R4、R退栈,计算R=R3-R进栈R p→空栈 15
栈的应用：表达式求值 15 步 输入 类型 动作 栈中内容 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 A top A B C D - * + E F / - R2=B*R1 R3=A+R2 top 空栈 后缀表达式求值过程：