22068: 合法出栈序列

http://cs101.openjudge.cn/practice/22068/

给定一个由大小写字母和数字构成的，没有重复字符的长度不超过62的字符串x，现在要将该字符串的字符依次压入栈中，然后再全部弹出。

要求左边的字符一定比右边的字符先入栈，出栈顺序无要求。

再给定若干字符串，对每个字符串，判断其是否是可能的x中的字符的出栈序列。

输入

第一行是原始字符串x 后面有若干行(不超过50行)，每行一个字符串，所有字符串长度不超过100

输出

对除第一行以外的每个字符串，判断其是否是可能的出栈序列。如果是，输出"YES"，否则，输出"NO"

样例输入

abc
abc
bca
cab

样例输出

YES
YES
NO

来源: Guo wei

python

def is_valid_pop_sequence(origin, output):
    if len(origin) != len(output):
        return False  # 长度不同，直接返回False

    stack = []
    bank = list(origin)
    
    for char in output:
        # 如果当前字符不在栈顶，且bank中还有字符，则继续入栈
        while (not stack or stack[-1] != char) and bank:
            stack.append(bank.pop(0))
        
        # 如果栈为空，或栈顶字符不匹配，则不是合法的出栈序列
        if not stack or stack[-1] != char:
            return False
        
        stack.pop()  # 匹配成功，弹出栈顶元素
    
    return True  # 所有字符都匹配成功

# 读取原始字符串
origin = input().strip()

# 循环读取每一行输出序列并判断
while True:
    try:
        output = input().strip()
        if is_valid_pop_sequence(origin, output):
            print('YES')
        else:
            print('NO')
    except EOFError:
        break

python

# 23n2300011406(cry_QAQ)
origin = input()
while True:
    try:
        outout = input()
        stack,bank = [],list(origin) #stack 用于模拟栈操作，bank 存放原始字符串尚未入栈的字符
        l = len(origin)
        flag = False
        if len(outout) == l:
            for i in range(l):
                # 如果bank不为空且stack为空，则将bank的第一个字符入栈
                if bank and not stack: 
                    stack.append(bank.pop(0))
                
                 # 将bank中的字符入栈，直到栈顶字符和出栈序列的当前字符相同
                while bank and stack[-1] != outout[i]:
                    stack.append(bank.pop(0))
                if stack.pop() != outout[i]:
                    print('NO')
                    flag = True
                    break
            if not flag:
                print('YES')
        else:
            print('NO')
    except EOFError:
        break

卢卓然-23-生命科学学院，思路：

利用stack的FILO的性质

入栈的顺序是降序排列（如6,5,4,3,2,1)，由于栈是FILO，那么出栈序列任意数A的后面比A大的数都是按照升序排列的；

入栈的顺序是升序排列（如1,2,3,4,5,6)，由于栈是FILO，那么出栈序列任意数A的后面比A小的数都是按照降序排列的。

以第二种情况为例，因为在出栈序列任意数A的后面比A小的数，都具有的特点是，比A早进栈而且比A晚出栈。那么这些数组成的序列就必然是恰好倒序的。

python

#23 生科 卢卓然
#将x中每个字符正序编号1~n
x=input()
L=len(x)
dic=dict()
i=1
for string in x:
    dic[string]=i
    i+=1
#提前声明一个maximum，防止oj特有的一种CE
maximum=-1

def check(index,length):#index当前字符的位置,length是s的长度
    '''鉴定该位置之后所有编号比他小的字符是否全为降序排列'''
    
    global s,maximum#maximum该位置之前字符中出现的最大编号
    number=dic[s[index]]
    if number<=maximum:
        return True
    '''之前的最大的编号的字符之后的所有编号比他小的字符全为降序排列,
    所以编号比maximum小的字符之后的就更是降序排列,剪枝'''
    
    tempmax=number#tempmax暂时的最大符号，不断更新以判断是否为降序排列
    flag=True#标记是否为降序排列
    for k in range(index+1,length):
        tempstr=s[k]
        tempnum=dic[tempstr]
        if tempnum<=number:#编号比number小
            if tempnum<=tempmax:#是否为降序排列
                tempmax=tempnum#更新tempmax
                continue
            else:
                flag=False
                break
    if flag:
        maximum=number#更新maximum
        return True
    else:
        return False

output=[]
while True:
    try:
        s = input()
        if set(s)==set(x) and len(set(s))==len(s):#防止蛇皮数据导致RE
            f=True#YES还是NO
            maximum=-1#初始化为一个比较小的值
            for j in range(L-2):#L-2:最后两位不用看，没有意义
                if not check(j,L):
                    f=False
                    break
            if f:
                output.append('YES')
            else:
                output.append("NO")
        else:
            output.append("NO")
    except EOFError:
        break

for o in output:
    print(o)

22068: 合法出栈序列 ​

22068: 合法出栈序列