第1章 栈(C++版).ppt

第一章栈,栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）。一个栈可以用定长为的数组来表示，用一个栈指针TOP指向栈顶。若TOP0，表示栈空，TOP=N时栈满。进栈时TOP加。退栈时TOP减。当TOPn;coutd;doa+i=n%d;n=n/d;while(n!=0);for(j=i;j=1;j-)cout0)top-;elsereturn0;i+;if(top!=0)return0;/检测栈是否为空。不空则说明有未匹配的括号elsereturn1;main()scanf(%s,c);if(judge(c)printf(YES);elseprintf(NO);return0;,【例2】编程求一个后缀表达式的值【问题描述】从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以作为结束标志。【算法分析】后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。比如，169*(4+3)转换成后缀表达式为：16943+*，在字符数组A中的形式为：,栈中的变化情况：,运行结果：-47,#include#include#include#includeusingnamespacestd;intstack101;chars256;intcomp(chars256)inti=0,top=0,x,y;while(i=strlen(s)-2)switch(si)case+:stack-top+=stacktop+1;break;case-:stack-top-=stacktop+1;break;case*:stack-top*=stacktop+1;break;case/:stack-top/=stacktop+1;break;default:x=0;while(si!=)x=x*10+si+-0;stack+top=x;break;i+;/whilereturnstacktop;,main()printf(inputastring(_over):);gets(s);printf(result=%d,comp(s);return0;,【例3】车厢调度【问题描述】有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（nn;for(inti=1;iai;top=0;for(inti=1,cur=1;i=n;+i)/cur为当前要从A方向驶入的车厢号while(cur=ai)stack+top=cur+;if(stacktop=ai)-top;elsecoutNOendl;return0;coutYES()()()()()()()()()()【输出标例】YESYESYESYESNO,4、计算(calc.cpp)【问题描述】小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“”求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)【输入】输入文件calc.in共1行，为一个算式。【输出】输出文件calc.out共1行，就是密码。【输入样例】calc.in1+(3+2)*(72+6*9)/(2)【输出样例】calc.out258【限制】100%的数据满足：算式长度=30其中所有数据在231-1的范围内。,5、车厢调度(train.cpp)【问题描述】有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n=1000），分别按照顺序编号为1，2，3，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。负责车厢调度的工作人员需要知道能否使它以a1,a2,an的顺序从B方向驶出，请来判断能否得到指定的车厢顺序。【输入】train.in输入文件的第一行为一个整数n，其中n=1000，表示有n节车厢，第二行为n个数字，表示指定的车厢顺序。【输出】train.out如果可以得到指定的车厢顺序，则输出一个字符串”YES”，否则输出”NO”（注意要大写，不包含引号）。【输入样例】554321【输出样例】YES,6、中缀表达式值(Expr.cpp)【问题描述】输入一个中缀表达式（由0-9组成的运算数、加+减乘*除/四种运算符、左右小括号组成。注意“”也可作为负数的标志，表达式以“”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。注意：必须用栈操作，不能直接输出表