第一章 栈

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

1、进栈（PUSH）算法 ①若TOP≥ｎ时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）； ②TOP++（栈指针加１，指向进栈地址）； ③S[TOP]=X，结束（X为新进栈的元素）； 2、退栈（POP）算法 　　①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)； 　　②X=S[TOP]，（退栈后的元素赋给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 *y,int *top) //出栈 if (*top==0) printf("underflow"); else { *y=s[*top]; (*top)--; }

对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。 堆栈的数组模拟 十进制数N和其它d进制数的转换是实现计算的基本问题，解决方法很多，下面给出一种算法原理：N=(N / d)×d＋N % d （其中 / 为整除运算，%为求余运算）。 例如：(1348)10＝(2504)8运算过程如下： N N / 8 N % 8 9413   N N / 8 N % 8 1348 168 4 21 2 5

1、填空： (9413)10=( )8=( )16=( )2 2、数制转化程序 #include<cstdlib> #include<iostream> using namespace std; #define size 100 int a[size+1],n,d,i=0,j; main() { cout<<"Please enter a number(N) base 10:"; cin>>n; cout<<"please enter a number(d):"; cin>>d; do{ a[++i]=n%d; n=n/d; }while(n!=0); for (j=i;j>=1;j--)cout<<a[j]; return 0; } 3、火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。 ①如果进站的车厢序列为123，则可能的出站车厢序列是什么？ ②如果进站的车厢序列为123456，问能否得到135426和435612的出站序列。

假设输入的字符串存储在c中（char c[256] ）。 我们可以定义一个栈：char s[maxn+1]; 【例1】括号的匹配（表达式的合法性检查） 【问题描述】 假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于255，左圆括号少于20个。 【算法分析】 假设输入的字符串存储在c中（char c[256] ）。 我们可以定义一个栈：char s[maxn+1]; int top; 用它来存放表达式中从左往右的左圆括号（maxn=20）。 算法的思路为：顺序（从左往右）扫描表达式的每个字符c[i]，若是“（”，则让它进栈；若遇到的是“）”，则让栈顶元素出栈；当栈发生下溢或当表达式处理完毕而栈非空时，都表示不匹配，返回“NO”；否则表示匹配，返回“YES”。 #include<cstdio> #include<cstdlib> using namespace std; #define maxn 20 char c[256]; bool judge(char c[256])

{ int top=0,i=0; while (c[i]!='@') if (c[i]=='(') top++; if (c[i]==')') if (top>0) top--; else return 0; } i++; if (top!=0) return 0; //检测栈是否为空。不空则说明有未匹配的括号 else return 1; main() scanf("%s",c); if (judge(c))printf("YES"); else printf("NO"); return 0;

【例2】编程求一个后缀表达式的值 【问题描述】 从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。 【算法分析】 后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。 比如，16–9*(4+3)转换成后缀表达式为： 16□9□4□3□+*–，在字符数组A中的形式为： 栈中的变化情况： 运行结果：-47

#include<cstdio> #include<cstdlib> #include<string> #include<cstring> using namespace std; int stack[101]; char s[256]; int comp(char s[256]) { int i=0,top=0,x,y; while (i<=strlen(s)-2) switch (s[i]) case '+':stack[--top]+=stack[top+1]; break; case '-':stack[--top]-=stack[top+1]; break; case '*':stack[--top]*=stack[top+1]; break; case '/':stack[--top]/=stack[top+1]; break; default:x=0; while (s[i]!=' ') x=x*10+s[i++]-'0'; stack[++top]=x; break; } i++; } //while return stack[top];

main() { printf("input a string(@_over):"); gets(s); printf("result=%d",comp(s)); return 0; }

栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈，下面以表达式计算为例子加以说明。 　　源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句 X＝4＋8×2－3; (式 11.1) 其正确的计算结果应该是１７，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为：X＝12×2－3＝24－3＝21 这结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先数法。 　　一般表达式中会遇到操作数、运算符和语句结束符等，以算术运算符为例，对每种运算赋予一个优先数，如： 运算符：×　÷　＋　－　 优先数：２　２　１　１ （语句结束符“；”的优先数为零） 在运算过程中，优先数高的运算符应先进行运算（但遇到括号时，应另作处理）。按这样的规定，对式（11.1）自左向右进行运算时，其计算顺序就被唯一地确定下来了。计算顺序确定后，在对表达式进行编译时，一般设立两个栈，一个称为运算符栈（OPS），另一个称为操作数栈（OVS），以便分别存放表达式中的运算符和操作数。编译程序自左向右扫描表达式直至语句结束，其处理原则是： 　　①凡遇到操作数，一律进入操作数栈； 　　②当遇到运算符时，则将运算符的优先数与运算符栈中的栈顶元素的优先

