第4章 2.栈的应用

《第4章 2.栈的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.2栈的应用举例例一、数制转换例二、括号匹配的检验例三、背包问题例四、表达式求值例五、迷宫求解例六、实现递归例一、数制转换算法基于原理：N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8，其运算过程如下(除8取余法)：计算顺序输出顺序1348888816842102502商余数voidconversion(){InitStack(S);scanf("%d",N);while(N){Push(S,N%8);//余数入栈N=N/8;//商}while(!StackEmpty(S)){Pop(S,e);prin

2、tf("%d",e);}}//conversion例二、括号匹配的检验假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或(()])均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;例如：考虑下列括号序列：[([][])]12345678到来的是“不速之客”;直到结束，也没有到来所“期待”的括弧;算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元

3、素比较，若相匹配，则“左括弧出栈”否则表明不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余Statusmatching(string&exp){intstate=1;while(i<=Length(exp)&&state){switchofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case”)”:{if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}else{state=0;}break;}……}if(Stac

4、kEmpty(S)&&state)returnOK;…...例三背包问题(P70)假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使wi1+wi2+…+wik=T，要求找出所有满足上述条件的解。例如：当T=10，各件体积为{1，8，4，3，5，2}时，可找到下列4组解：(1，4，3，2)、(1，4，5)、(8，2)和(3，5，2)。使用算法：回溯法。使用数据结构：栈。读懂P70图4.4：各件下标：{0，1，2，3，4，5}对应体积：{1，8，4，3，5，2}图

5、中所示为下标，需与对应的体积相印证。0,10,11,80,12,43,35,2物品体积:(1,8,4,3,5,2)。背包总体积10。0,1,2,3,4,50,12,44,50,12,45,20,13,34,50,13,35,20,14,55,20,14,55,2编号体积0,85,22,43,35,22,44,52,45,23,34,55,23,35,24,55,25,2限于二元运算符的表达式定义:表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量

6、表达式简单变量::=标识符

7、无符号整数例四、表达式求值表达式的三种

8、标识方法：设Exp=S1+OP+S2则称OP+S1+S2为前缀表示法S1+OP+S2为中缀表示法S1+S2+OP为后缀表示法例如:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算

9、符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;如何从后缀式求值？先找运算符，再找操作数例如：abcde/f+abd/ec-d/e(c-d/e)f如何从原表达式求得后缀式？每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中,优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f从原表达式求得后缀式的规律为：1)设立暂存运算符的栈;2)设表达式的结束符为“#”,予设运算符栈的栈底为“#”3)若当前字符是操作数，则直接发

10、送给后缀式;4)若当前运算符的优先数高于栈顶运算符，则进栈;5)否则，退出栈顶运算符发送给后缀式;6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：voidtransform(charsuffix