What python code generates all possible groupings (trees) for binary operators

Question

As explained in several SO questions and more abstractly at mathworld , a sequence of Catalan numbers corresponds to the number of brackets that can be generated for any given number of operators. But I did not find an algorithm to generate all these groups.

This binary bracketing algorithm follows Tamari Lattice and can be described in several ways. The most obvious practical application of this algorithm is the generation of all possible expressions by all possible brackets around binary operators and the numbers on which they work. This can be used to exhaustively test various types of binary tree operations.

A web search revealed one implementation in C # , but I think it would take me some time to understand, since I don't know the C # syntax.

So, what python code generates all possible groupings of parentheses around statements (which, thus, can be used with the actual expression to generate all the possibilities)? The result will look like this for 2, 3, and 4:

AllBinaryTrees (2)

• (x (xx))
• ((xx) x)

AllBinaryTrees (3)

• (((xx) x) x)
• ((x (xx)) x)
• ((xx) (xx))
• (x ((xx) x))
• (x (x (xx)))

AllBinaryTrees (4)

• (x (x (x (xx))))
• (x (x ((xx) x)))
• (x ((xx) (xx)))
• (x ((x (xx)) x))
• (x (((xx) x) x))
• ((xx) (x (xx)))
• ((xx) ((xx) x))
• ((x (xx)) (xx))
• (((xx) x) (xx))
• ((x (x (xx))) x)
• ((x ((xx) x)) x)
• (((xx) (xx)) x)
• (((x (xx)) x) x)
• (((((xx) x) x) x)

Even better would be code that would do something like the following:

AllBinaryTrees ("2 + 3/4")

output:

• 2+ (3/4)
• (2 + 3) / 4

Answer 1

What about

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) 

Sample Usage:

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

Output:

 (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

The accepted answer only works for single-digit numbers, and I will leave it as the accepted answer, because it illustrates the concept in a readable way. This modified, messy looking version works for all numbers, not just numbers:

 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 

Sample Usage:

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

Output:

 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