第七讲 栈的应用

第三章栈和队列栈的应用2023/2/51滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系2复习与回顾栈的特点栈的基本术语链栈顺序栈2滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系3

栈的应用举例一、数制转换二、括号匹配的检验三、表达式求值四、实现递归

本讲内容3滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系4

算法基于原理：“除基取余法”

即：除以基数取余数，逆序排列。

一、数制转换4滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系5

例如：（1348)10=(2504)8，其运算过程如下：

N

Ndiv8

Nmod8

13481684

168210

2125

202计算顺序输出顺序5滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系6voidconversion(){

InitStack(S);

scanf("%d",N);while(N){

Push(S,N%8);N=N/8;}while(!StackEmpty(S))

{

Pop(S,e);printf("%d",e);}}//conversion6滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系7二.括号匹配的检验括号匹配问题括号匹配{[()]}，((){})，()括号不匹配(()，()]，([)]检验括号匹配的方法：“期待的急迫程度”检查括号匹配的算法设一栈遇到左括号则入栈，遇到右括号时，若栈空，则不匹配(右括号太多)；否则，如果栈顶元素与该右括号匹配，则出栈；否则不匹配(括号不配对)。输入结束后，若栈为空，则匹配，否则不匹配(左括号太多)。7滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系81.算术表达式的组成操作数（运算对象或运算量）运算符界限符（如圆括号，作用是改变运算次序）

其中操作数可以是常量、变量、函数、表达式运算符有单目、双目，我们仅以+、-、*、/四种运算为例三.（算术）表达式的求值8滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系92.常见表达式有几种:

(根据运算符在表达式中的不同位置)

3*(5–2)中缀表达式3*(5–2)后缀表达式前缀表达式352-**3-529滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系10三种表达式的特点操作数之间的相对次序不变运算符的相对次序可能不同中缀式：必须有括号信息，否则运算顺序改变前缀式：无括号；连续出现的两个操作数和在它们之前出现且紧靠它们的运算符构成了一个最小表达式后缀式：无括号；运算符的排列顺序就是计算顺序，每个运算符加上在它之前且紧靠它的两个操作数构成了一个最小表达式。10滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系113.后缀表达式的计算（仅讨论个位数运算）

算法自左至右读取表达式中的字符设一栈存放操作数当读到运算符时，则取出栈顶的两个数进行运算，将结果入栈最终结果保存在栈中。11滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系12intPostfix(){ InitStack(S); read(c); while(c

!=

'='){

if(isdigit(c)){ read(v);

Push(S,v); }

else

{ Pop(S,b);

Pop(S,a); Push(S,Operate(a,c,b)); } read(c); }

Pop(S,result); returnresult;}12滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系13后缀表达式求值

用实型数栈S存放计算后缀式的中间及最终结果，求值算法可描述如下:

栈初始化。从左到右扫描后缀表达式，重复下述两步操作，直到表达式尾。①从表达式中取出下个TOKEN(操作数、运算符)②CASETOKENOF

操作数：将操作数直接入栈S;

运算符：出栈两个操作数，对其进行TOKEN操作，结果压入栈S

当遇到后缀表达式结束，栈顶的值就是结果(应是栈中唯一元素)。13滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系14835+562/-*-#

求值883835+83+5=8888562/6/2=38853-885-3=22*88*2=1616-8-16=-8-814滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系154.中缀表达式转化为后缀表达式分析

中缀表达式1+2*3+(4*5+6)*7后缀表达式123*+45*6+7*+算法读到操作数时立即输出运算符存放在栈中，遇到运算符时，弹出当前栈顶运算符直到遇到优先级更低的运算符为止。15滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系16中缀表达式转为后缀表达式

设中缀表达式和后缀表达式分别在数组IFX和PFX中，用栈S实现中缀式转为后缀式，对IFX中表达式从左到右扫描，设TOKEN是扫描读到的符号，转换算法可描述如下。栈初始化。从左到右扫描数组IFX，重复下述两步操作，直到表达式尾。

16滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系17

①从IPX中取出TOKEN(数字、运算符、左括号、右括号)；②CASETOKENOF

‘(’：压入栈S;

操作数：将操作数直接送入PFX，后面加一个空格;

运算符：如栈空或TOKEN比栈顶元素优先级高，将TOKEN进栈；否则，将栈内优先级高于或等于TOKEN的运算符，退栈并将退栈元素送入PFX；

‘)’：退栈并将退栈元素送PFX，直到碰到左括号，左括号退栈不送PFX。结束符号:连续退栈并送退栈元素到PFX，直至栈空。17滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系18举例：将中缀表达式

8-(3+5)*(5-6/2)#

转为后缀表达式883

835

835+

835+5

835+56

835+562

835+562/-

835+562/-*-

18滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系19表达式转换的简单方法中缀表达式转为后缀表达式有三步：（1）将中缀表达式中所有的子表达式按计算规则用嵌套括号括起来；（2）顺序将每对括号中的运算符移到相应括号的后面；（3）删除所有括号。

