第四章栈的应用

1、4.1.5 4.1.5 栈的应用举例栈的应用举例例一、例一、 数制转换数制转换例二、例二、 括号匹配的检验括号匹配的检验4.2 4.2 表达式求值表达式求值4.3.4.3.递归递归例一、例一、 数制转换数制转换算法基于原理：算法基于原理： N = (N div d)d + N mod d 例如：例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输出顺序输出顺序 void Transform(long num, int r) Stack a; InitStack(a)

2、; /初始化栈初始化栈 while(num!=0) int k=num % r; Push(a,k); /计算顺序进栈计算顺序进栈 num/=r; while(!StackEmpty(a) /出栈出栈 coutPop(a); coutendl; 例二、例二、 括号匹配的检验括号匹配的检验假设在表达式中假设在表达式中（）（）或或（ ）等为正确的格式，等为正确的格式，（ ）或（）或（ ）或或 （）（）)均为不正确的格式。均为不正确的格式。则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配不匹配的情况: : 到来的右括弧到来的右括弧并非是所并非是所“期待期待”的；的

3、；例如：考虑下列括号序列：例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 到来的是“不速之客”； 直到结束，也没有到来所“期待”的括弧。 算法的设计思想：算法的设计思想： 1 1）左括弧左括弧: : 则进栈则进栈 2 2）出现）出现右括弧右括弧: : 若栈空，若栈空，不匹配不匹配。 否则和栈顶元素比较，否则和栈顶元素比较， 若相匹配，则若相匹配，则“左括弧出栈左括弧出栈” ” ， 否则表明否则表明不匹配不匹配。 3 3）表达式检验）表达式检验结束结束时，时， 若若栈空栈空，表达式中匹配，表达式中匹配正确正确， 否则否则不匹配不匹配。 switch (ch) case : ca

4、se (: Push(a,ch); break; /左括号进栈左括号进栈 case : if(Peek(a)=) Pop(a); /右括号右括号 else return 0; break; if(StackEmpty(a) return 1; else return 0; 二元运算符的表达式定义二元运算符的表达式定义: : 表达式表达式:=(:=(操作数操作数)+()+(运算符运算符)+()+(操作数操作数) ) 操作数操作数:=:=简单变量简单变量 | | 表达式表达式 简单变量简单变量:=:=标识符标识符 | | 无符号整数无符号整数4.2 4.2 表达式求值表达式求值 表达式的三种标识方

5、法：表达式的三种标识方法：设设 Exp = S1 + OP + S2则称则称 OP + S1 + S2 为为前缀前缀表示法表示法 S1 + OP + S2 为为中缀中缀表示法表示法 S1 + S2 + OP 为为后缀后缀表示法表示法 Exp = a b + (c d / e) f前缀式: + a b c / d e f中缀式: a b + c d / e f后缀式: a b c d e / f + 结论结论: :1 1）操作数之间的相对次序）操作数之间的相对次序不变不变; ;2 2）运算符的相对次序）运算符的相对次序不同不同; ;4)4)前缀式前缀式连续出现的两个操作数连续出现的两个操作数和在

6、它们之前且紧靠它们的运算和在它们之前且紧靠它们的运算符构成一个最小表达式符构成一个最小表达式; ;3)3)中缀式中缀式丢失了括弧信息，丢失了括弧信息， 致使运算的次序致使运算的次序不确定不确定;5)5)后缀式后缀式算符在式中出现的顺序算符在式中出现的顺序恰为恰为表达式的运算顺序表达式的运算顺序; ;每个运算每个运算符和在它之前出现且紧靠它的两符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。个操作数构成一个最小表达式。中缀式转换为后缀式中缀式转换为后缀式: :1. 3/5+6 3 5 / 6 +2. 16-9*(4+3) 16 9 4 3 + * -3. 2*(x+y)/(1-x) 2

7、x y + * 1 x - /4. (25 + x) * (a * (a+b) +b)25 x +aa b +*b +*如何从后缀式求值？如何从后缀式求值？先找运算符，再找操作数先找运算符，再找操作数例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f(a b)+(c-d/e) f char a30=12 3 20 4 / * 8 - 6 * +;4/5*1587-6*42+54 while(ch!=) /扫描每一个字符扫描每一个字符 switch(ch) case *: x=Pop(S)*Pop(S); break; case /: x=Pop(S); / 弹

8、出除数弹出除数 if(x!=0.0) x=Pop(S)/x; /弹出的是被除数弹出的是被除数 else cerrDiv by 0!x; /读入一个浮点数读入一个浮点数 Push(S,x); /浮点数或运算的结果压栈浮点数或运算的结果压栈 insch; /输入下一个字符输入下一个字符 如何从中缀表达式求得后缀式？如何从中缀表达式求得后缀式？在中缀式中，每个运算符的运算次序要由它它后一个后一个运算符运算符来定，在后缀式中，运算符按实际运算次序排列。表达式: : a + b c d / e f 后缀式: : a b c + d e / f 从中缀式求得后缀式的算法为：从中缀式求得后缀式的算法为：1)

