patternpythonMinor
Check if all of the delimiters in an expression are matched and closed
Viewed 0 times
expressionthematchedallareclosedandcheckdelimiters
Problem
Problem
Write an algorithm to determine if all of the delimiters in an
expression are matched and closed.
Any advice of code functional bug, performance in terms of algorithm time complexity, code style are appreciated.
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 failAny 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
it would be better to make
The
Creating lists and maps of characters
This is a PITA to type:
An easier and less error-prone way is to call
If it's a stack, call it a stack
And you're using it as a stack, so I suggest to call it a
Use doctests
Doctests are awesome. You can run them with
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.