例如，将中缀表达式8-(3+5)*(5-6/2）转为后缀表达式。按如上步骤：执行完上面第一步后为：(8-((3+5)*(5-(6/2))))；执行完上面第二步后为：(8((35)+(5(62)/)-)*)-；执行完上面第三步后为：835+562/-*-19滨州学院计算机科学技术系2023/2/5滨州学院计算机科学技术系20作业用栈实现将中缀表达式

10+(18+9*3)/15-6#

转换成后缀表达式并进行后缀表达式的计算，分别画出两个步骤中的栈的变化示意图。20滨州学院计算机科学技术系四.

栈与递归1.函数调用与返回的过程2.递归函数3.递归的设计原则4.递归的优点和缺点5.消除递归21滨州学院计算机科学技术系1.函数调用与返回的过程（1）函数调用

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，

需先完成三项任务：将返回地址、所有实参等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。22滨州学院计算机科学技术系1.函数调用与返回的过程（2）函数返回

从被调用函数返回调用函数之前，应该完成下列三项任务：保存被调函数的计算结果；释放被调函数保存局部变量的数据区；依照被调函数保存的返回地址将控制转移到调用函数。函数嵌套调用时，后调用的函数先返回。23滨州学院计算机科学技术系intmain(){ intn=10; intsn;

sn=sum(n); cout<<sn<<endl;}intsum(intn){ inti,s=0;

for(i=1;i<n;i++) s+=i; returns;}intmain(){ intn=10; intsn;

sn=sum(n); cout<<sn<<endl;}intsum(intn){ inti,s=0;

for(i=1;i<n;i++) s+=i; returns;}main:n=10main:sn=sum:n=10goto:5sum:i=sum:s=0sum:i=11sum:s=55main:sn=55main()sum()24滨州学院计算机科学技术系2.递归函数函数直接或间接调用自身，称为递归(Recursion)。何时应用递归？问题具有递归的数学定义使用了递归的数据结构问题存在递归的解决方法25滨州学院计算机科学技术系递归过程的应用（1）（1）问题的数学定义是递归的：求n的阶乘n!

longFact(intn){if(n==1)return(1);elsereturn(n*Fact(n-1));}26滨州学院计算机科学技术系递归过程的应用（1）（1）问题的数学定义是递归的：计算Fibonacci数列：0,1,1,2,3,5,8,13,21,…longFib(intn){if(n==1)return0;if(n==2)return1;returnFib(n-1)+Fib(n-2);}27滨州学院计算机科学技术系递归过程的应用（1）（1）问题的数学定义是递归的：计算xn（n为整数，n≥0）28滨州学院计算机科学技术系递归过程的应用（1）（1）问题的数学定义是递归的：计算xn（n为整数，n≥0）doublePower(doublex,intn){if(n==0)return1;if(n==1)returnx;if(n%2==0)returnPower(x*x,n/2);elsereturnx*Power(x*x,n/2);}例如计算X64只需要6次乘法29滨州学院计算机科学技术系voidPrintLinkList(LinkListL){if(L!=NULL){printf(L->data);if(L->next!=NULL){PrintLinkList(L->next);}}}LL->next…以后将要学习的广义表、树和二叉树等结构也具有递归的特点，所以常常使用递归算法。递归过程的应用（2）（2）数据结构是递归的：

打印链表中各结点的值30滨州学院计算机科学技术系递归过程的应用（3）问题存在递归的解决方法n阶Hanoi塔问题：假设有三个分别命名为X,Y,Z的塔座，在X塔座上插有n个直径大小各不相同，依小到大编号为1，2，…,n的圆盘，要求：把X上的n个圆盘移到Z上，排列顺序相同，移动规则为：每次只能移动一个园盘；园盘可以在任一塔上做多次移动；在任何时刻，大盘不能压在小盘的上面。XYZ31滨州学院计算机科学技术系栈与递归的实现:Hanoi数学归纳法n=1,OK;设n=k时，若可以以Y为辅助塔，把k个盘从X移动到Z;当n=k+1时，方法：把X中k个盘，以Z为辅助塔，移动到Y;把X中第k+1个盘，移动到Z;把Y中k个盘，以X为辅助塔，移动到Z;32滨州学院计算机科学技术系问题存在递归的解决方法

Hanoi(n,a,b,c)表示解决n个盘子的汉诺塔问题（从a搬到c，可以借助b）。解决方法：若n=1，直接将盘子从a搬到c即可；否则，可以分解为如下步骤：Hanoi(n-1,a,c,b)move(n,a,c)Hanoi(n-1,b,a,c)voidHanoi(intn,chara,charb,charc){if(n==1)move(n,a,c);else{Hanoi(n-1,a,c,b);move(n,a,c);

Hanoi(n-1,b,a,c);}}33滨州学院计算机科学技术系3.递归的设计原则如果递归设计不当…容易造成无穷递归，最终会耗尽应用程序的栈空间，导致栈溢出错误，使程序失败。//无穷递归的例子//讲不完的故事voidStory(){print(“从前有座山，山上有个庙，庙里有个和尚在讲故事：”);

Story();}34滨州学院计算机科学技术系3.递归的设计原则（1）基准情形必须存在不用继续递归即可解决的情况。（2）不断推进对于需要递归解决的情况，每一次递归都要使得求解朝着基准情况的方向推进。（3）递归可行性假设所有的递归调用都能运行。（4）合成效益解决一个问题时，切勿在不同的递归调用中做重复的工作。35滨州学院计算机科学技术系一个不符合合成效益法则的例子：longFib(intn){if(n==1)return0;if(n==2)return1;returnFib(n-1)+Fib(n-2);}Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)36滨州学院计算机科学技术系4.递归的优点和缺点优点：递归函数结构清晰，程序易读，正确性容易证明。缺点：反复的递归函数调用使得执行效率较低。37滨州学院计算机科学技术系5.消除递归为什么消除递归？某些语言不支持函数的递归调用。在某些关键部分，递归算法影响了执行的效率。如何消除递归？（1）转化为递推（循环）。（2）自己管理一个递归工作栈。38滨州学院计算机科学技术系（1）递归和递推使用递推可以有效减少函数递归调用的次数，节省了时间和空间。//递推计算n!longFact(intn){longfactor=1;for(inti=1;i<n;i++)factor=i*factor;