How to parse a string and return a nested array?

Question

I want a Python function that takes a string, and returns an array, where each item in the array is either a character, or another array of this kind. Nested arrays are marked in the input string by starting with '(' and ending with ')'.

Thus, the function would act like this:

1) foo("abc") == ["a", "b", "c"]
2) foo("a(b)c") == ["a", ["b"], "c"]
3) foo("a(b(c))") == ["a", ["b", ["c"]]]
4) foo("a(b(c)") == error: closing bracket is missing
5) foo("a(b))c") == error: opening bracket is missing
6) foo("a)b(c") == error: opening bracket is missing

Note: I'd prefer a solution that's purely functional.

Use recursion here, it's a perfect fit. Finding a '(' in the token stream means recurse-into. Finding a ')' at the top level invocation means that there is a balance mismatch. — user2246674
– user2246674, Commented Jun 17, 2013 at 5:22
Recursion indeed. As long as the string isn't too long, that is. Please also bear in mind that this might need a wrapper funstion, since we would need to check whether the number of '(' matches the number of ')'. If so, call the recursive function. If not, give appropriate error message. — Truerror
– Truerror, Commented Jun 17, 2013 at 5:41
Yes, I know that I'll use recursion here. I know how to write a function (that uses a stack) that returns whether the brackets in a string are balanced and well-ordered, but it's taking the next step and trying to return nested arrays that stumps me. This isn't homework. This is part of a bigger parsing program. — Tespa42
– Tespa42, Commented Jun 17, 2013 at 6:47

Jared · Accepted Answer · 2013-06-17 06:19:35Z

8

def foo(s):
    def foo_helper(level=0):
        try:
            token = next(tokens)
        except StopIteration:
            if level != 0:
                raise Exception('missing closing paren')
            else:
                return []
        if token == ')':
            if level == 0:
                raise Exception('missing opening paren')
            else:
                return []
        elif token == '(':
            return [foo_helper(level+1)] + foo_helper(level)
        else:
            return [token] + foo_helper(level)
    tokens = iter(s)
    return foo_helper()

And,

>>> foo('a((b(c))d)(e)')
['a', [['b', ['c']], 'd'], ['e']]

answered Jun 17, 2013 at 6:19

Jared

26.5k7 gold badges61 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Tespa42 Over a year ago

Do you wanna try to rewrite this in a functional style?

Jared Over a year ago

@FinalZero What do you mean? This is already a recursive solution.

Tespa42 Over a year ago

I mean in a way that doesn't use iter and next.

Tespa42 Over a year ago

The answer isn't purely functional, but I'll accept it anyways, because it helped me conceptualize and write the purely functional solution, which requires foo to return a tuple instead of just an array.

falsetru · Accepted Answer · 2013-06-17 07:45:59Z

8

Iterative.

def foo(xs):
    stack = [[]]
    for x in xs:
        if x == '(':
            stack[-1].append([])
            stack.append(stack[-1][-1])
        elif x == ')':
            stack.pop()
            if not stack:
                return 'error: opening bracket is missing'
                #raise ValueError('error: opening bracket is missing')
        else:
            stack[-1].append(x)
    if len(stack) > 1:
        return 'error: closing bracket is missing'
        #raise ValueError('error: closing bracket is missing')
    return stack.pop()

assert foo("abc") == ["a", "b", "c"]
assert foo("a(b)c") == ["a", ["b"], "c"]
assert foo("a(b(c))") == ["a", ["b", ["c"]]]
assert foo("a((b(c))d)(e)") == ['a', [['b', ['c']], 'd'], ['e']]
assert foo("a(b(c)") == "error: closing bracket is missing"
assert foo("a(b))c") == "error: opening bracket is missing"
assert foo("a)b(c") == 'error: opening bracket is missing'

edited Jun 17, 2013 at 7:45

answered Jun 17, 2013 at 6:55

falsetru

371k69 gold badges769 silver badges659 bronze badges

1 Comment

FMc Over a year ago

+1 And you don't need result: just set stack = [[]] and then return stack.pop(). Seems more pure that way -- just the stack.

fricke · Accepted Answer · 2013-06-17 05:58:30Z

2

I would suggest two ways:

Either program your own recusive descent parser like here, or use pyparsing, something like

import pyparsing as pp
expr = pp.Forward()
expr << pp.Word(pp.alphas) + pp.Optional('(' + expr + ')') + pp.Optional(pp.Word(pp.alphas))

here you describe a recursive expression as a sequence of alphas, which can be interleaved by balanced parentheses. When you check this example for the outputs you will see how to get the desired output structure (though it will require some tweaking on your side and require some learning about pyparsing).

