Quale codice python genera tutti i possibili raggruppamenti (alberi) per gli operatori binari

Question

Come spiegato in diverse domande SO, e in modo più astratto a mathworld, la sequenza di numeri catalani corrisponde al numero di raggruppamenti parentesi che possono essere generati per qualsiasi dato numero di operatori. Ma non ho trovato un algoritmo per generare tutti questi raggruppamenti.

Questo algoritmo di bracketing binario corrisponde allo Tamari Lattice e può essere descritto in diversi modi. L'uso pratico più ovvio per questo algoritmo è generare tutte le possibili espressioni da ogni possibile parentesi attorno agli operatori binari e ai numeri su cui operano. Questo può essere usato per testare esaustivamente vari tipi di operazioni su alberi binari.

La ricerca sul Web ha rivelato one implementation in C# ma penso che mi ci vorrà un po 'per capire come non conosco la sintassi C#.

Quindi, quale codice Python genera tutti i possibili raggruppamenti di parentesi attorno agli operatori (che possono quindi essere utilizzati con un'espressione reale per generare tutte le possibilità)?Uscita apparirebbe come segue per 2, 3, e 4:

AllBinaryTrees (2)

1. (x (xx))
2. ((xx) x)

AllBinaryTrees (3)

1. (((xx) x) x)
2. ((x (xx)) x)
3. ((xx) (xx))
4. (x ((xx) x))
5. (x (x (xx)))

AllBinaryTrees (4)

1. (x (x (x (xx))))
2. (x (x ((xx) x)))
3. (x ((xx) (xx)))
4. (x ((x (xx)) x))
5. (x (((xx) x) x))
6. ((xx) (x (xx)))
7. ((xx) ((xx) x))
8. ((x (xx)) (xx))
9. (((xx) x) (xx))
10. ((x (x (xx))) x)
11. ((x ((xx) x)) x)
12. (((xx) (xx)) x)
13. (((x (xx)) x) x)
14. ((((xx) x) x) x)

012.351.

Ancora meglio sarebbe codice che ha fatto qualcosa di simile al seguente:

AllBinaryTrees ("2 + 3/4")

uscita:

1. 2+ (3/4)
2. (2 + 3)/4

Answer 1

Come su

def allbinarytrees(s): 
    if len(s) == 1: 
     yield s 
    else: 
     for i in range(1, len(s), 2): 
      for l in allbinarytrees(s[:i]): 
       for r in allbinarytrees(s[i+1:]): 
        yield '({}{}{})'.format(l, s[i], r) 

utilizzo Esempio:

for t in allbinarytrees('1+2-3*4/5'): 
    print(t) 

uscita:

(1+(2-(3*(4/5)))) 
(1+(2-((3*4)/5))) 
(1+((2-3)*(4/5))) 
(1+((2-(3*4))/5)) 
(1+(((2-3)*4)/5)) 
((1+2)-(3*(4/5))) 
((1+2)-((3*4)/5)) 
((1+(2-3))*(4/5)) 
(((1+2)-3)*(4/5)) 
((1+(2-(3*4)))/5) 
((1+((2-3)*4))/5) 
(((1+2)-(3*4))/5) 
(((1+(2-3))*4)/5) 
((((1+2)-3)*4)/5) 

Answer 2

La risposta accettata funziona solo per i numeri a cifra singola, ed andrò come risposta accettata perché illustra il concetto in un facile leggere la moda.Questo, Messier guardando versione modificata funziona per tutti i numeri, non solo singole cifre: l'utilizzo

def allbinarytrees(s): 
    if s.isdigit(): 
     yield s 
    else: 
     i = 0 
     while i < len(s)-1: 
      while i < len(s) and s[i].isdigit(): 
       i += 1 
      if i < len(s) - 1: 
       for left in allbinarytrees(s[:i]): 
        for right in allbinarytrees(s[i+1:]): 
         yield '({}{}{})'.format(left, s[i], right) 
      i += 1 

Esempio:

j=0 
for t in allbinarytrees('11+22*3/4456'): 
    j += 1 
    print j, (t[1:-1]) 

uscita:

1 11+(22*(3/4456)) 
2 11+((22*3)/4456) 
3 (11+22)*(3/4456) 
4 (11+(22*3))/4456 
5 ((11+22)*3)/4456