栈及其应用.ppt

栈及其应用安庆四中 范江文.在现实生活中，常常会出现一些特殊的线性结构的情形。例如，我们在洗碗时，总是将最后洗的碗叠在当前一列碗的最上面，而用的时候总是将最上面的碗，也就是最后洗的碗先拿去用。类似的，储蓄罐、瓷坛等只有一个开口的容器存放物品时，都是具有最后放的东西最先倒出来的特性。图1是某个火车站的车厢调度储存室，进站的火车厢只能从左端进入，并从左端出站。这个特殊的调度室也具有一端封闭的特性，因此最后调入的火车厢肯定最先调出。我们将具有先进后出特性的特殊装置，称之为栈。一、栈的定义一、栈的定义 从上面的例子，我们可以看出，栈(Stack)是一种特殊的线性表，它的特殊之处在于限定仅能在表的一端进行插入或删除操作。换句话说，栈的操作是按后进先出的顺序处理数据，因此栈又称后进先出表(Lastn First Out,LIFO)。对于一个栈来说，我们习惯上称它的可操作端为栈顶(Top)，另一端为栈底(Bottom)。设栈S=(a1,a2,，an),a1端为栈底，an端为栈顶，则有:1.插入一个元素an+1后，栈更新为S=(a1,a2,.,an,an+1)2.从栈中删除一个元素后，栈更新为S=(a1,a2,.,an-1)特别的，不含任何元素的栈称为空栈。.二、栈的实现二、栈的实现1.1.栈的顺序存储结构栈的顺序存储结构 我们称用顺序结构存储的栈为顺序栈(array-based stack)，即:利用连续的存储单元依次记录栈的所有元素。一般来说，使用一维数组B存储栈的所有元素，变量top记录栈的大小，将s1叫作为栈底，stop为栈顶。顺序栈Stack定义如下:TYPE Stack=record top:integer;栈顶指针 s:array 1.Maxlength of elemtype;记录栈中元素的线性表)Procedure init;初始化栈function push(var st:stack;a:elemtype):boolean;压栈，若栈不满，则在栈顶插入元素a,返回 true;否则返回falsefunction pop(stack):elemtype;弹栈，若栈不为空则删除栈顶元素并返回元素值;否则返回NULLprocedure stack.init;Top-0 栈置空function push(var st:stack;a:elemtype):boolean;If topmaxlength then begin inc(st.top);st.sst.top:=a;end else push:=fasle;function pop():elemtype;If st.top=0 then 栈为空 else pop:=st.sst.top;dec(st.top);.三、栈的应用三、栈的应用（一）（一）堆栈具有先进后出(后进先出)的特性，凡是具有这种特性的题目我们都可以用堆栈来试一试。例1编制一个满足下列要求的程序:对于输人的任意一个非负十进制整数，打印输出与其等值的八进制数。例如:(1348)10=(2504)8例2括弧匹配检验:假设表达式中允许包含两种括号即圆括号和方括号，其嵌套的顺序随意，如()或()等为正确的匹配，()或()或()均为错误的匹配。现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配?这八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序，一般来说应从高位到低位，这恰好和计算过程相反。所以，堆栈的用武之地出来了。具体做法就是把求到的数位先依次入栈，然后再依次出栈。看是否匹配，具体是看每个左括号是否有一个右括号跟它匹配。而且括号可以嵌套，要检查外层括号是否匹配，必须先检查内层的括号是否匹配，也就是先遇到的左括号后处理，这时，堆栈又有了用武之地。具体做法是遇到左括号就入栈，遇到右括号就出栈并判断是否匹配。当括号串全部处理完毕，而且堆栈为空，则是合法的，其他情况都是非法的。.例3给定N(N,X,X=).算法如下算法如下:function exp-cal:longint;inistack(optr);inisiack(opnd);初始化操作数和操作符栈push(optr,);预处理将压入操作符栈read(w);while not(w=)and(gettop(optr)=)DO表达式还没有处理完毕If not w in op then push(opnd,w);read(w)else case predede(op(gettop(optr),op(w)of比较optr栈顶元素和当前算符的优先级别:theta:=pop(optr);b:=pop(opnd);a:=pop(opnd);push(opnd,operate(a,theta,b);栈顶算符优先级高，从opnd中取出两个操作数进行计算X:writeln there is an error of express!);exit(1);Endreturn(gettop(opnd)endF.【例【例5】等价表达式】等价表达式问题描述问题描述 明明进行了中学之后，学到了代数表达式，有一天，他碰到一道很麻烦的选择题。这个题目的提干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和提干中的表达式等价的。这个题目手算很麻烦，以为明明对计算编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个问题吗？这个选择题中的每个表达式都满足下面的性质:1.表达式只可能包含一个变量a 2.表达式中出现的数都是正整数，而且都小于10000。3.表达式中可以包括四种运算+(加)，一(减)，*(乘),(乘幂)，以及小括号(,)。小括号的优先级最高，其次是,然后是*,最后是+和-。+和-的优先级是相同的，相同优先级的运算从左到右进行。(注意:运算符+-*都是英文字符）4.幂指数只可能是1 到10之间的正整数（包括1和10）5.表达式内部、头部或者尾部都可能有一些多余的空格。下面是一些合理的表达式的例子:（(a1)2）3,a*a+a-a,(a+a),9999+(a-a)*a,1+(a-a)3,1109.【输入】输入文件equal.in的第一行给出的是提干中的表达式。第二行是一个整数n(2=n=26),表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A,B,C,D.输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的，输出输出文件equal.out 包括一行,这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列、而且之间没有空格。样例输入(a+1)2 3 (a-1)2+4*a a+1+a a2+2*a*1+12+10+a-a样例输出 AC数据规模l 对于30%的数据，表达式中只可能出现两种运茸符“+”和“-；对于其他的数据，四种运算符在表达式中都可能出现。对于全部的数据，表达式中却可能出现小括号。.【分析】这道题目是要我们判断有哪些表达式和给出的表达式本质相同。如果我们将每个表达式进行化简，然后进行相等判断，很难找到同一规则，最后都变成最简表达式，即使有统一规则，程序也比较复杂。注意到数学里面的恒等式的性质，如果两个表达式相等，那么对a取任意符合表达式条件的数值，两个表达式的计算结果一致。因此我们可以用抽样取值法，也就是对表达式中的变量a随机取若干个值代入若两个表达式的计算结果一致，则认为两个表达式等价。当然，抽样调查并不能保证所有，但如果抽样的数值比较好的话，从概率上分析，出错率会很低。算法流程如下:1.随机取20-30 个a 值2.将每个a的取值代入每个表达式,计算出每个表达式的结果.3.如果对每个取值,两个表达式的结果相等则认为它们是等价的表达式，否则不是。4.输出结果.这里需要注意一些小问题，在随机取值时,尽量取随机素数。另外,表达式可以出现连续的幂运算,这样计算的结果会很大。为了简化运算,我们可以将每次运算的中间结果对某大素数取余即可。需要注意的是幂运算的优先规则是从左到右运算.比如：A102=a20，而不是a100.练练 习习1、括弧匹配检验:假设表达式中允许包含两种括号即圆括号和方括号，其嵌套的顺序随意，如()或()等为正确的匹配，()或()或()均为错误的匹配。现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配?2、例3给定N(N=100000)个数，找出每个数后面第一个比它大的数的编号。没有输出0。input:3 2 6 1 1 2output:3 3 0 6 6 03、利用栈实现算术表达式求值利用栈实现算术表达式求值编写一个包含有“+”、“-”、“，”、“/”、“(”、“)”等运算符的表达式，计算出该表达式的数值。4、等价表达式等价表达式.