regards markus

answered Jun 17, 2013 at 5:58

fricke

1,4001 gold badge11 silver badges22 bronze badges

Comments

Ashwini Chaudhary · Accepted Answer · 2013-06-17 07:03:16Z

2

Using regex and ast.literal_eval

>>> import re
>>> from ast import literal_eval
>>> def listit(t):
...         return list(map(listit, t)) if isinstance(t, (list, tuple)) else t
... 
def solve(strs):
    s = re.sub(r'[A-Za-z]', "'\g<0>',", strs)
    s = re.sub(r"\)", "\g<0>,", s)
    try: return listit( literal_eval('[' + s  + ']') )
    except : return "Invalid string! "
...     
>>> solve("abc")
['a', 'b', 'c']
>>> solve("a(b)c")
['a', ['b'], 'c']
>>> solve("a(b(c))")
['a', ['b', ['c']]]
>>> solve("a(b(c)")
'Invalid string! '
>>> solve("a)b(c")
'Invalid string! '
>>> solve("a(b))c")
'Invalid string! '
>>> solve('a((b(c))d)(e)')
['a', [['b', ['c']], 'd'], ['e']]

answered Jun 17, 2013 at 7:03

Ashwini Chaudhary

252k60 gold badges478 silver badges519 bronze badges

Comments

Alex L · Accepted Answer · 2013-06-17 06:54:16Z

One rather quick and nasty approach (just for something different):

import json, re

def foo(x):
    # Split continuous strings
    # Match consecutive characters
    matches = re.findall('[a-z]{2,}', x)
    for m in matches:
        # Join with ","
        x = x.replace(m, '","'.join(y for y in list(m))) 

    # Turn curvy brackets into square brackets
    x = x.replace(')', '"],"')
    x = x.replace('(', '",["')

    # Wrap whole string with square brackets
    x = '["'+x+'"]'

    # Remove empty entries
    x = x.replace('"",', '')
    x = x.replace(',""', '')

    try:
        # Load with JSON
        return json.loads(x)
    except:
        # TODO determine error type
        return "error"

def main():
    print foo("abc")     # ['a', 'b', 'c']
    print foo("a(b)c")   # ['a', ['b'], 'c']
    print foo("a(b(c))") # ['a', ['b', ['c']]]
    print foo("a(b))c")  # error

    print foo('a((b(c))d)(e)') # ['a', [['b', ['c']], 'd'], ['e']]

Janne Karila · Accepted Answer · 2013-06-17 07:00:36Z

1

def parse_nested(iterator, level=0):
    result = []
    for c in iterator:
        if c == '(':
            result.append(parse_nested(iterator, level+1))
        elif c == ')':
            if level:
                return result
            else:
                raise ValueError("Opening parenthesis missing")
        else:
            result.append(c)
    if level:
        raise ValueError("Closing parenthesis missing")
    else:
        return result

print parse_nested(iter('a((b(c))d)(e)'))

answered Jun 17, 2013 at 7:00

Janne Karila

25.3k6 gold badges59 silver badges97 bronze badges

Comments

Harry Wang · Accepted Answer · 2013-06-17 06:29:18Z

0

Recursion is something very powerful that you should try to use.

Here is my code:



    # encoding: utf-8
    # Python33

    def check(s):
        cs = [c for c in s if c == '(' or c ==')']
        flag = 0
        for c in cs:
            if flag < 0:
                return 'opening bracket is missing'        
            if c == '(':
                flag += 1
            else:
                flag -= 1
        if flag < 0:
            return 'opening bracket is missing'
        elif flag > 0:
            return 'closing bracket is missing'
        else:
            return ''

    def _foo(cs):
        result = []
        while len(cs):
            c = cs.pop(0)
            if c == '(':
                result.append(_foo(cs))
            elif c == ')':
                return result
            else:
                result.append(c)
        return result

    def foo(s):
        valiad = check(s)
        if valiad:
            return valiad
        cs = list(s)
        return _foo(cs)

    if __name__ == '__main__':
        ss = ["abc","a(b)c","a(b(c))","a(b(c)","a(b))c","a)b(c"]
        for s in ss:
            print(foo(s))

edited Jun 17, 2013 at 6:29

answered Jun 17, 2013 at 6:05

Harry Wang

851 silver badge7 bronze badges

1 Comment

Harry Wang Over a year ago

My code is ok, but error when display in the answer area... I am trying to fix it._______I replaced the '<' whit '<', and it did work!

Collectives™ on Stack Overflow

How to parse a string and return a nested array?

7 Answers 7

4 Comments

1 Comment

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

4 Comments

1 Comment

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related