JSON, lists and recursion in python

Question

I am new to Python and have come across a problem I cannot solve.

I have decoded the following parse tree from JSON to the following list.

>>> tree
['S', ['NP', ['DET', 'There']], ['S', ['VP', ['VERB', 'is'], ['VP', ['NP', ['DET', 'no'], ['NOUN', 'asbestos']], ['VP', ['PP', ['ADP', 'in'], ['NP', ['PRON', 'our'], ['NOUN', 'products']]], ['ADVP', ['ADV', 'now']]]]], ['.', '.']]]

Using a recursive function, I have been able to obtain a list containing the terminal words.

def explorer(tree):
    for sub in tree[1:]:
        if(type(sub) == str):
            allwords.append(sub)
        else:
            explorer(sub)

>>> allwords
['There', 'is', 'no', 'asbestos', 'in', 'our', 'products', 'no'.]

Now I need to replace the words that meet some criteria in the original tree, so that I get something like this:

['S', ['NP', ['DET', 'There']], ['S', ['VP', ['VERB', 'is'], ['VP', ['NP', ['DET', 'no'], ['NOUN', '_REPLACED_']], ['VP', ['PP', ['ADP', 'in'], ['NP', ['PRON', 'our'], ['NOUN', 'products']]], ['ADVP', ['ADV', 'now']]]]], ['.', '.']]]

I have tried the following function, but I am unable to propagate the replacements upwards, so I always get the same old original tree.

def replacer(tree):
    string=[]
    for sub in tree[1:]:
        if(type(sub) == str):
            if #'condition is true':
                sub="_REPLACE_"
                return sub
            else: return sub    
        else:
            string.extend(replacer(sub))
    print(string)

I would appreciate some hint in how to achieve the results. Thank you in advance.

@Daniel Roseman Thank you for the edit!

Serge
– Serge

2013-03-31 16:37:37 +00:00
Commented Mar 31, 2013 at 16:37 — Serge
– Serge, Commented Mar 31, 2013 at 16:37

mrKelley · Accepted Answer · 2013-04-05 22:31:41Z

So here is an example of how I use list comprehensions to do this sort of thing. If you don't know, the list comprehension is something = [explorer(x) for x in something]. That's also where the recursion is happening. What you get back is a list of the exact same structure, but you've "been to" every endpoint and can check for and replace things. I did a couple arbitrary replacements.

>>> tree = ['S', ['NP', ['DET', 'There']], ['S', ['VP', ['VERB', 'is'], ['VP', ['NP', ['DET', 'no'], ['NOUN', 'asbestos']], ['VP', ['PP', ['ADP', 'in'], ['NP', ['PRON', 'our'], ['NOUN', 'products']]], ['ADVP', ['ADV', 'now']]]]], ['.', '.']]]
>>> def explorer(something):
        if type(something) == list:
            something = [explorer(x) for x in something]
        else:   # You may want to check other conditions here, like if it's a string
            if something == 'asbestos':
                something = 'Oh my'
            if something == 'S':
                something = 'Z'
        return something

>>> explorer(tree)
['Z', ['NP', ['DET', 'There']], ['Z', ['VP', ['VERB', 'is'], ['VP', ['NP', ['DET', 'no'], ['NOUN', 'Oh my']], ['VP', ['PP', ['ADP', 'in'], ['NP', ['PRON', 'our'], ['NOUN', 'products']]], ['ADVP', ['ADV', 'now']]]]], ['.', '.']]]
>>>

I just noticed something after reading your words more carefully. The reason you are not able to "propagate replacements upwards" is because your loop is structured something like this:

for x in aList:
    if x = somethingSpecial:
        x = somethingElse

That does not work in Python, but this does:

for i,x in enumerate(aList):
    if x = somethingSpecial:
        aList[i] = somethingElse

Now aList has ben modified the way you want. If you don't know what enumerate() does, just copy/paste this:

aList = ['a','b','c']
for i,x in enumerate(aList):
    print(i,x)

David Wolever · Accepted Answer · 2013-03-31 15:09:06Z

2

Your problem is that you are retuning the string in some cases, and printing a list in others. Make sure that your replacer is always returning a list of strings, and you should be fine.

answered Mar 31, 2013 at 15:09

David Wolever

156k94 gold badges365 silver badges513 bronze badges

Comments

Justin O Barber · Accepted Answer · 2013-03-31 15:54:14Z

If I understand your question correctly, one way to solve your question is like this:

 >>> tree = ['S', ['NP', ['DET', 'There']], ['S', ['VP', ['VERB', 'is'], ['VP', ['NP', ['DET', 'no'], ['NOUN', 'asbestos']], ['VP', ['PP', ['ADP', 'in'], ['NP', ['PRON', 'our'], ['NOUN', 'products']]], ['ADVP', ['ADV', 'now']]]]], ['.', '.']]]
 >>> def replacer(tree):
        for i, sub in enumerate(tree[1:]):
            if type(sub) == str and sub == 'asbestos':
                tree[i+1] = '__REPLACE__'
            else:
                replacer(sub)

If you make a change to tree[1:], you are not actually making a change to the list but rather to the splice. So the enumerate function gets you around this issue. Your sub="_REPLACE_" does not actually change the list. It merely assigns a new value to the name sub.

The result:

>>> replacer(tree)
>>> tree
['S', ['NP', ['DET', 'There']], ['S', ['VP', ['VERB', 'is'], ['VP', ['NP', ['DET', 'no'], ['NOUN', '__REPLACE__']], ['VP', ['PP', ['ADP', 'in'], ['NP', ['PRON', 'our'], ['NOUN', 'products']]], ['ADVP', ['ADV', 'now']]]]], ['.', '.']]]

To get a new list like your first function creates, you can simply apply your first function to the new tree list:

>>> explorer(tree)
['There', 'is', 'no', '__REPLACE__', 'in', 'our', 'products', 'now', '.']

Collectives™ on Stack Overflow

JSON, lists and recursion in python

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related