NYOJ2.0 括号配对问题

一时失言乱红尘 2022-03-30 11:08 184阅读 0赞

# 2-括号配对问题 #

*  内存限制:64MB 时间限制:3000ms 特判: No

*    
    
 *  通过数:377 提交数:1622 难度:3

## 题目描述: ##

现在，有一行括号序列，请你检查这行括号是否配对。

## 输入描述: ##

第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[", "]", "(", ")" 四种字符

## 输出描述: ##

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

## 样例输入: ##

复制

3
    [(])
    (])
    ([[]()])

## 样例输出: ##

No
    No
    Yes

# 解题思路:运用到一种数据结构:栈
    # 将输入的字符串输入到栈中(在这里用到的python的列表,python列表可以实现栈的功能),然后将数据从栈顶
    # 取出,对另外一个列表进行判断,若其为空,则直接将数据添入其中,若不为空则用其栈顶数据与数据进行匹配,若配对则
    # 将其取出,若不则将数据添入其中
    
    N = int(input())
    d = {'[': ']', ']': '[', '(': '(', ')': '('}
    while N > 0:
        S = input()
        # 将字符串转成列表
        lt = list(S)
        # 定义空列表
        ln = []
        # 当lt不为空时
        while len(lt) > 0:
            # 取出栈顶数据
            t = lt.pop()
            # 若ln中有数据
            if len(ln) > 0:
                # 若ln栈顶数据为[或(开口向右的,则此括号字符串不可能匹配成功
                if ln[-1] == '[' or ln[-1] == '(':
                    break
                else:
                    # 若匹配成功则将栈顶数据取出
                    if t == d[ln[-1]]:
                        ln.pop()
                    # 匹配失败,则将数据放入ln栈顶
                    else:
                        ln.append(t)
            else:
                ln.append(t)
        # 结束时,若ln为空则说明全部匹配成功
        if len(ln) == 0:
            print('Yes')
        # 否则匹配失败
        else:
            print('No')
        N -= 1