信息学奥赛教学-栈-C版

1、第一章 栈,栈是只能在某一端插入和删除的特殊线性表。 用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。 栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。 一个栈可以用定长为的数组来表示，用一个栈指针TOP指向栈顶。若TOP0，表示栈空，TOP=N时栈满。进栈时TOP加。退栈时TOP减。当TOP0时为下溢。栈指针在运算中永远指向栈顶。,1、进栈（PUSH）算法 若TOP时，则给出溢出信息，作出错处理（进

2、栈前首先检查栈是否已满，满则溢出；不满则作）； TOP+（栈指针加，指向进栈地址）； STOP=X，结束（X为新进栈的元素）； 2、退栈（POP）算法 若TOP0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作)；X=STOP，（退栈后的元素赋给X）；TOP-，结束（栈指针减，指向栈顶）。 进栈、出栈的c+实现过程程序： #define n 100 void push(int s,int *top,int *x) /入栈 if (*top=n) printf(overflow); else (*top)+; s*top=*x; void pop(int s,int

3、*y,int *top) /出栈 if (*top=0) printf(underflow); else *y=s*top; (*top)-; ,对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。 堆栈的数组模拟 十进制数N和其它d进制数的转换是实现计算的基本问题，解决方法很多，下面给出一种算法原理：N=(N / d)dN % d （其中 / 为整除运算，%为求余运算）。 例如：(1348)10(2504)8运算过程如下：,1、填空： (9

4、413)10=( )8=( )16=( )2 2、数制转化程序 #include #include using namespace std; #define size 100 int asize+1,n,d,i=0,j; main() coutn; coutd; do a+i=n%d; n=n/d; while(n!=0); for (j=i;j=1;j-)coutaj; system(pause); return 0; 3、火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。 如果进站的车厢序列为123，则可能的出站车厢序列是什么？ 如果进站的车厢序列为123456，问能否得到13

5、5426和435612的出站序列。,【例1】括号的匹配（表达式的合法性检查） 【问题描述】 假设一个表达式有英文字母（小写）、运算符（+，*，/）和左右小（圆）括号构成，以“”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于255，左圆括号少于20个。 【算法分析】 假设输入的字符串存储在c中（char c256 ）。 我们可以定义一个栈：char smaxn+1; int top; 用它来存放表达式中从左往右的左圆括号（maxn=20）。 算法的思路为：顺序（从左往右）扫描表达式的每个字符ci，若是“（”，则让

6、它进栈；若遇到的是“）”，则让栈顶元素出栈；当栈发生下溢或当表达式处理完毕而栈非空时，都表示不匹配，返回“NO”；否则表示匹配，返回“YES”。,#include #include using namespace std; #define maxn 20 char c256; bool judge(char c256), int top=0,i=0; while (ci!=) if (ci=() top+; if (ci=) if (top0) top-; else return 0; i+; if (top!=0) return 0; /检测栈是否为空。不空则说明有未匹配的括号 else r

