数据结构第3章栈和队列.ppt

3.2.5表达式求值1）问题的提出

设计一个小计算器:对键入的表达式进行求值。如何对表达式求值呢？高级语言中的赋值语句：变量=表达式；Y=2;Z=3;X=y+z*2;2）表达式的构成操作数+运算符+界符（如括号）3）表达式的求值：例5+6?(1+2)-4按照四则运算法则，上述表达式的计算过程为：5+6?(1+2)-4=5+6?3-4=5+18-4=23-4=191234如何确定运算符的运算顺序？运算符和界限符统称为算符。根据算术四则运算的规则（即中缀式的运算规则），任两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系之一：θ1θ2θ1的优先权低于θ2θ1=θ2θ1的优先权等于θ2θ1θ2θ1的优先权高于θ2算符间的优先关系θ2θ1+-*/()#+-*/(=)#=算法需两个栈。一个是运算符栈(OPTR)；另一个是操作数或运算结果栈(OPND)。算法的基本思想是：（1）首先置操作数栈为空栈；为了使表达式中第一个运算符能够进栈，首先将一个优先权最低的运算符‘#’压入运算符栈中成为其栈底。（2）从左向右依次读出表达式中的每一个字符，①若为操作数，则将其压入操作数栈中，接着读出下一个字符；②若为运算符，则和运算符栈的栈顶运算符比较优先权：ⅰ如果读出的运算符的优先权高于运算符栈栈顶运算符的优先权，则将其压入运算符栈中，接着读出下一个字符；ⅱ如果读出的运算符的优先权等于运算符栈栈顶运算符的优先权（即左右括号相遇），则从运算符栈中退出一个运算符（即左括号）；ⅲ如果读出的运算符的优先权低于运算符栈栈顶运算符的优先权，则从操作数栈连续退出两个操作数（先退出的是第二操作数，后退出的是第一操作数），从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈中。算法中还调用了两个函数。其中Precede()的功能是判断两个运算符θ1和θ2的优先关系；Operate()的功能是求两数a和b作θ运算的结果。表达式求值示意图：5+6?(1+2)-4topbaseOPTR栈#OPND栈topbase5toptop+top6top×top(top1top+top2toptoptoptop3toptoptoptoptop18toptoptoptop23top-top4toptoptoptop19toptoptop5读入表达式过程：+6×(1+2)-4#=191+2=36×3=185+18=2323-4=19一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，称为递归函数。很多数学函数是递归定义的，如阶乘函数若n=0若n02阶Fibonacci数列若n=0若n=1其他情形123.3栈与递归的实现递归函数执行过程的信息传递和控制转移可以用栈结构来实现。系统将整个程序运行时所需的空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当退出一个函数时，就释放它所占用的存储区，当前工作的函数的数据区总在栈顶。例如，递归函数fact（4）的执行过程如图所示，例递归的执行情况分析voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i=w;++i)printf(“%3d,”,w);printf(“/n”);}}运行结果：1，2，2，3，3，3，递归调用执行情况如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)输出：3,3,3w2print(1);（2）w=2（1）w=3top(3)输出：2,2w1print(0);（3）w=1（2）w