9、 设立操作符栈栈R R；运算符优先级运算符优先级 高于栈顶则入栈高于栈顶则入栈; ; 否则，否则，出栈出栈发发给后缀式给后缀式S2S2中；直到高于栈顶则中；直到高于栈顶则入栈入栈2) 设表达式的结束符为“”， 预设运算符栈R的栈底为“”；3) 若当前字符是操作数， 则直接发送给后缀式S2中。4)4)“(”“(” 直接直接进栈进栈; ;优先级最低优先级最低“0 0” “)” “)”R R中运算符中运算符出栈出栈, , 直到遇到直到遇到 左括弧左括弧“(”(” 为止。为止。 字符串字符串S1=10+(18+9*3)/15-6 栈栈R R暂存运算符暂存运算符S2存放转换后的后缀式字符串字符串1 0+

10、(1 8+9*3)*+/1 5-/ +- 保存保存被调函数的被调函数的计算结果计算结果； 释放释放被调函数的被调函数的数据区数据区； 依照被调函数保存的返回地址将依照被调函数保存的返回地址将控制转移控制转移到主调函数。到主调函数。从被调用函数从被调用函数返回返回主调用函数主调用函数之前之前，应该完成下列三项任务：应该完成下列三项任务：多个函数嵌套调用的规则是：多个函数嵌套调用的规则是：内存管理实行内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区的数据区函数函数a

11、的数据区的数据区函数函数b的数据区的数据区 函数函数f(n)=n!，递归函数递归函数f f(n)可表示为可表示为 1 (n=0) f(n)= n*f(n-1) (n0)递归函数执行的过程可视为同一同一函数函数进行嵌套调用，例如： 求解求解 f(n)=n! 的递归函数为：的递归函数为： long f(int n) if(n=0) return 1; else return n*f(n-1); 求求f(4)=4! 递归表示递归表示: n*f(n-1) 结束条件结束条件 f(0)=0!=14 r13 r22 r21 r20 r2计算计算f(4)= 4*f(4-1) 计算计算f(3)= 3*f(3-1

12、) 计算计算f(2)= 2*f(2-1)计算计算f(1)= 1*f(1-1)计算计算f(0)= 1126244.1.5 4.1.5 栈的应用举例栈的应用举例例一、例一、 数制转换数制转换例二、例二、 括号匹配的检验括号匹配的检验4.2 4.2 表达式求值表达式求值4.3.4.3.递归递归 一个无头结点单链表按逆序输出：一个无头结点单链表按逆序输出： void verout(LNode *L) while L verout(L-next); coutdata; void delete(LinkList &L, ElemType x) / L为无头结点的单链表的头指针为无头结点的单链表的头

13、指针if (L) if (L-data=x) p=L; L=L-next; free(p); delete(L, x); else delete(L-next, x); 1. 实现递归函数，必须利用“栈”。一个递归递归函数必定能改写改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。需要注意的是递归函数递归层次的深度决定所需存储量的大小。2.2. 分析递归算法的工具是分析递归算法的工具是递归树递归树. 从递归树上可以得到递归函数的各种从递归树上可以得到递归函数的各种 相关信息。相关信息。递归递归树的深度树的深度即为递归即为递归 函数的函数的递归深度递归深度； 递归树

14、上的递归树上的结点数目结点数目恰为函数中的恰为函数中的 主要操作主要操作重复次数重复次数 例如例如: : n=3的梵塔算法中主要操作的梵塔算法中主要操作 move的执行次数递归树的执行次数递归树: :move(3, a, b, c)move(2, a, c, b)move(2, b, a, c)move(1, a, b, c)move(1, c, a, b)move(1, b, c, a)move(1, a, b, c)4.3 4.3 栈与递归栈与递归 将所有的实在参数、返回地址等将所有的实在参数、返回地址等信息信息传递给被调函数传递给被调函数保存保存； 为被调函数的局部变量为被调函数的局部变

15、量分配存储区分配存储区 将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。 一个主调函数，在一个主调函数，在运行被调用函运行被调用函数之前数之前，需先完成三项任务：，需先完成三项任务：3.3.若递归树若递归树蜕化蜕化为为单支树或者递归树单支树或者递归树中含有很多中含有很多相同相同的结点，则表明该的结点，则表明该递归函数递归函数不适用不适用。nn-110。计算斐波那契递归函数的递归树中计算斐波那契递归函数的递归树中有很多有很多重复重复出现的结点。出现的结点。F5F4F3F3F2F2F1F1F0F1F0。4. 递归函数中的递归函数中的尾递归尾递归容易容易消除消除。例如：先序遍历二叉树可以改写为：例如：先序遍历二叉树可以改写为： void PreTraverse( BiTree T) While (T) Visit(T-data); PreTraverse(T-lchild); T = T-rchild; / PreTraversevoid delete(LinkList &L, ElemType x) / L为无头结点的单链表的头指针为无头结点的单链表的头指针if (L) if (L-dat