7、eturn 1; main() scanf(%s,c); if (judge(c)printf(YES); else printf(NO); system(pause); return 0; ,【例2】编程求一个后缀表达式的值 【问题描述】 从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以作为结束标志。 【算法分析】 后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，

8、直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。 比如，169*(4+3)转换成后缀表达式为： 16943+*，在字符数组A中的形式为：,栈中的变化情况：,运行结果：-47,#include #include #include #include using namespace std; int stack101; char s256; int comp(char s256) int i=0,top=0,x,y; while (i=strlen(s)-2) switch (si) case +:stack-top+=stacktop+1; break; case -:stack-

9、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+; /while return stacktop; ,main() printf(input a string(_over):); gets(s); printf(result=%d,comp(s); system(pause); return 0; ,栈的用途极为广泛，在源程

10、序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈，下面以表达式计算为例子加以说明。 源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句 X4823; (式 11.1) 其正确的计算结果应该是，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为：X122324321 这结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先数法。一般表达式中会遇到操作数、运算符和语句结束符等，以算术运算符为例，对每种运算赋予一个优先数，如： 运算符： 优先数： （语句结束符“；”的优先数为零

11、） 在运算过程中，优先数高的运算符应先进行运算（但遇到括号时，应另作处理）。按这样的规定，对式（11.1）自左向右进行运算时，其计算顺序就被唯一地确定下来了。计算顺序确定后，在对表达式进行编译时，一般设立两个栈，一个称为运算符栈（OPS），另一个称为操作数栈（OVS），以便分别存放表达式中的运算符和操作数。编译程序自左向右扫描表达式直至语句结束，其处理原则是：凡遇到操作数，一律进入操作数栈；当遇到运算符时，则将运算符的优先数与运算符栈中的栈顶元素的优先,数相比较；若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在操作数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入操作

12、数栈，然后继续比较该运算符与栈顶元素的优先数。例如式（11.1）中，当扫描到“”和“”时都要将运算符入栈。接着扫描到“”号， 其优先数小于乘号所以乘号退栈，并执行，将结果再存入操作数栈。再将“”号的优先数与运算符栈的栈顶元素“”号的优先数相比较，两者相等，所以再将加号退栈，进行，结果为，再入栈，接着，由于运算栈已空，所以减号入栈。当扫描到“”时，操作数入栈。当扫描到“；”时，其优先数最低， 所以减号退栈并执行20-3，结果为17并入栈。因已扫描到语句结束符，所以表达式的求值结束，结果为17。,【例3】模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含、运算符，允许含括号），输出算术表

13、达式的值。设输入的表达式串是合法的。 【算法分析】 建立两个栈，一个是操作数栈（number），一个是运算符栈（symbol），根据运算符的优先级对两个栈进行相应的操作。 #include #include #include #include using namespace std; int number101,i=0, p=1; char symbol101,s256, t256; void push() /算符入栈运算 symbol+p=si; void pop() /运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算 switch (symbolp-) case +:numberp+=

14、numberp + 1;break;,case -:numberp-=numberp + 1;break; case *:numberp*=numberp + 1;break; case /:numberp/=numberp + 1;break; bool can() /判断运算符的优先级别,建立标志函数 if (si=+|si=-),while (si=0 ,1、表达式括号匹配(stack.cpp) 【问题描述】 假设一个表达式有英文字母（小写）、运算符（+，*，/）和左右小（圆）括号构成，以“”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否

15、则返回“NO”。表达式长度小于255，左圆括号少于20个。 【输入文件】 输入文件stack.in包括一行数据，即表达式， 【输出文件】 输出文件stack.out包括一行，即“YES” 或“NO”。 【样例输入1】 2*(x+y)/(1-x) 【样例输出1】 YES 【样例输入2】 (25+x)*(a*(a+b+b) 【样例输出2】 NO,【上机练习】,2、括弧匹配检验(check.cpp) 【问题描述】 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（ （）或（ ）等为正确的匹配，（ ）或（ （ ）或 ( ( ) ) ）均为错误的匹配。 现在的问题是，要求检验一个给定表

16、达式中的括弧是否正确匹配？ 输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “OK” ，不匹配就输出“Wrong”。 输入一个字符串：（），输出：OK 【输入格式】 输入仅一行字符（字符个数小于255） 【输出格式】 匹配就输出 “OK” ，不匹配就输出“Wrong”。 【输入样例】check.in （） 【输出样例】check.out Wrong,3、字符串匹配问题 【问题描述】 字符串中只含有括号 (),判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是,(),，例如。输入: () 输出:YES，而输入()， ()都应该输出NO。 【输入

17、格式】strs.in 文件的第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。 【输出格式】strs.out 在输出文件中有N行，每行都是YES或NO。 【输入样例】 5 ()() ()() ()() ()()() ()()() 【输出标例】 YES YES YES YES NO,4、计算(calc.cpp) 【问题描述】 小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“”求出的值就是密码。小明数学学得

18、不好，还需你帮他的忙。(“/”用整数除法) 【输入】 输入文件calc.in共1行，为一个算式。 【输出】 输出文件calc.out共1行，就是密码。 【输入样例】calc.in 1+(3+2)*(72+6*9)/(2) 【输出样例】calc.out 258 【限制】 100%的数据满足：算式长度=30 其中所有数据在231-1的范围内。,5、车厢调度(train.cpp) 【问题描述】 有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n=1000），分别按照顺序编号为1，2，3，n。假定在进入车站前，每节车厢之间都不是连着

19、的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。 负责车厢调度的工作人员需要知道能否使它以a1,a2,an的顺序从B方向驶出，请来判断能否得到指定的车厢顺序。 【输入】train.in 输入文件的第一行为一个整数n，其中n=1000，表示有n节车厢，第二行为n个数字，表示指定的车厢顺序。 【输出】train.out 如果可以得到指定的车厢顺序，则输出一个字符串”YES”，否则输出”NO”（注意要大写，不包含引号）。 【输入样例】 5 5 4 3 2 1 【输出样例