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

Question

As explained in several SO questions, and more abstractly at mathworld, the sequence of Catalan numbers happens to correspond to the number of parenthetical groupings that can be generated for any given number of operators. But I haven't found an algorithm to generate all these groupings.

This binary bracketing algorithm corresponds to the Tamari Lattice and can be described in a number of different ways. The most obvious practical use for this algorithm is to generate all possible expressions by every possible bracketing around binary operators and the numbers they operate on. This can be used to exhaustively test various types of operations on binary trees.

Web searching did reveal one implementation in C# but I think it would take me a while to understand as I don't know C# syntax.

So, what python code generates all the possible groupings of parenthesis around operators (which can thus be used with an actual expression to generate all the possibilities)? Output would look as follows for 2, 3, and 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)

Even better would be code which did something like the following:

AllBinaryTrees("2+3/4")

output:

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

Answer 1

How 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 accepted answer because it illustrates the concept in an easy to read fashion. This modified, messier looking version works for all numbers, not just single digit 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