表达式求值(数据结构).ppt

u中缀中缀(infix)表示表示 如如 A+B；u前缀前缀(prefix)表示表示 ，如如 +AB；u后缀后缀(postfix)表示表示 ，如如 AB+；rst1rst2rst3rst4rst5rst6rst1rst2rst3rst4rst5rst6n顺序扫描表达式的每一项，根据它的类顺序扫描表达式的每一项，根据它的类型做如下相应操作：型做如下相应操作：u若该项是若该项是操作数操作数，则将其，则将其压栈压栈；u若该项是若该项是操作符操作符，则，则连续从栈中连续从栈中退出两个操作数退出两个操作数Y和和X，形成运算指令形成运算指令XY，并将计算结果重新，并将计算结果重新压栈压栈。n当表达式的所有项都扫描并处理完后，当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。栈顶存放的就是最后的计算结果。步步 输入输入类类 型型动动 作作栈内容栈内容1置空栈置空栈空空2A操作数操作数 进栈进栈A3B操作数操作数 进栈进栈AB4C操作数操作数 进栈进栈ABC5D操作数操作数 进栈进栈ABCD6- -操作符操作符 D、C 退栈退栈, 计算计算C- -D, 结果结果 r1 进栈进栈ABr17*操作符操作符 r1、B 退栈退栈, 计算计算B*r1, 结果结果 r2 进栈进栈Ar28+操作符操作符 r2、A 退栈退栈, 计算计算A*r2, 结果结果 r3 进栈进栈r3步步 输入输入类类 型型动动 作作栈内容栈内容9E操作数操作数 进栈进栈r3E10F操作数操作数 进栈进栈r3EF11操作符操作符 F、E 退栈退栈, 计算计算EF, 结果结果 r4 进栈进栈r3r412G操作数操作数 进栈进栈r3r4G13/操作符操作符 G、r4 退栈退栈, 计算计算r4/E, 结果结果 r5 进栈进栈r3r514+ +操作符操作符 r5、r3 退栈退栈, 计算计算r3+r5, 结果结果 r6 进栈进栈r6操作符 ch ; ( *, /, % +, - - )isp (栈栈内内) 0 1 7 5 3 8icp (栈栈外外) 0 8 6 4 2 1