PTA练习题：堆栈操作合法性

╰半橙微兮° 2023-03-14 05:53 40阅读 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

#include<stdio.h>
    #include<string.h>
    
    int main()
    {
    	int n,m;
    	scanf("%d %d",&n,&m);
    	int arr[n];
    	char s[n][101];
    	getchar();
    	for(int i=0;i<n;i++)
    	{
    		gets(s[i]);
    	}
    	for(int i=0;i<n;i++)
    	{
    		int top = 0; 
    		int cnt = 0;
    		for(int j=0;j<strlen(s[i]);j++)
    		{
    			if(s[i][j] == 'S')
    			{
    				if(top == m)
    				{
    					cnt = 1;
    					break;
    				}
    				top++;
    			}
    			if(s[i][j] == 'X')
    			{
    				if(top == 0)
    				{
    					cnt = 1;
    					break;
    				}
    				top--;
    			}
    		}
    		if(cnt || top != 0)
    		{
    			arr[i] = -1;
    		}
    		else
    		{
    			arr[i] = 1;
    		}
    	}
    	for(int i=0;i<n;i++)
    	{
    		if(arr[i] == 1)
    		{
    			printf("YES");
    		}
    		else
    		{
    			printf("NO");
    		}
    		if(i != n-1)
    		{
    			printf("\n");
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，40人围观）

还没有评论，来说两句吧...

相关阅读

相关 PTA——特殊堆栈

特殊堆栈 (30 分) 堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个

我不是女神ヾ/ 2023年10月02日 16:25/ 0 赞/ 77 阅读

相关【PTA】特殊堆栈

题目重述堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：

淩亂°似流年/ 2023年07月03日 02:38/ 0 赞/ 62 阅读

相关 PTA练习题：堆栈模拟队列

设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S)：判断堆栈S

分手后的思念是犯贱/ 2023年03月14日 05:53/ 0 赞/ 102 阅读

相关 PTA练习题：括号匹配

给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,\[ \],\{ \}是否匹配。输入格式: 输入在一行中给出一

布满荆棘的人生/ 2023年03月14日 05:53/ 0 赞/ 61 阅读

相关 PTA练习题：堆栈操作合法性

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作

╰半橙微兮°/ 2023年03月14日 05:53/ 0 赞/ 41 阅读

相关 PTA练习题：旅游规划

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是

r囧r小猫/ 2023年02月19日 13:28/ 0 赞/ 95 阅读

相关 PTA练习题：路径判断

给定一个有N个顶点和E条边的无向图，请判断给定的两个顶点之间是否有路径存在。假设顶点从0到N−1编号。输入格式: 输入第1行给出2个整数N(0<N≤10)和E，分别是图

约定不等于承诺〃/ 2023年02月19日 13:28/ 0 赞/ 105 阅读

相关堆栈操作合法性

题目描述：假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法

梦里梦外;/ 2022年07月29日 11:42/ 0 赞/ 172 阅读

相关 PTA练习题.高考状元

include<iostream> include<string> using namespace std; class stude

骑猪看日落/ 2022年06月13日 03:53/ 0 赞/ 318 阅读

相关堆栈操作合法性

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作

￡神魔★判官ぃ/ 2022年05月09日 04:28/ 0 赞/ 201 阅读