栈及其应用ppt课件

栈及其应用,安庆四中范江文,1,在现实生活中，常常会出现一些特殊的线性结构的情形。例如，我们在洗碗时，总是将最后洗的碗叠在当前一列碗的最上面，而用的时候总是将最上面的碗，也就是最后洗的碗先拿去用。类似的，储蓄罐、瓷坛等只有一个开口的容器存放物品时，都是具有最后放的东西最先倒出来的特性。图1是某个火车站的车厢调度储存室，进站的火车厢只能从左端进入，并从左端出站。这个特殊的调度室也具有一端封闭的特性，因此最后调入的火车厢肯定最先调出。我们将具有先进后出特性的特殊装置，称之为栈。,一、栈的定义从上面的例子，我们可以看出，栈(Stack)是一种特殊的线性表，它的特殊之处在于限定仅能在表的一端进行插入或删除操作。换句话说，栈的操作是按后进先出的顺序处理数据，因此栈又称后进先出表(LastnFirstOut,LIFO)。对于一个栈来说，我们习惯上称它的可操作端为栈顶(Top)，另一端为栈底(Bottom)。设栈S=(a1,a2,，an),a1端为栈底，an端为栈顶，则有:1.插入一个元素an+1后，栈更新为S=(a1,a2,.,an,an+1)2.从栈中删除一个元素后，栈更新为S=(a1,a2,.,an-1)特别的，不含任何元素的栈称为空栈。,2,二、栈的实现1.栈的顺序存储结构我们称用顺序结构存储的栈为顺序栈(array-basedstack)，即:利用连续的存储单元依次记录栈的所有元素。一般来说，使用一维数组B存储栈的所有元素，变量top记录栈的大小，将s1叫作为栈底，stop为栈顶。顺序栈Stack定义如下:TYPEStack=recordtop:integer;栈顶指针s:array1.Maxlengthofelemtype;记录栈中元素的线性表)Procedureinit;初始化栈functionpush(varst:stack;a:elemtype):boolean;压栈，若栈不满，则在栈顶插入元素a,返回true;否则返回falsefunctionpop(stack):elemtype;弹栈，若栈不为空则删除栈顶元素并返回元素值;否则返回NULLprocedurestack.init;Top-0栈置空functionpush(varst:stack;a:elemtype):boolean;Iftop,X,X=),8,算法如下:functionexp-cal:longint;inistack(optr);inisiack(opnd);初始化操作数和操作符栈push(optr,);预处理将压入操作符栈read(w);whilenot(w=)and(gettop(optr)=)DO表达式还没有处理完毕Ifnotwinopthenpush(opnd,w);read(w)elsecasepredede(op(gettop(optr),op(w)of比较optr栈顶元素和当前算符的优先级别:theta:=pop(optr);b:=pop(opnd);a:=pop(opnd);push(opnd,operate(a,theta,b);栈顶算符优先级高，从opnd中取出两个操作数进行计算X:writelnthereisanerrorofexpress!);exit(1);Endreturn(gettop(opnd)endF,9,10,【例5】等价表达式问题描述明明进行了中学之后，学到了代数表达式，有一天，他碰到一道很麻烦的选择题。这个题目的提干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和提干中的表达式等价的。这个题目手算很麻烦，以为明明对计算编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个问题吗？这个选择题中的每个表达式都满足下面的性质:1.表达式只可能包含一个变量a2.表达式中出现的数都是正整数，而且都小于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,11,【输入】输入文件equal.in的第一行给出的是提干中的表达式。第二行是一个整数n(2=n=26),表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A,B,C,D.输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的，输出输出文件equal.out包括一行,这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列、而且之间没有空格。样例输入(a+1)23(a-1)2+4*aa+1+aa2+2*a*1+12+10+a-a样例输出AC数据规模l对于30%的数据，表达式中只可能出现两种运茸符“+”和“-；对于其他的数据，四种运算符在表达式中都可能出现。对于全部的数据，表达式中却可能出现小括号。,12,【分析】这道题目是要我们判断有哪些表达式和给出的表达式本质相同。如果我们将每个表达式进行化简，然后进行相等判断，很难找到同一规则，最后都变成最简表达式，即使有统一规则，程序也比较复杂。,注意到数学里面的恒等式的性质，如果两个表达式相等，那么对a取任意符合表达式条件的数值，两个表达式的计算结果一致。因此我们可以用抽样取值法，也就是对表达式中的变量a随机取若干个值代入若两个表达式的计算结果一致，则认为两个表达式等价。当然，抽样调查并不能保证所有，但如果抽样的数值比较好的话，从概率上分析，出错率会很低。算法流程如下:1.随机取20-30个a值2.将每个a的取值代入每个表达式,计算出每个表达式的结果.3.如果对每个取值,两个表达式的结果相等则认为它们是等价的表达式，否则不是。4.输出结果.这里需要注意一些小问题，在随机取值时,尽量取随机素数。另外,表达式可以出现连续的幂运算,这样计算的结果会很大。为了简化运算,我们可以将每次运算的中间结果对某大素数取余即可。需要注意的是幂运算的优先规则是从左到右运算.比如：A102=a20，而不是a100.,13,练习,1、括弧匹配检验:假设表达式中允许包含两种括号即圆括号和方括号，其嵌套的顺序随意，如()或()等为正确的匹配，()或()或()均为错误的匹配。现在的问题是，要求检验一个给定表达式中的括弧是否正确匹