A46342. $合法出栈序列给定一个由不同小写字母构成的长度不超过8的字符串x，现在要将该字符串的字符依次压入栈中，然后再全部弹出。要求左边的字符一定比右边的字符先入栈，出栈顺序无要求。再给定若干字符串，对每个字符串，判断其是否是可能的x中的字符的出栈序列。输入第一行是原始字符串x 后面有若干行，每行一个字符串输出对除第一行以外的每个字符串，判断其是否是可能的出栈序列。如果是，输出"YES"，否则，输出"NO"\dots$

填空题困难

知识点

栈出栈序列模拟

题目描述

合法出栈序列 给定一个由不同小写字母构成的长度不超过8的字符串x，现在要将该字符串的字符依次压入栈中，然后再全部弹出。 要求左边的字符一定比右边的字符先入栈，出栈顺序无要求。 再给定若干字符串，对每个字符串，判断其是否是可能的x中的字符的出栈序列。 输入 第一行是原始字符串x 后面有若干行，每行一个字符串 输出 对除第一行以外的每个字符串，判断其是否是可能的出栈序列。如果是，输出"YES"，否则，输出"NO" 样例输入 abc abc bca cab 样例输出 YES YES NO

参考答案

import sys
 
list_1 = list(input())
 
# print(list_1)
for line in sys.stdin:
    list_2 = list(line)
    index = 0
    stack = []  # 模拟入栈出栈过程
    for i in list_1:  # 遍历每个入栈元素
        stack.append(i)  # 入栈
        while len(stack) > 0 and stack[-1] == list_2[index]:  # 判者栈顶元素和比对的队列首部是否相同
            stack.pop()  # 相同就弹栈，一直弹到不同为止
            index += 1
    if len(stack) == 0:
        print("YES")  # 栈为空则YES,否则匹配失败NO
    else:
        print("NO")

上一题下一题

竞赛

考级认证

学习入口

题目描述

参考答案

题目描述

参考答案

同类题目