CODEWITHSUNDEEP
python
paddu
paddu

Reputation: 713

Matching balanced parentheses but must check for preserving the order

Similar question

Here are my test cases ->

{(<[testdata])>} -> false

{just{test<of>Unbalanced}String') -> False

{(<[ABalancedExample]>)} -> True

opening = ['[','(','<','{']
closing = [']',')','>','}']

My code doesn't work for {(<[testdata])>} as the order of the parentheses is not taken care of

def check(str):
    count = 0
    if not str:
        return None
    for i in str:
        if i in opening:
            count += 1
        elif i in closing:
            count -= 1
        if count < 0:
            return False
    return count == 0

Upvotes: 0

Views: 88

Answers (1)

Adam Smith
Adam Smith

Reputation: 54223

This is a stack problem. Luckily lists work as stacks by default.

def check(s):
    """
    >>> check("{(<[testdata])>}")
    False
    >>> check("{just{test<of>Unbalanced}String')")
    False
    >>> check("{(<[ABalancedExample]>)}")
    True
    """

    bracket_matches = {
        '[': ']',
        '(': ')',
        '<': '>',
        '{': '}',
    }

    opening = set(bracket_matches.keys())
    closing = set(bracket_matches.values())
    stack = []
    
    for ch in s:
        if ch in opening:
            stack.append(bracket_matches[ch])
            continue
        if ch in closing:
            try:
                if ch == stack.pop():
                    continue
                else:
                    return False
            except IndexError:
                # stack is empty
                return False
    return stack == []

Note that if you need to allow non-matching closing brackets so long as the rest of the brackets still balance, this becomes insufficient, e.g. including the following test makes this function non-compliant:

>>> check("{{<[test}data]>}}")

Upvotes: 2

Related Questions