Codility每周一课：L7 Stacks and Queue

7.png

P7.1 Brackets

Determine whether a given string of parentheses (multiple types) is properly nested.

• P7.1 括号嵌套
  判断一个串(多种类型)中的括号是否是正确的嵌套

满足以下任一条件，则认为由N个字符组成的字符串S是正确嵌套的：

1. S为空；

2. S的形式为"(U)"或"[U]"或"U"，其中U是正确嵌套的字符串；

3. S的形式为"VW"，其中V和W是正确嵌套的字符串;

例如，字符串"[()()]"是正确的嵌套，但"([)()]"不是正确的嵌套。

编写函数：

def solution(S)

如果字符串S由N个字符组成，则如果S嵌套正确，则返回1，否则返回0。

例如，给定S="[()()]"，函数应返回1，给定S="([)()]"，函数应返回0。

假定：

1. N是区间[0，200000]中的整数；

2. 字符串S是由以下字符中的几种组成： "(", "{", "[", "]", "}" 和 ")"；

• 解题思路

如果是括号的左半部分，就存储在列表里。如果是括号的右半部分，首先判断列表是否为空，如果是空的，则不匹配。如果不为空，则判断列表的最后一个符号是否是这个括号的左半部分，如果不是就不匹配。是的话，就把列表最后一个删除。遍历完字符串后，如果列表中依然有元素，则不匹配。如果没有，则是匹配的。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 7：Stacks and Queues
# P 7.1 Brackets


def solution(S):
    """
    判断字符串S中的符号是否为正确的嵌套
    :param S: 字符串
    :return: 判断是否为正确的嵌套
    """
    left = '([{'
    brackers_dict = {'(': ')', '[': ']', '{': '}'}
    brackers = []
    if len(S) == 0:
        return 1
    else:
        for i in S:
            if i in left:
                brackers.append(i)
            else:
                try:
                    if brackers_dict[brackers[-1]] == i:
                        brackers.pop(-1)
                    else:
                        return 0
                except IndexError:
                    return 0
        if len(brackers) == 0:
            return 1
        else:
            return 0

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image