数据结构栈.ppt

《数据结构栈.ppt》由会员分享，可在线阅读，更多相关《数据结构栈.ppt（30页珍藏版）》请在优知文库上搜索。

1、顺序栈的数据结构表示顺序栈的数据结构表示 #define maxsize 栈的大小栈的大小; struct stack1 int astack_size; int t; stack1 s;3526例1：1,2,3,4,5 例2：5,4,3,2,1 例3：3,2,4,5,1 例4：3,1,4,5,2 C A B 入栈：1,2,3,4,5 no; yes; yes; yes; 设设f(n)表示有表示有n节车厢的出站的方法数节车厢的出站的方法数 那么那么,第第1节车厢显然有进栈和不进栈两种方法节车厢显然有进栈和不进栈两种方法. 不进栈的方法为不进栈的方法为f(n-1) 进栈的方法数进栈的方法数,可以

2、归结为元素可以归结为元素1第第i次出栈的所有可能性。次出栈的所有可能性。 元素元素1排列在第排列在第i个位置，那么将整个序列分裂为个位置，那么将整个序列分裂为2i，1，i+1n 两个部分。显然方法数为两个部分之积，如下：两个部分。显然方法数为两个部分之积，如下：nfinfif21)0(),(*) 1(其中nfinfifnf21)0(),(*) 1()(其中 char a9= ,(,),; cinst;x=true;k=0; len=st.length(); for(j=0;jlen;j+) for(w=1;w=8;w+) if(stj=aw)break; if(ww)coutNOendl;x=

3、false;break; else k+;ck=w;/入栈入栈 else if(ck+w!=9)coutNOendl;x=false;break; else k-;/出栈出栈 if(x=true) if(k=0)coutYESendl; else coutNOendl;Description：由键盘输入一个算术表达式，该表达式由数字，加（+）、减（-）、乘（*）、求商（/）运算符及小括号组成。 例如：6+8*（5-5*（26-1）/2+7） 请编一程序，若输入的表达式的值。 Input：输入一个算术表达式（表达式的长度小于255，输入数字的值 int compare_PRI(char a,ch

4、ar b) /优先级比较,a:符号栈顶,b:将入栈符号 if(a=(&b=)return 0; /返回相等信息,则出栈,b丢弃左右括号相遇则两者消失 if(a=() return -1; /返回-1,则b入栈(优先级低于其它符号 if(b=)|a=/|b=+|b=-|a=b) return 1; /返回1,则用栈项a计算将处理的)低于其它符号,ab相等则b低 return -1;以以3*(7-2)为例为例,操作过程如下操作过程如下,构造操作符和操作数栈构造操作符和操作数栈int cal(int a,char mark,int b)/计算函数 switch (mark) case +: retu

5、rn a+b; case -: return a-b; case *: return a*b; case /: return a/b; int main() int temp,num250,numtop=-1,marktop=0,k; char mark250; string s; cins; mark0=(; s+=); while(ks.length() if(sk=0)/若当前要处理字符是数字若当前要处理字符是数字 temp=0;/将连续的数字字符转换成数压入数字栈将连续的数字字符转换成数压入数字栈 while(sk=0&ks.length()temp=temp*10+sk+-0; nu

6、m+numtop=temp; continue; switch(compare_PRI(markmarktop,sk)/若不是数字则是符号，根据当前符号栈与当前若不是数字则是符号，根据当前符号栈与当前符号优先级比较结果处理符号优先级比较结果处理 case 1:/当前符号低，则用栈顶符号计算，并将符号栈顶出栈，数字栈出两个进一个当前符号低，则用栈顶符号计算，并将符号栈顶出栈，数字栈出两个进一个 numnumtop-1=cal(numnumtop-1,markmarktop,numnumtop);/计算计算 numtop-;/修改数字栈顶修改数字栈顶 marktop-;/修改符号栈顶修改符号栈顶

7、break; case 0: marktop-;k+;break;/相等，则符号栈出栈，栈顶减相等，则符号栈出栈，栈顶减1，扫描下一个字符，扫描下一个字符 case -1: mark+marktop=sk;k+;/优先级高则当前符号入栈，扫描下一个字符优先级高则当前符号入栈，扫描下一个字符 coutnum0st; int len=strlen(st); couttree(st,0,len-1); return 0;int poskh(char st,int right ,int p) /寻找字符串left到right区间内与p位置的(匹配的)的位置 int t=1;/sp是一个( p+;/从下

8、一个位置开始找 for(int i=p;i=left;i-) /从右到左扫描,主要因为减号和除号如3-2-1 应是(3-2)-1 而不是3-(2-1). if(sti=A&sti=a&sti=z) continue; if(sti=() t-;continue; if(sti=) t+;continue; if(sti=+|sti=-)&t=0) return i; if(t=0&k=0) k=i;/返回最右边的*、/号 return k; int isnum(char st,int left,int right)/判断字符串left到right区间是否是一个数，是则返回数值，否则返回1 in

9、t data=0; for(int i=left;i=0&sti=9)return -1;/不是一个数data=data*10+sti-0; return data;int cal(int a,char mark,int b)/计算函数 switch (mark) case +: return a+b; case -: return a-b; case *: return a*b; case /: return a/b; int tree(char st,int left,int right) int tmp,l1,l2,p; tmp=isnum(st,left,right); if (tmp

10、!=-1)return tmp;/返回值 if(stleft=(&poskh(st,right,left)=right)tree(st,left+1,right-1);return; /去外括号 p=findlow(st,left,right); l1=tree(st,left,p-1);/左面 l2=tree(st,p+1,right);/右面 return cal(l1,stp,l2);等价表达式等价表达式明明进了中学之后，学到了代数表达式。有一天，明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个

11、代数表达式，然后列出了若干选首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达是判断选项中哪些代数表达式是和题干中的表达式等价的。式等价的。这个题目手算很麻烦，因为明明对计算机编程很这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？个问题。假设你是明明，能完成这个任务吗？这个选择题中的每个表达式都满足下面的性质：这个选择题中的每个表达式都满足下面的性质：1表达式只

12、可能包含一个变量表达式只可能包含一个变量a。2表达式中出现的数都是正整数，而且都小于表达式中出现的数都是正整数，而且都小于10000。3表达式中可以包括四种运算表达式中可以包括四种运算+（加），（加），-（减），（减），*（乘），（乘），（乘幂），以及小括号（乘幂），以及小括号(，)。小括号的优先级最高，其次是小括号的优先级最高，其次是，然后是，然后是*，最后，最后是是+和和-。+和和-的优先级是相同的。相同优先的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符级的运算从左到右进行。（注意：运算符+，-，*，以及小括号以及小括号(，)都是英文字符）都是英文字符）4幂指数只可能是幂指

13、数只可能是1到到10之间的正整数（包括之间的正整数（包括1和和10）。）。5 表达式内部，头部或者尾部都可能有一些多余的空格。表达式内部，头部或者尾部都可能有一些多余的空格。下面是一些合理的表达式的例子：下面是一些合理的表达式的例子：(a1) 2)3，a*a+a-a，(a+a)，9999+(a-a)*a，1 + (a -1)3，1109【输入文件输入文件】输入文件输入文件equal.in的第一行给出的是题干中的表达式。第二行是一个整数的第一行给出的是题干中的表达式。第二行是一个整数n（2 = n = 26），表示选项的个数。后面），表示选项的个数。后面n行，每行包括一个选项中的表达式。这行，每

14、行包括一个选项中的表达式。这n个选项的标号分别是个选项的标号分别是A，B，C，D输入中的表达式，的长度都不超过输入中的表达式，的长度都不超过50个个字符，而且保证选项中总有表达式和题干中的表达式是等价的。字符，而且保证选项中总有表达式和题干中的表达式是等价的。【输出文件输出文件】输出文件输出文件equal.out包括一行，这一行包括一系列选项的标号，表示哪些选项包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。空格。【样例输入样例输入】( a + 1) 23

15、(a-1)2+4*aa + 1+ aa2 + 2 * a * 1 + 12 + 10 -10 +a -a【样例输出样例输出】AC【数据规模数据规模】对于对于30%的数据，表达式中只可能出现两种运算符的数据，表达式中只可能出现两种运算符+和和-；对于其它的数据，四种运算符对于其它的数据，四种运算符+，-，*，在表达式中都可能出现。在表达式中都可能出现。对于全部的数据，表达式中都可能出现小括号对于全部的数据，表达式中都可能出现小括号(和和)。 这道题目是要我们判断有哪些表达式和给出的表达式本质相这道题目是要我们判断有哪些表达式和给出的表达式本质相同。最简单的想法是将每个表达式进行化简，但是通过仔细

16、同。最简单的想法是将每个表达式进行化简，但是通过仔细的读题，可以发现这是不可能的。因为这样的话涉及到多项的读题，可以发现这是不可能的。因为这样的话涉及到多项式的加法、减法、乘法、幂运算。这在时间有限的考场上是式的加法、减法、乘法、幂运算。这在时间有限的考场上是几乎不可能写出来的。而且，也非常难以写对，时间效率也几乎不可能写出来的。而且，也非常难以写对，时间效率也很难保证。很难保证。 注意到数学里面的恒等式的性质，恒等式中代入任何值结果注意到数学里面的恒等式的性质，恒等式中代入任何值结果都应该是一样的。而非恒等的式子，结果相等的概率是非常都应该是一样的。而非恒等的式子，结果相等的概率是非常非常小的。那么我们有了一种新的思路，就是每次随机一个非常小的。那么我们有了一种新的思路，就是每次随机一个a的取值，然后对于所有的表达式计算一次结果。看有多少个的取值，然后对于所有的表达式计算一次结果。看有多少个和原来的表达式计算出来的结果是一样的。如果只取一个和原来的表达式计算出来的结果是一样的。如果只取一个a值值进行计算，仍然有一定的概率出错。那么我们多随机几个数，进行计算，仍然有一定的概率出错。那么