Comment "dérécursifier" un programme ?

Version imprimable

Bonjour,
le code ci-dessous me permet d'élargir les possibilités de la méthode split. L'emploi de la récursivité rend les choses immédiates à programmer.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#!/usr/bin/env python
#coding=utf-8
 
def findValues(stringToAnalyse, theSeparators, cleanSpaces = False):
    """
    If stringToAnalyse = "p_1 ; p_2 ; p_3 | r_1 ; r_2 | s"
    and theSeparators = ["|", ";"] then
    the following list will be returned :
 
            [ ['p_1', 'p_2', 'p_3'],
              ['r_1', 'r_2'],
              ['s'] ]
 
    theSeparators must be sorted from the first to find to the last to find.
    """
    if not theSeparators:
        if cleanSpaces:
            stringToAnalyse = stringToAnalyse.strip()
 
        return stringToAnalyse
 
    answer = []
 
    actualSeparator = theSeparators[0]
    remainingSeparators = theSeparators[1:]
 
    piecesOfText = stringToAnalyse.split(actualSeparator)
 
    for onePiece in piecesOfText:
        answer.append( findValues(onePiece, remainingSeparators, cleanSpaces) )
 
    return answer
 
 
################
# LITLLE TESTS #
################
 
if __name__ == '__main__':
    tests = []
 
    tests.append( [ "    p_1    ;  p_2     ;   p_3     |      r_1   ;    r_2     |   s     ", ["|", ";"] ] )
    tests.append( [ "p_1 ; p_2, P-II ; p_3 | r_1 ; r_2 | s", ["|", ";", ","] ] )
    tests.append( [ "p_1 ; p_2, P-II ; p_3", [";"] ] )
 
    for oneTest in tests:
        print '-'*40
        print oneTest[0]
        print findValues(oneTest[0], oneTest[1], cleanSpaces = True)

Je voudrais malgré tout, par simple curiosité, voir comment on pourrait obtenir le même type de fonctionnalité sans utiliser la récursivité. Le nombre de séparateurs est inconnu a priori. Quelqu'un voit-il comment faire ?

Toute info. est la bienvenue.

02/11/2009, 11h17
kango

Salut,

très probablement avec une expression régulière. ou alors une analyse caractère pas caractère de la chaine à traiter qui nécessitera très probablement un volume plus important qu'avec une expression régulière.
02/11/2009, 16h00
aepli

Bonjour,

Pour se passer de la récursivité, il faut reproduire plus ou moins se qui est fait automatiquement lors des appels de fonction. C'est à dire, de gérer soi même la pile des variables.

Ceci peut se faire en itérant des pointeurs (en c par exemple). Avec python, je pencherai plus pour des listes. ;)

Maintenant cela peut être un exercice ardu, aussi s'il n'est pas question de d'espace mémoire insuffisant ou performance trop désastreuse, je ne suis pas sur que cela en vaut la peine ...
Évidemment, si c'est pour la beauté du geste, c'est une toute autre histoire :mouarf:

Salutations.

Pour ma 1ère méthode la récursivité va à merveille et j'ai la flemme de chercher la méthode non récursive. Mais si quelqu'un voit comment faire je suis preneur.

Sinon j'ai fait un sorte de multiSplit qui renvoie une réponse bien différente du 1er code de ce post.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def multiSplit(stringToAnalyse, theSeparators, cleanSpaces = False):
    """
    If stringToAnalyse = "p_1 ; p_2 ; p_3 | r_1 ; r_2 | s"
    and theSeparators = ["|", ";"] then
    the following list will be returned :
            ['p_1', 'p_2', 'p_3', 'r_1', 'r_2', 's']
    """
    if not theSeparators:
        raise ValueError, "theSeparators can't be empty"
 
# WARNING ! We must sort the opening symbolic tags for the longer to the shorter.
    theSeparators.sort(lambda x,y: cmp(-len(x), -len(y)))
 
    answer = []
    actualPieceOfText = ''
    newPiece = False
    i_max = len(stringToAnalyse)
    i = 0
 
    while i < i_max:
        for oneSeparator in theSeparators:
            if stringToAnalyse[i: i+len(oneSeparator)] == oneSeparator:
                if cleanSpaces:
                    actualPieceOfText = actualPieceOfText.strip()
                answer.append(actualPieceOfText)
                i += len(oneSeparator)
                actualPieceOfText = ''
                newPiece = True
                break
 
        if newPiece:
            newPiece = False
        else:
            actualPieceOfText += stringToAnalyse[i]
            i += 1
 
    if actualPieceOfText:
        if cleanSpaces:
            actualPieceOfText = actualPieceOfText.strip()
        answer.append(actualPieceOfText)
 
    return answer

Et là la méthode non récursive me vient immédiatement à l'esprit.