第3章-链栈及栈的应用.ppt

第3章 链栈及栈的应用 3 表达式求值 把表达式翻译成正确的机器执行指令,要正确地解释表达式. 算符优先法是根据算术四则运算的规定来编译或解释表达式的. 表达式由操作数,运算符,界限符组成.操作数可以是变量或常量;此处考虑的运算符仅为+-*/,界限符有左右括号和结束符”#”. 为实现算符优先法,可以使用两个工作栈.OPTR:存放运算符, OPND:存放操作数或运算结果. 算法的基本思想: (1)置操作数栈为空,表达式起始符”#”,作为运算符栈的栈底. (2)依次读入表达式中每个字符,若是操作数进OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为”#”). 算法 OperandType EvaluateExpression(){ //算术表达式求值的算符优先算法,设OPTR和OPND分别为运算符栈和操作数栈;OP为算符(运算符和界限符)集合 InitStack(OPTR;) Push(OPTR,’#’);InitStack(OPND);c=getchar(); while(c!=‘#’||GetTop(OPTR)!=‘#’){ if (!In(c,OP)){Push((OPND,c);c=getchar();}//操作数进操作数栈 else switch(Precede(GetTop(OPTR),c){ case ‘’: //栈顶元素优先权低,进运算符栈 Push(OPTR,c);c=getchar(); break; case ‘=’://脱括号并接收下一个字符,左右括号或两”#”相遇 Pop(OPTR,x);c=getchar(); break; case ‘’: //栈顶元素优先权高, 运算符退栈,操作数退栈, //并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; }//switch }//while return GetTop(OPND); }//EvaluateExpression 3.3 栈与递归 例: 斐波那契数列为：0、1、1、2、3、……，即：　　 fib(0)=0;　　 fib(1)=1;　　 fib(n)=fib(n-1)+fib(n-2) （当n1时）。　　 写成递归函数有：　　 int fib(int n)　　 { if (n==0) return 0;　　 if (n==1) return 1;　　 if (n1) return fib(n-1)+fib(n-2);　　 } 　　 递归执行分递推和回归两个阶段。 在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。　 在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。 通常,一个函数调用另一个函数之前,要作如下工作: a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区; c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情: a)保存被调函数的计算结果; b)释放被调用函数的数