数相比较；若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在操作数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入操作数栈，然后继续比较该运算符与栈顶元素的优先数。 　　例如式（11.1）中，当扫描到“＋”和“×”时都要将运算符入栈。接着扫描到“－”号， 其优先数小于乘号所以乘号退栈，并执行８×２，将结果１６再存入操作数栈。再将“－”号的优先数与运算符栈的栈顶元素“＋”号的优先数相比较，两者相等，所以再将加号退栈，进行４＋１６，结果为２０，再入栈，接着，由于运算栈已空，所以减号入栈。当扫描到“３”时，操作数入栈。当扫描到“；”时，其优先数最低， 所以减号退栈并执行20-3，结果为17并入栈。因已扫描到语句结束符，所以表达式的求值结束，结果为17。

【例3】模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含＋、－、×、÷运算符，允许含括号），输出算术表达式的值。设输入的表达式串是合法的。 【算法分析】 建立两个栈，一个是操作数栈（number），一个是运算符栈（symbol），根据运算符的优先级对两个栈进行相应的操作。 #include<cstdio> #include<cstdlib> #include<string> #include<cstring> using namespace std; int number[101],i=0, p=1; char symbol[101],s[256], t[256]; void push() //算符入栈运算 { symbol[++p]=s[i]; } void pop() //运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算 switch (symbol[p--]) case '+':number[p]+=number[p + 1];break;

case '-':number[p]-=number[p + 1];break; } bool can() //判断运算符的优先级别,建立标志函数 { if ((s[i]=='+'||s[i]=='-')&&symbol[p]!='(') return 1; if ((s[i]=='*'||s[i]=='/')&&(symbol[p]=='*'||symbol[p]=='/'))return 1; return 0; main() printf("String :");gets(s); s[strlen(s)]=')';symbol[p]='('; while (i<strlen(s)) while (s[i]=='(') //左括号处理 push();i++; int x=0;

while (s[i]>='0'&&s[i]<='9') //取数入操作数栈 x=x*10+s[i++]-'0'; number[p]=x; do { if (s[i]==')') //右括号处理 while (symbol[p]!='(') pop(); number[--p]=number[p + 1]; } else { //根据标志函数值作运算符入栈或出栈运算处理 while (can()) pop(); push(); i++; }while (i<strlen(s)&&s[i-1]==')'); printf("Result=%d", number[0]); return 0;

【上机练习】 1、表达式括号匹配(stack.cpp) 【问题描述】 假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“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) 【问题描述】 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［ ］（））或［（［ ］［ ］）］等为正确的匹配，［（ ]）或（［ ］（ ）或 ( ( ) ) ）均为错误的匹配。 　　现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？ 输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “OK” ，不匹配就输出“Wrong”。 输入一个字符串：［（［］［］）］，输出：OK 【输入格式】 输入仅一行字符（字符个数小于255） 【输出格式】 匹配就输出 “OK” ，不匹配就输出“Wrong”。 【输入样例】check.in ［（］） 【输出样例】check.out Wrong

3、字符串匹配问题 【问题描述】 字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])， ([])都应该输出NO。 【输入格式】strs.in 文件的第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。 【输出格式】strs.out 在输出文件中有N行，每行都是YES或NO。 【输入样例】 5 {}{}<><>()()[][] {{}}{{}}<<>><<>>(())(())[[]][[]] {<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]] ><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]] 【输出标例】 YES NO

4、计算(calc.cpp) 【问题描述】 小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法) 【输入】 输入文件calc.in共1行，为一个算式。 【输出】 输出文件calc.out共1行，就是密码。 【输入样例】calc.in 1+(3+2)*(7^2+6*9)/(2) 【输出样例】calc.out 258 【限制】 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”（注意要大写，不包含引号）。 【输入样例】 5 5 4 3 2 1 【输出样例】 YES

6、中缀表达式值(Expr.cpp) 【问题描述】 输入一个中缀表达式（由0-9组成的运算数、加+减—乘*除/四种运算符、左右小括号组成。注意“—”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。 注意：必须用栈操作，不能直接输出表达式的值。如果再考虑是实数运算呢？ 【输入文件】Expr.in 输入文件的第一行为一个以@结束的字符串。 【输出文件】Expr.out 如果表达式不合法，请输出“NO”，要求大写。 如果表达式合法，请输出计算结果。 【输入样例】 1＋2×8―9 【输出样例】 8