首页 > 试题广场 >

完成括号匹配

[编程题]完成括号匹配

热度指数：3761 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

合法的括号匹配序列被定义为:
1. 空串""是合法的括号序列
2. 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列
3. 如果"X"是一个合法的序列,那么"[X]"也是一个合法的括号序列
4. 每个合法的括号序列都可以由上面的规则生成
例如"", "[]", "[][][]", "[[][]]", "[[[[]]]]"都是合法的。
牛牛现在给出一个括号序列s,牛牛允许你执行的操作是:在s的开始和结尾处添加一定数量的左括号('[')或者右括号(']')使其变为一个合法的括号匹配序列。牛牛希望你能求出添加最少的括号之后的合法的括号匹配序列是什么。

输入描述:

输入包括一个字符串s,s的长度length(1 ≤ length ≤ 50),s中只包含'['和']'。

输出描述:

输出一个字符串,表示括号完全匹配的序列。

示例1

输入

][

输出

[][]

算法知识视频讲解

Python

白色纯度

有一个取巧的方法，先将原字符串中所有的‘[]’替换为空，留下来的就是无法匹配的。在依次在左边或者右边添加相应的符号即可。

if __name__=='__main__':
    string = input().strip()
    s= string
    length = len(s)
    temp = float('inf')
    while length!=temp:
        length = temp
        s = s.replace('[]','')
        temp = len(s)
    left = []
    right = []
    for i in s:
        if i==']':
            left.append('[')
        else:
            right.append(']')
    ans1 = ''.join(left[::-1])
    ans2 = ''.join(right[::-1])
    res = ans1 + string+ans2
    print(res)

发表于 2019-09-15 15:51:43 回复(0)