HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Check if all of the delimiters in an expression are matched and closed

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
expressionthematchedallareclosedandcheckdelimiters

Problem

Problem

Write an algorithm to determine if all of the delimiters in an
expression are matched and closed.

{(abc)22}[14(xyz)2] should pass

[ { ] } should fail

{ (x) } [ should fail

Any advice of code functional bug, performance in terms of algorithm time complexity, code style are appreciated.

delimiters = ['[', ']', '(', ')', '{', '}']
delimiters_map = {']':'[', ')':'(', '}':'{'}

def check_match(source):
    working_set = []
    for i,v in enumerate(source):
        if v not in delimiters:
            continue
        if v in delimiters_map: # end of a delimiter:
            if working_set[-1] != delimiters_map[v]:
                return False
            else:
                working_set.pop(-1)
        elif v in delimiters:
            working_set.append(v)

    if len(working_set) > 0:
        return False
    else:
        return True

if __name__ == "__main__":
    print check_match('{(abc)22}[14(xyz)2]')
    print check_match('[ { ] }')
    print check_match('{ (x) } [')

Solution

Performance

Checking if a list contains a value is an \$O(n)\$ operation.
To make if v not in delimiters fast,
it would be better to make delimiters a set instead of a list.

The elif v in delimiters: is unnecessary, because at that point we already know that v is in delimiters, so you can replace with a simple else:.

Creating lists and maps of characters

This is a PITA to type:

delimiters = ['[', ']', '(', ')', '{', '}']
delimiters_map = {']':'[', ')':'(', '}':'{'}


An easier and less error-prone way is to call list to turn a string into a list of characters:

openers = list('[({')
closers = list('])}')
delimiters = set(openers + closers)
delimiters_map = dict(zip(closers, openers))


If it's a stack, call it a stack

working_set is a misleading name. It suggests a set, but it's a list.
And you're using it as a stack, so I suggest to call it a stack.

Use doctests

Doctests are awesome. You can run them with python -mdoctests script.py.

def check_match(source):
    """
    >>> check_match('{(abc)22}[14(xyz)2]')
    True

    >>> check_match('[ { ] }')
    False

    >>> check_match('{ (x) } [')
    False

    >>> check_match('')
    True

    """
    # ... (your implementation)

Code Snippets

delimiters = ['[', ']', '(', ')', '{', '}']
delimiters_map = {']':'[', ')':'(', '}':'{'}
openers = list('[({')
closers = list('])}')
delimiters = set(openers + closers)
delimiters_map = dict(zip(closers, openers))
def check_match(source):
    """
    >>> check_match('{(abc)22}[14(xyz)2]')
    True

    >>> check_match('[ { ] }')
    False

    >>> check_match('{ (x) } [')
    False

    >>> check_match('')
    True

    """
    # ... (your implementation)

Context

StackExchange Code Review Q#150771, answer score: 7

Revisions (0)

No revisions yet.