separate string into contents in parentheses vs brackets vs flat text

Question

I need a way to, give a string of text in python, separate its contents into a list, splitting by 3 parameters - outermost brackets versus outermost parentheses versus normal text, preserving the original syntax.

For example, given a string

(([a] b) c ) [d] (e) f

The expected output would be this list:

['(([a] b) c )', '[d]', '(e)', ' f']

I tried several things with regex, such as

\[.+?\]|\(.+?\)|[\w+ ?]+

which gave me

>>> re.findall(r'\[.+?\]|\(.+?\)|[\w+ ?]+', '(([a] b) c ) [d] (e) f')
['(([a] b)', ' c ', ' ', '[d]', ' ', '(e)', ' f']

(item c in the wrong list)

I also tried the greedy version of it,

\[.+\]|\(.+\)|[\w+ ?]+

but it falls short when the string has separate operators of the same kind:

>>> re.findall(r'\[.+\]|\(.+\)|[\w+ ?]+', '(([a] b) c ) [d] (e) f')
['(([a] b) c ) [d] (e)', ' f']

Then I moved on from regex to use stacks instead:

>>> def parenthetic_contents(string):
    stack = []
    for i, c in enumerate(string):
        if c == '(' or c == '[':
            stack.append(i)
        elif (c == ')' or c == ']'):
            start = stack.pop()
            yield (len(stack), string[start + 0:i+1])

Which worked great, for brackets and parentheses, except I have no way of getting the flat text (or I do, but I don't know about it?):

>>> list(parenthetic_contents('(([a] b) c ) [d] (e) f'))
[(2, '[a]'), (1, '([a] b)'), (0, '(([a] b) c )'), (0, '[d]'), (0, '(e)')]

I am not familiar with pyparsing. It looked at first as if nestedExpr() would do the trick, but it takes only one delimiter (() or [], but not both), which wouldn't work for me.

I am all out of ideas now. Any suggestions would be welcome.

Answer 1

Only very lightly tested (and the output includes white space). As with @Marius' answer (and the general rule about paren matching requiring a PDA), I use a stack. However, I have a little extra paranoia built in to mine.

def paren_matcher(string, opens, closes):
    """Yield (in order) the parts of a string that are contained
    in matching parentheses.  That is, upon encounting an "open
    parenthesis" character (one in <opens>), we require a
    corresponding "close parenthesis" character (the corresponding
    one from <closes>) to close it.

    If there are embedded <open>s they increment the count and
    also require corresponding <close>s.  If an <open> is closed
    by the wrong <close>, we raise a ValueError.
    """
    stack = []
    if len(opens) != len(closes):
        raise TypeError("opens and closes must have the same length")
    # could make sure that no closes[i] is present in opens, but
    # won't bother here...

    result = []
    for char in string:
        # If it's an open parenthesis, push corresponding closer onto stack.
        pos = opens.find(char)
        if pos >= 0:
            if result and not stack: # yield accumulated pre-paren stuff
               yield ''.join(result)
               result = []
            result.append(char)
            stack.append(closes[pos])
            continue
        result.append(char)
        # If it's a close parenthesis, match it up.
        pos = closes.find(char)
        if pos >= 0:
            if not stack or stack[-1] != char:
                raise ValueError("unbalanced parentheses: %s" %
                    ''.join(result))
            stack.pop()
            if not stack: # final paren closed
                yield ''.join(result)
                result = []
    if stack:
        raise ValueError("unclosed parentheses: %s" % ''.join(result))
    if result:
        yield ''.join(result)

print list(paren_matcher('(([a] b) c ) [d] (e) f', '([', ')]'))
print list(paren_matcher('foo (bar (baz))', '(', ')'))

Answer 2

I managed to do this using a simple parser that keeps track of how deep you are in the stack using the level variable.

import string

def get_string_items(s):
    in_object = False
    level = 0
    current_item = ''
    for char in s:
        if char in string.ascii_letters:
            current_item += char
            continue
        if not in_object:
            if char == ' ':
                continue
        if char in ('(', '['):
            in_object = True
            level += 1
        elif char in (')', ']'):
            level -= 1
        current_item += char
        if level == 0:
            yield current_item
            current_item = ''
            in_object = False
    yield current_item

Output:

list(get_string_items(s))
Out[4]: ['(([a] b) c )', '[d]', '(e)', 'f']
list(get_string_items('(hi | hello) world'))
Out[12]: ['(hi | hello)', 'world']

Answer 3

You can still use nestedExpr, you want to create several expressions, one with each kind of delimiter:

from pyparsing import nestedExpr, Word, printables, quotedString, OneOrMore

parenList = nestedExpr('(', ')')
brackList = nestedExpr('[', ']')
printableWord = Word(printables, excludeChars="()[]")

expr = OneOrMore(parenList | brackList | quotedString | printableWord)

sample = """(([a] b) c ")" ) [d] (e) f "(a quoted) [string] with ()'s" """

import pprint
pprint.pprint(expr.parseString(sample).asList())

prints:

[[['[a]', 'b'], 'c', '")"'],
 ['d'],
 ['e'],
 'f',
 '"(a quoted) [string] with ()\'s"']

Notice that by default, nestedExpr returns the parsed contents in a nested structure. To preserve the original text, wrap the expressions in originalTextFor:

# preserve nested expressions as their original strings
from pyparsing import originalTextFor
parenList = originalTextFor(parenList)
brackList = originalTextFor(brackList)

expr = OneOrMore(parenList | brackList | quotedString | printableWord)

pprint.pprint(expr.parseString(sample).asList())

prints:

['(([a] b) c ")" )', '[d]', '(e)', 'f', '"(a quoted) [string] with ()\'s"']

Answer 4

Well, once you abandon the idea that parsing nested expressions should work at unlimited depth, one can use regular expressions just fine by specifying a maximum depth in advance. Here is how:

def nested_matcher (n):
    # poor man's matched paren scanning, gives up after n+1 levels.
    # Matches any string with balanced parens or brackets inside; add
    # the outer parens yourself if needed.  Nongreedy.  Does not
    # distinguish parens and brackets as that would cause the
    # expression to grow exponentially rather than linearly in size.
    return "[^][()]*?(?:[([]"*n+"[^][()]*?"+"[])][^][()]*?)*?"*n

import re

p = re.compile('[^][()]+|[([]' + nested_matcher(10) + '[])]')
print p.findall('(([a] b) c ) [d] (e) f')

This will output

['(([a] b) c )', ' ', '[d]', ' ', '(e)', ' f']

Which is not quite what you stated above, but then your description and example did not really make explicit what you intend to do with spaces.