通辽建设工程网站,wordpress价格,搜索引擎排名优化是什么意思,wordpress空间免费目录
1.1栈的基本概念
1.1.1栈的定义
1.1.2栈的基本操作 1.2栈的顺序存储结构
1.2.1构造原理 1.2.2基本算法
1.3栈的链式存储结构
1.3.1构造原理
1.3.2基本算法
2.1队列的基本概念
2.1.1队列的定义 2.1.2队列的基本运算 2.2队列的顺序存储结构
2.2.1构造原理
2.2.1基…目录
1.1栈的基本概念
1.1.1栈的定义
1.1.2栈的基本操作 1.2栈的顺序存储结构
1.2.1构造原理 1.2.2基本算法
1.3栈的链式存储结构
1.3.1构造原理
1.3.2基本算法
2.1队列的基本概念
2.1.1队列的定义 2.1.2队列的基本运算 2.2队列的顺序存储结构
2.2.1构造原理
2.2.1基本算法 2.3队列的链式存储结构
2.3.1构造原理 2.3.2基本算法
3.1例题
判断题
单选题
函数题
另类堆栈
用顺序栈实现将非负的十进制数转换为指定的进制数 简单表达式求值
另类循环队列
编程题 括号匹配
栈操作的合法性 1.1栈的基本概念
1.1.1栈的定义
栈限定仅在表尾进行插入操作和删除操作的线性表
栈顶表尾允许操作的一端
栈底表头不允许操作
空栈当表没有元素时 先进后出 FILOFrist In Last Out
1.1.2栈的基本操作
初始化栈将栈S置为一个空栈不含任何元素
入栈 将元素插入到栈中又称为压栈或进栈
出栈删除栈顶元素又称为退栈
取栈顶元素取出栈顶元素
判断栈是否为空若为空返回真否则返回假
判断栈是否为满若为空返回真否则返回假 1.2栈的顺序存储结构
1.2.1构造原理
描述栈的顺序储存结构最简单的方法是利用一维数组data[0…M-1]来表示同时定义一个整型变量不妨取名top给出栈顶元素的位置。 #define M (10005) typedef char ElemType; typedef struct{ ElemType data[M] int top; //初始top-1 }SqStack; 1.2.2基本算法
初始化栈
void init(SqStack *s){s-top-1;
}
测试栈是否为空
int isEmpty(SqStack s){return s.top-1;
}
测试栈是否已满
int isFull(SqStack s){return s.topM-1;
}
入栈
int push(SqStack *s,ElemType item){if(isFull(*s)) return 0;else{s-data[(s-top)]item;return 1;}
}
出栈
int pop(SqStack *s,ElemType *item){if(isEmpty(*s)) return 0;else{*items-data[(s-top)--];return 1;}
}
1.3栈的链式存储结构
1.3.1构造原理 typedef struct node{ ElemType data; struct node *next; }SNode,*LinkStack; LinkStack top; //栈顶指针 1.3.2基本算法
栈初始化
void init(LinkStack *top){*topNULL;
} 测试栈是否为空
int isEmpty(LinkStack top){return topNULL;
}
入栈
int push(LinkStack *top,ElemType item){LinkStack p(LinkStack)malloc(sizeof(SNode));if(pNULL) return 0;else{p-dataitem;p-next*top;*topp;return 1;}
}
出栈
int pop(LinkStack *top,ELemType *item){LinkStack p;if(isEmpty(*top)) return 0;else{p*top;*item(*top)-data;*top(*top)-next;free(p);return 1;}
}
2.1队列的基本概念
2.1.1队列的定义
队列简称队。是一种只允许在表的一端进行插入操作而在表的另一端进行删除操作的线性表。允许插入的一段称为队尾队尾元素的位置由rear指出允许删除的一端称为队头队头元素的位置由front指出。 先进先出 FIFOFrist In First Out 2.1.2队列的基本运算
初始化队列将队列q设置成一个空队列
入队列将元素x插入到队尾中也称“进队”“插入”
入队列将队列q的队头元素删除并用x返回其值也称“退队”“删除”
取队头元素得到队列q队头元素之值并用x返回其值
判队空判断队列q是否为空若空返回1否则返回0 2.2队列的顺序存储结构
2.2.1构造原理
在实际程序设计过程中通常借助一个一维数组data[0…M-1]来描述队列的顺序储存结构同时设置两个变量front与rear分别指出当前队头元素与队尾元素的位置。 #define M (10005) typedef struct{ ElemType data[M]; int front,rear; }SqQueue; 2.2.1基本算法
初始化队列
void init(SqQueue *q){q-frontq-rear0;
}
测试队列是否为空
int isEmpty(SqQueue q){return q.frontq-rear;
}
测试队列是否已满
int isFull(SqQueue q){return q-rearM;
}
入队
int push(SqQueue *q,ElemType item){if(q-rearM) return 0;else{q-data[q-rear]item;q-rear;return 1;}
}
出队
int pop(SqQueue *q,ElemType *item){if(isEmpty(*q)) return 0;else{*itemq-data[q-front];q-front;return 1;}
} 2.3队列的链式存储结构
2.3.1构造原理
队列的链式储存结构是一个用线性链表表示一个队列指针front与rear分别指向实际队头元素与实际队尾元素的位置。 typedef stuct node{ ElemType data; stuct node *next; }QNode,*QLink; typedef stuct { QLink front; QLink rear; }LinkQueue; 2.3.2基本算法
初始化队列
void init(LinkQueue *q){q-front(QLink)malloc(sizeof(QNode));q-front-nextNULL;q-rearq-front;
}
测试队列是否为空
int isEmpty(LinkQueue q){return q-front-nextNULL;
}
销毁一个队列
void delQueue(QLink *front,QLink *rear){while(*front){ //队列非空时rearfront-next;free(front);frontrear;}
}
3.1例题
判断题
1-1 在用数组表示的循环队列中front值一定小于等于rear值。
1-2 通过对堆栈S操作Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为123。
1-3 若一个栈的输入序列为{1, 2, 3, 4, 5}则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
1-4 队列是一种插入和删除操作分别在表的两端进行的线性表是一种先进后出的结构。
1-5 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。
1-6 若一个栈的输入序列为123…N输出序列的第一个元素是i则第j个输出元素是j−i−1。
1-7 栈顶元素和栈底元素有可能是冋一个元素。
1-8 Circular Queue is defined to be a queue implemented by a circularly linked list or a circular array.
1-9 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑溢出情况。
1-10 循环队列也存在着空间溢出问题。
1-11 环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。
1-12 若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志则在设置一个空队时只需将队首指针和队尾指针赋同一个值不管什么值都可以。
单选题
2-1
设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4则最后一个出栈的元素必定是
A.1
B.3
C.5
D.1或者5 2-2
表达式a*(bc)-d的后缀表达式是
A.a b c * d -
B.a b c d * -
C.a b c * d -
D.- * a b c d 2-3
线性表、堆栈、队列的主要区别是什么
A.线性表用指针堆栈和队列用数组
B.堆栈和队列都是插入、删除受到约束的线性表
C.线性表和队列都可以用循环链表实现但堆栈不能
D.堆栈和队列都不是线性结构而线性表是 2-4
若top为指向栈顶元素的指针判定栈S最多容纳m个元素为空的条件是
A.S-top 0
B.S-top -1
C.S-top ! m-1
D.S-top m-1 2-5
如果循环队列用大小为m的数组表示队头位置为front、队列元素个数为size那么队尾元素位置rear为
A.frontsize
B.frontsize-1
C.(frontsize)%m
D.(frontsize-1)%m 2-6
假设有5个整数以1、2、3、4、5的顺序被压入堆栈且出栈顺序为3、5、4、2、1那么为了获得这样的输出堆栈大小至少为
A.2
B.3
C.4
D.5 2-7
若已知一队列用单向链表表示该单向链表的当前状态含3个对象是1-2-3其中x-y表示x的下一节点是y。此时如果将对象4入队然后队列头的对象出队则单向链表的状态是
A.1-2-3
B.2-3-4
C.4-1-2
D.答案不唯一 2-8
若用大小为6的数组来实现循环队列且当前front和rear的值分别为0和4。当从队列中删除两个元素再加入两个元素后front和rear的值分别为多少
A.2和0
B.2和2
C.2和4
D.2和6 2-9
若元素a、b、c、d、e、f依次进栈允许进栈、退栈操作交替进行但不允许连续三次进行退栈工作则不可能得到的出栈序列是
A.b c a e f d
B.c b d a e f
C.d c e b f a
D.a f e d c b 2-10
有六个元素以6、5、4、3、2、1的顺序进栈问哪个不是合法的出栈序列
A.2 3 4 1 5 6
B.3 4 6 5 2 1
C.5 4 3 6 1 2
D.4 5 3 1 2 6 2-11
若一个栈的入栈序列为1、2、3、…、N输出序列的第一个元素是i则第j个输出元素是
A.i−j−1
B.i−j
C.j−i−1
D.不确定 2-12
将5个字母ooops按此顺序入栈则有多少种不同的出栈顺序可以仍然得到ooops
A.1
B.3
C.5
D.6 2-13
给定一个堆栈的入栈序列为{ 1, 2, ⋯, n }出栈序列为{ p1, p2, ⋯, pn }。如果p2n则存在多少种不同的出栈序列
A.1
B.2
C.n−1
D.n 2-14
以下不是栈的基本运算的是( )。
A.删除栈顶元素
B.删除栈底元素
C.判断栈是否为空
D.将栈置为空栈 2-15
一个递归的定义可以用递归过程求解也可以用非递归过程求解但单从运行时间来看 通常递归过程比非递归过程 。
A.较快
B.较慢
C.相同
D.无法确定 2-16
设顺序栈的栈顶指针int 类型指向栈顶元素位置则判断一个栈ST最多元素为MaxSize为栈满的条件是。
A.ST.top ! -1
B.ST.top -1
C.ST.top ! MaxSize - 1
D.ST.top MaxSize - 1 2-17
假设一个栈的输入序列是1234则不可能得到的输出序列是 。
A.1,2,3,4
B.4,1,2,3
C.4,3,2,1
D.1,3,4,2 2-18
设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4则最后一个出栈的元素必定是____。
A.1
B.3
C.5
D.1或者5 2-19
为解决计算机主机与打印机之间速度不匹配问题通常设置一个打印数据缓冲区主机将要输出的数据依次写入该缓冲区而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是
A.堆栈
B.队列
C.树
D.图 2-20
某队列允许在其两端进行入队操作但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作则不可能得到的出队序列是
A.b a c d e
B.d b a c e
C.e c b a d
D.d b c a e 2-21
如果循环队列用大小为m的数组表示且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围那么这样的循环队列可以容纳的元素个数最多为
A.m-1
B.m
C.m1
D.不能确定 2-22
在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是( )。
A.f-nexts; fs;
B.r-nexts; rs;
C.s-nexts; rs;
D.s-nextf; fs; 2-23
循环顺序队列中是否可以插入下一个元素。
A.与队头指针和队尾指针的值有关
B.只与队尾指针的值有关与队头指针的值无关
C.只与数组大小有关与队首指针和队尾指针的值无关
D.与曾经进行过多少次插入操作有关 2-24
现有队列 Q 与栈 S初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }1在队头S 为空。若允许下列3种操作1出队并输出出队元素2出队并将出队元素入栈3出栈并输出出栈元素则不能得到的输出序列是
A.1, 2, 5, 6, 4, 3
B.2, 3, 4, 5, 6, 1
C.3, 4, 5, 6, 1, 2
D.6, 5, 4, 3, 2, 1 2-25
若用一个大小为6的数组来实现循环队列且当前rear和fornt的值分别为0和3。从当前队列中删除一个元素再加入两个元素后rear和front的值分别为 。
A.1和5
B.2和4
C.4和2
D.5和1 2-26
设一数列的顺序为123456通过队列操作可以得到 的输出序列。
A.3,2,5,6,4,1
B.1,2,3,4,5,6
C.6,5,4,3,2,1
D.4,5,3,2,6,1 2-27
判断一个循环队列QU最多元素为MaxSize为空的条件是。
A.QU.front QU.rear
B.QU.front ! QU.rear
C.QU.front (QU.rear 1) % MaxSize
D.QU.front ! (QU.rear 1) % MaxSize 2-2
用单链表表示的链队的队头在链表的位置。
A.链头
B.链尾
C.链中
D.均可以 2-29
关于栈和队列的下列说法正确的是
A.栈的插入操作是在栈顶进行插入时需将栈内所有元素后移
B.栈是后进先出的结构出栈时除了栈顶元素其余元素无需移动
C.循环队列的出队操作删除的是队头元素采用循环队列存储时其余队列元素均需要移动
D.链队列的入队操作在表尾进行操作时间与队列长度成正比 2-30
最不适合用作链队的链表是。
A.只带队头指针的非循环双链表
B.只带队头指针的循环双链表
C.只带队尾指针的循环双链表
D.只带队尾指针的循环单链表 2-31
下列关于栈的叙述中错误的是
采用非递归方式重写递归程序时必须使用栈函数调用时系统要用栈保存必要的信息只要确定了入栈次序即可确定出栈次序栈是一种受限的线性表允许在其两端进行操作
A.仅 1
B.仅 1、2、3
C.仅 1、3、4
D.仅 2、3、4 2-32
假设栈初始为空将中缀表达式a/b(c*d-e*f)/g转换为等价的后缀表达式的过程中当扫描到f时栈中的元素依次是 。
A.(*-
B.(-*
C./(*-*
D./-* 2-33
已知程序如下。
int S(int n)
{ return (n0)?0:s(n-1)n;}
void main()
{countS(1);
}程序运行时使用栈来保存调用过程的信息自栈底到栈顶保存的信息依次对应的是
A.main()→S(1)→S(0)
B.S(0)→S(1)→main()
C.main()→S(0)→S(1)
D. S(1)→S(0)→main()
函数题
另类堆栈
在栈的顺序存储实现中另有一种方法是将Top定义为栈顶的上一个位置。请编写程序实现这种定义下堆栈的入栈、出栈操作。如何判断堆栈为空或者满
函数接口定义
bool Push( Stack S, ElementType X );
ElementType Pop( Stack S );
其中Stack结构定义如下
typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode {ElementType *Data; /* 存储元素的数组 */Position Top; /* 栈顶指针 */int MaxSize; /* 堆栈最大容量 */
};
typedef PtrToSNode Stack;
注意如果堆栈已满Push函数必须输出“Stack Full”并且返回false如果队列是空的则Pop函数必须输出“Stack Empty”并且返回ERROR。
裁判测试程序样例
#include stdio.h
#include stdlib.h#define ERROR -1
typedef int ElementType;
typedef enum { push, pop, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode {ElementType *Data; /* 存储元素的数组 */Position Top; /* 栈顶指针 */int MaxSize; /* 堆栈最大容量 */
};
typedef PtrToSNode Stack;Stack CreateStack( int MaxSize )
{Stack S (Stack)malloc(sizeof(struct SNode));S-Data (ElementType *)malloc(MaxSize * sizeof(ElementType));S-Top 0;S-MaxSize MaxSize;return S;
}bool Push( Stack S, ElementType X );
ElementType Pop( Stack S );Operation GetOp(); /* 裁判实现细节不表 */
void PrintStack( Stack S ); /* 裁判实现细节不表 */int main()
{ElementType X;Stack S;int N, done 0;scanf(%d, N);S CreateStack(N);while ( !done ) {switch( GetOp() ) {case push: scanf(%d, X);Push(S, X);break;case pop:X Pop(S);if ( X!ERROR ) printf(%d is out\n, X);break;case end:PrintStack(S);done 1;break;}}return 0;
}/* 你的代码将被嵌在这里 */
输入样例
4
Pop
Push 5
Push 4
Push 3
Pop
Pop
Push 2
Push 1
Push 0
Push 10
End输出样例
Stack Empty
3 is out
4 is out
Stack Full
0 1 2 5 代码
bool Push( Stack S, ElementType X ){if(S-TopS-MaxSize){
//Top定义为栈顶的上一个位置,此刻通过判断Top是否MaxSize判断表满printf(Stack Full\n);return false;}S-Data[S-Top]X;return ture;
}
ElementType Pop( Stack S ){if(S-Top) return S-Data[--S-Top];else{printf(Stack Empty\n);return ERROR;}
}
用顺序栈实现将非负的十进制数转换为指定的进制数
利用顺序栈将输入的非负的十进制数N转换为指定的d二、八或十六进制数。
顺序栈的定义如下
#define STACKSIZE 100
typedef int DataType;
typedef struct
{ DataType items[STACKSIZE]; /*存放栈中元素的一维数组*/int top; /*用来存放栈顶元素的下标*/
}SqStack;
函数接口定义
int DecimalConvert(SqStack *s, int dec, int scale);
函数参数说明形参--s、dec、scale其中s是存放转换后的scale进制数的各位数字dec 主函数输入的待转换的十进制数scale是指定的数制只能是2、8或16。 函数返回值1表示函数执行完成0表示函数未成功执行。
裁判测试程序样例
#include stdio.h
#include stdlib.h
#define STACKSIZE 100
typedef int DataType;
typedef struct
{DataType items[STACKSIZE]; /*存放栈中元素的一维数组*/int top; /*用来存放栈顶元素的下标*/
}SqStack;
int InitSqStack(SqStack* S)
{ // 初始化顺序栈S-top -1;return 1;
}
int SqStackPush(SqStack* S, DataType e)
{ // 压栈函数if (S-top STACKSIZE - 1)return 0; /*栈已满*/S-top;S-items[S-top] e;return 1;
}
int SqStackPop(SqStack* S, DataType* e)
{ /* 将栈S的栈顶元素弹出放到e所指的存储空间中 */if (S-top -1) /* 栈为空 */return 0;*e S-items[S-top]; /* 将栈顶元素带回来 */S-top--; /* 修改栈顶指针 */return 1;
}
int SqStackEmpty(SqStack S)
{ /* S为顺序栈 */if (S.top -1)return 1;elsereturn 0;
}
/* 本题要求函数 */
int DecimalConvert(SqStack* s, int dec, int scale);int main()
{SqStack s;char ch[] 0123456789ABCDEF; //二、八、十六进制所使用的数字unsigned dec, scale;DataType tmp;InitSqStack(s);scanf(%d %d, dec, scale); // 某些编译器要求此处改为scanf_sif (DecimalConvert(s, dec, scale)){printf(十进制数:%d,转换为:%d进制数,结果为:, dec, scale);while (!SqStackEmpty(s)){SqStackPop(s, tmp);printf(%c, ch[tmp]);}}elseprintf(数制转换未成功);return 0;
}
/* 请在这里填写答案 */
输入样例
20 2
输出样例
十进制数:20,转换为:2进制数,结果为:10100输入样例
20 8
输出样例
十进制数:20,转换为:8进制数,结果为:24输入样例
20 16
输出样例
十进制数:20,转换为:16进制数,结果为:14
代码
int DecimalConvert(SqStack *s, int dec, int scale){if(dec0) return 0;while(dec){int rdec%scale
//裁判测试中有将9的数转换成字母所以我们只需要求出余数即可SqStackPush(s,r); //压入栈s中dec/scale;}return 1;
} 简单表达式求值
本题要求实现两个整数的运算运算符仅有四种、-、* 、/ 但是以字符串的形式输入表达式。注意这里的除数结果是整数即5/41。
函数接口定义
int cal( char a[] );
其中 a是用户传入的参数此处为表达式表达式。
裁判测试程序样例
#include stdio.h
int cal( char s[] );
int main()
{char a[100];int res;scanf(%s,a);rescal(a);printf(%d,res);return 0;}
/* 请在这里填写答案 */
输入样例
12312输出样例
135
代码
#includemath.h
int cal(char *s){int count10,count20,num0;int c[100],d[100],c10,d10,aaa0,i;while(s[num]);num--; //计算字符串长度for(int i0;inum;i){ //第一个数字每一位存数组if(s[i]0s[i]9) //保证数字c[count1]s[i]-0;elsebreak;}for(int icount11;inum;i){ //第二个数字每一位存数组if(s[i]0s[i]9)d[count2]s[i]-0;elsebreak;}for(int icount1-1;i0;i--){ //把数组转成数字c1c[i]*pow(10,count1-i-1);}for(int icount2-1;i0;i--){d1d[i]*pow(10,count2-i-1);}switch(s[count1]){ //加减乘除四个操作case :aaac1d1;break;case -:aaac1-d1;break;case *:aaac1*d1;break;case /:aaac1/d1;break;}return aaa;
}
另类循环队列
如果用一个循环数组表示队列并且只设队列头指针Front不设尾指针Rear而是另设Count记录队列中元素个数。请编写算法实现队列的入队和出队操作。
函数接口定义
bool AddQ( Queue Q, ElementType X );
ElementType DeleteQ( Queue Q );
其中Queue结构定义如下
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {ElementType *Data; /* 存储元素的数组 */Position Front; /* 队列的头指针 */int Count; /* 队列中元素个数 */int MaxSize; /* 队列最大容量 */
};
typedef PtrToQNode Queue;
注意如果队列已满AddQ函数必须输出“Queue Full”并且返回false如果队列是空的则DeleteQ函数必须输出“Queue Empty”并且返回ERROR。
裁判测试程序样例 #include stdio.h
#include stdlib.h#define ERROR -1
typedef int ElementType;
typedef enum { addq, delq, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {ElementType *Data; /* 存储元素的数组 */Position Front; /* 队列的头、尾指针 */int Count; /* 队列中元素个数 */int MaxSize; /* 队列最大容量 */
};
typedef PtrToQNode Queue; Queue CreateQueue( int MaxSize )
{Queue Q (Queue)malloc(sizeof(struct QNode));Q-Data (ElementType *)malloc(MaxSize * sizeof(ElementType));Q-Front 0;Q-Count 0;Q-MaxSize MaxSize;return Q;
}bool AddQ( Queue Q, ElementType X );
ElementType DeleteQ( Queue Q );Operation GetOp(); /* 裁判实现细节不表 */int main()
{ElementType X;Queue Q;int N, done 0;scanf(%d, N);Q CreateQueue(N);while ( !done ) {switch( GetOp() ) {case addq: scanf(%d, X);AddQ(Q, X);break;case delq:X DeleteQ(Q);if ( X!ERROR ) printf(%d is out\n, X);break;case end:while (Q-Count) printf(%d , DeleteQ(Q));done 1;break;}}return 0;
}/* 你的代码将被嵌在这里 */
输入样例
4
Del
Add 5
Add 4
Add 3
Del
Del
Add 2
Add 1
Add 0
Add 10
End输出样例
Queue Empty
5 is out
4 is out
Queue Full
3 2 1 0
代码
bool AddQ( Queue Q, ElementType X ){if(Q-CountQ-MaxSize){printf(Queue Full\n);return false;}Q-Data[(Q-FrontQ-Count)%Q-MaxSize]X; //注意Q是循环队列Q-Count;return true;
}
ElementType DeleteQ( Queue Q ){if(Q-Count0){printf(Queue Empty\n);return ERROR;}ElementType XQ-Data[Q-Front]; //队列先进的先出Q-Front(Q-Front1)%Q-MaxSize;Q-Count--;return X;}编程题 括号匹配
给定一串字符不超过100个字符可能包括括号、数字、字母、标点符号、空格编程检查这一串字符中的( ) ,[ ],{ }是否匹配。
输入格式:
输入在一行中给出一行字符串不超过100个字符可能包括括号、数字、字母、标点符号、空格。
输出格式:
如果括号配对输出yes否则输出no。
输入样例1:
sin(1020)输出样例1:
yes输入样例2:
{[}]输出样例2:
no
代码
#includestdio.h
int main(){char s1[120],s2[120];int s2l,flag1;gets(s1);for(int i0;s1[i]!\0;i){ //字符串中包含空格if(s1[i](||s1[i][||s1[i]{){s2[s2l]s1[i];}else if(s1[i])){if(s2l1||s2[s2l]!(){flag0;break;}s2l--;}else if(s1[i]]){if(s2l1||s2[s2l]![){flag0;break;}s2l--;}else if(s1[i]}){if(s2l1||s2[s2l]!}){flag0;break;}s2l--;}}if(flag0||index!0) printf(no);else printf(yes);return 0;
}
栈操作的合法性
假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列对一个空堆栈进行操作相应操作均可行如没有出现删除时栈空且最后状态也是栈空则称该序列是合法的堆栈操作序列。请编写程序输入S和X序列判断该序列是否合法。
输入格式:
输入第一行给出两个正整数 n 和 m其中 n 是待测序列的个数m≤50是堆栈的最大容量。随后 n 行每行中给出一个仅由S和X构成的序列。序列保证不为空且长度不超过100。
输出格式:
对每个序列在一行中输出YES如果该序列是合法的堆栈操作序列或NO如果不是。
输入样例
4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX输出样例
YES
NO
NO
NO 代码
#includebits/stdc.h
using namespace std;
int main(){int n,m;cinnm;char str[120];while(n--){cinstr;int l0;int flag0;for(int j0;jstrlen(str);j){if(str[j]S) l;else if(str[j]X) l--;else flag;if(lm||l0) break;}if(l0flag0) coutYES\n;else coutNO\n;}return 0;
}
