使用python假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写程序,输入S和X序列,判断该序列是否合法。 输入格式: 输入第一行给出两个正整数N和M,其中N是待测序列的个数,M(≤50)是堆栈的最大容量。随后N行,每行中给出一个仅由S和X构成的序列。序列保证不为空,且长度不超过100。 输出格式: 对每个序列,在一行中输出YES如果该序列是合法的堆栈操作序列,或NO如果不是。
时间: 2024-02-17 11:05:02 浏览: 24
可以使用栈的思想来解决这个问题。具体地,遍历序列中的每一个元素,如果是 "S",就将计数器加 1,表示入栈一个元素;如果是 "X",就将计数器减 1,表示弹出一个元素。如果计数器小于 0,说明在某个时刻栈已经为空了,但是仍然进行了出栈操作,此时该序列不合法。最后如果计数器为 0,说明序列合法,否则不合法。
下面是具体的 Python 代码实现:
```python
n, m = map(int, input().split())
for i in range(n):
s = input().strip()
stack = []
cnt = 0
for c in s:
if c == "S":
cnt += 1
if cnt > m:
break
stack.append(c)
else:
cnt -= 1
if not stack:
break
stack.pop()
if cnt == 0:
print("YES")
else:
print("NO")
```
其中,`stack` 表示模拟的栈,`cnt` 表示栈中元素的个数。在遍历序列中的每一个元素时,如果是 "S",就将计数器加 1,并将该元素入栈;如果是 "X",就将计数器减 1,并将栈顶元素弹出。如果计数器小于 0 或者栈为空,就直接退出循环,因为此时已经不可能使序列合法了。最后根据计数器的值判断序列是否合法。