Parenthesis matching in Python

Great language though it is, Python code can lead to statements with many, deeply-nested parentheses. Here's a little program with two functions to check that the parentheses in a string match and to find the locations of the matching parentheses.

check_parentheses works by simply keeping a counter of the number of open parentheses, j, which (reading "left to right") is incremented whenever an open parenthesis is encountered and decremented whenever a closed parenthesis is encountered. By the end of the string, j should equal zero if the parentheses are balanced (every open parenthesis has a matching close parenthesis).

find_parentheses uses a stack, implemented as a Python list: this is a "last in, first out" (LIFO) data structure. The index of each open parenthesis encountered is placed on top of the stack (appended to the list); each close parenthesis triggers a pop from the top of the stack: an index is removed from the end of the list. If this operation fails because the stack is empty, it is because there are too many close parentheses (no corresponding open parenthesis was previously placed on the stack). Moreover, if the stack isn't empty after parsing the entire string, it is because there are too many open parentheses (which never got popped off the stack).

def check_parentheses(s):
    """ Return True if the parentheses in string s match, otherwise False. """
    j = 0
    for c in s:
        if c == ')':
            j -= 1
            if j < 0:
                return False
        elif c == '(':
            j += 1
    return j == 0

def find_parentheses(s):
    """ Find and return the location of the matching parentheses pairs in s.

    Given a string, s, return a dictionary of start: end pairs giving the
    indexes of the matching parentheses in s. Suitable exceptions are
    raised if s contains unbalanced parentheses.

    """

    # The indexes of the open parentheses are stored in a stack, implemented
    # as a list

    stack = []
    parentheses_locs = {}
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        elif c == ')':
            try:
                parentheses_locs[stack.pop()] = i
            except IndexError:
                raise IndexError('Too many close parentheses at index {}'
                                                                .format(i))
    if stack:
        raise IndexError('No matching close parenthesis to open parenthesis '
                         'at index {}'.format(stack.pop()))
    return parentheses_locs

test_strings = [
    'as (adjks) sdj(ds(dfsf)) fdd(dsd(dsdss(1))dsds)ddsd',
    'as (adjks) sdj(ds(dfsf) fdd(dsd(dsdss(1))dsds)ddsd',
    'as (adjks) sdj(ds(dfsf)) fdd)(dsd(dsdss(1))dsds)ddsd',
]

for i, s in enumerate(test_strings, start=1):
    print('\ntest string {}:\n{}'.format(i, s))
    print('Parentheses match?', check_parentheses(s))
    try:
        parentheses_locs = find_parentheses(s)
        print('Parentheses locations:\n{}'.format(str(
                    sorted([(k,v) for k, v in parentheses_locs.items()])
           )))
    except IndexError as e:
        print(str(e))

test string 1:
as (adjks) sdj(ds(dfsf)) fdd(dsd(dsdss(1))dsds)ddsd
Parentheses match? True
Parentheses locations:
[(3, 9), (14, 23), (17, 22), (28, 46), (32, 41), (38, 40)]

test string 2:
as (adjks) sdj(ds(dfsf) fdd(dsd(dsdss(1))dsds)ddsd
Parentheses match? False
No matching close parenthesis to open parenthesis at index 14

test string 3:
as (adjks) sdj(ds(dfsf)) fdd)(dsd(dsdss(1))dsds)ddsd
Parentheses match? False
Too many close parentheses at index 28

Comments

Comments are pre-moderated. Please be patient and your comment will appear soon.

Somnath Mahato 8 years, 4 months ago

Sir I am learning python if you can help me with the algorithm
of this program.

Link | Reply

Current rating: 4.2

christian 8 years, 4 months ago

Hey Somnath,
I've added some explanation to the top of this post I hope you find useful.
Best wishes,
Christian

Current rating: 4.8

Ondrej 6 years, 5 months ago

def check_parentheses(s):
""" Return True if the parentheses in string s match, otherwise False. """
return s.count('(') == s.count(')')

Current rating: 5

christian 6 years, 5 months ago

Hi Ondrej,
Your code would check that there are the same number of open- and close-parentheses, but not that they match: e.g. it would return True for ')a + b )- c(('.

Ani Chari 4 years, 8 months ago

I think something like this will work too.

# Here we parse the args char by char
def is_paren_matched(string):
paren_map = {'}': '{', ')': '(', ']': '['}
stack = []
for c in string:
# If we see a paren opener
if c in paren_map.values():
stack.append(c)
# If we see a paren closer
if c in paren_map.keys() and \
(not len(stack) or paren_map[c] != stack.pop()):
return False
return len(stack) == 0