Here is an example where the скобки 〈 п{р}авильно (вло[ж]ены)〉.
Here is an example where скобки НЕ 〈 пр(авильно вложены〉).

2 answers 2

A classic solution using a stack that preserves the types of (unbalanced) opening brackets:

 For each character in the text
    check if it is an opening bracket
        if so, add to the stack the type of this bracket (corner / round / etc)
    if not, check whether the character is a closing parenthesis
        if the last added opening bracket is the same,
            then remove it from the stack (a matching pair of brackets was found)
        Otherwise, terminate the algorithm — an incorrectly nested bracket was found.

 Continue to the end of the text and if the stack is empty, the text contains
 only properly nested brackets.

On Python 3:

 def is_balanced(text, brackets="〈〉()[]{}"): opening, closing = brackets[::2], brackets[1::2] stack = [] # keep track of opening brackets types for character in text: if character in opening: # bracket stack.append(opening.index(character)) elif character in closing: # bracket if stack and stack[-1] == closing.index(character): stack.pop() # remove the matched pair else: return False # unbalanced (no corresponding opening bracket) or # unmatched (different type) closing bracket return (not stack) # no unbalanced brackets

In this case, the type of bracket (curly / square / etc) is represented by an index in the opening list containing all opening brackets. closing contains closing brackets of the same types on the same indices.

Example:

 >>> is_balanced('скобки 〈 п{р}авильно (вло[ж]ены)〉') True >>> is_balanced('скобки НЕ 〈 пр(авильно вложены〉)') False

    You can remove flat (unfolded) balanced parts as long as possible, and then check whether [unbalanced] brackets remain in the text:

     def is_balanced(text, brackets="〈〉()[]{}"): L = list(map(re.escape, brackets)) # make it safe for a regex regex = re.compile('|'.join( # O <-> opening, C <-> closing ['{O}[^{B}]*{C}'.format(B=''.join(L),**vars()) for O, C in zip(L[::2], L[1::2])])) n = "number of substitutions" while n: text, n = regex.subn('', text) # remove non-nested/flat balanced parts return set(brackets).isdisjoint(text) # no [unbalanced] brackets left