3
\$\begingroup\$

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) } [')
\$\endgroup\$
6
\$\begingroup\$

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)
\$\endgroup\$
5
  • \$\begingroup\$ Nice catch janos, vote up and especially love your comments of using set and also elegant ways of initialize. Wondering if you have any ideas to improve algorithm time complexity comparing to current implementation? \$\endgroup\$
    – Lin Ma
    Dec 27 '16 at 2:54
  • \$\begingroup\$ BTW, janos, another comments is, how do you handle data structure of stack in Python 2.7? It seems there is no built-in stack data structure in Python 2.7? I always use list to simulate, your expertise is appreciated. \$\endgroup\$
    – Lin Ma
    Dec 27 '16 at 3:40
  • 2
    \$\begingroup\$ @LinMa Using a list as a stack is fine, and indeed explicitly encouraged in the Python docs: docs.python.org/2/tutorial/… Your use of the data structure looks fine – but the name is a bit misleading. \$\endgroup\$
    – alexwlchan
    Dec 27 '16 at 9:01
  • 2
    \$\begingroup\$ @LinMa I already addressed performance concerns in the first paragraph, I have nothing more to add on top of that \$\endgroup\$
    – janos
    Dec 27 '16 at 9:18
  • \$\begingroup\$ @alexwlchan, do you know what is the reason why Python does not have a stack individual class, other than reuse list? I think implement stack to have one end add/remove could have benefits in terms of performance comparing to a general list implementation, which allows add/remove at any location and any sequence. \$\endgroup\$
    – Lin Ma
    Dec 28 '16 at 22:02
4
\$\begingroup\$

Crashing bug

I have a number of cases where an unmatched closing delimiter causes the function to raise an IndexError:

check_match(']')
check_match('0]')
check_match(']0')
check_match('0]0')

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/private/tmp/delimiters.py", line 10, in check_match
    if working_set[-1] != delimiters_map[v]:
IndexError: list index out of range

In particular, it crashes whenever there’s no opening delimiter but there is at least one closing delimiter. Trying to look up the previous opening delimiter will fail, and we get the crash.

This diff fixes the bug, and after that I’m unable to find any other crashes:

-            if working_set[-1] != delimiters_map[v]:
+            if (not working_set) or (working_set[-1] != delimiters_map[v]):


How did I find this bug? (Hint: I’m not just lucky)

I used the Hypothesis testing library (mild disclaimer: I’m friends with the library author, and I’ve done bits of work on it).

Your function should always return either True or False, whatever text we give it as input. We can write a test with Hypothesis that asserts this is the case:

from hypothesis import given, strategies as st

@given(st.text())
def test_check_match_always_returns_bool(xs):
    """`check_match()` returns a boolean for any given text input."""
    assert check_match(xs) in (True, False)

When you run this with py.test, it tries 200 different, randomly-generated strings and quickly discovers the bug.

Once I patched the bug, I ran this test a bunch more times, and was unable to find any other crashes. That suggests any remaining crashers are at least rare, if even extant.

(Writing a test with Hypothesis that asserts a stronger form of correctness than “doesn’t crash” is left as an exercise for the reader.)

\$\endgroup\$
2
  • \$\begingroup\$ Nice catch alexwlchan for the bug and vote up. Wondering if you have any ideas to improve algorithm time complexity comparing to current implementation? \$\endgroup\$
    – Lin Ma
    Dec 27 '16 at 2:54
  • 1
    \$\begingroup\$ @LinMa All of the important comments I’d have made are in Janos’s answer, I didn’t feel the need to duplicate. \$\endgroup\$
    – alexwlchan
    Dec 27 '16 at 9:00
1
\$\begingroup\$

Code style advice:

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

def check_match(source):

Repeating the delimiters like that is error-prone if you or someone else wants to change them later. It's probably better to specify them as one list of open-close pairs and have your function compute the structures needed for scanning:

defaultDelimiters = [('[', ']'), ('(', ')'), ('{', '}')]

def check_match(source, delimiterPairs=defaultDelimiters):
    delimOpens = set(o for o,c in delimiterPairs)
    delimCloseToOpen = dict((c,o) for o,c in delimiterPairs)

Your function body:

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

As pointed out, working_set is an unclear name. Also, the enumerate and the first if aren't needed. Also, as pointed out, the [-1] reference can crash if the stack is empty. This can be avoided by initializing the stack with a sentinel value. Finally, instead of the last if statement you can simply return the boolean value. Putting it all together:

delimStack = ['sentinel']
for c in source :
    if c in delimOpens :
        delimStack.append(c)
    elif c in delimCloseToOpen :
        if delimCloseToOpen[c] != delimStack.pop() :
            return False
return (len(delimStack) == 1)

If performance is important, you could use a regular expression to skip the non-delimiter characters - this would probably be faster than an interpreted loop.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.