问题2609--初识堆栈

2609: 初识堆栈

时间限制: 1 Sec  内存限制: 128 MB
提交: 476  解决: 48
[状态] [讨论版] [提交] [命题人:]
题目描述

栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
假设以 S X 分别表示入栈和出栈操作。如果根据一个仅由 S X 构成的序列,对一 个堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称 该序列是合法的堆栈操作序列。请编写程序,输入 S X 序列,判断该序列是否合法。

输入

输入第一行给出两个正整数 N M,其中 N 是待测序列的个数,M≤50)是堆栈的 最大容量。随后 N 行,每行中给出一个仅由 S X 构成的序列。序列保证不为空,且长度 不超过 100

输出

对每个序列,如果该序列是合法的堆栈操作序列在一行中输出 YES,否则输出NO

样例输入 Copy
4 10 
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX
样例输出 Copy
YES
NO
NO
NO
来源/分类