In an article by Tom Davis on Catalan numbers, Davis mentions several problems that are shown to be equivalent. One of them is the problem of determining the number of strings of $n$ pairs of balanced parentheses. Another is the problem of determining the number of "multiplication orderings" of $n + 1$ numbers. In both cases, the answer to the problem is $C_n$, or the nth Catalan number.
For example, with $n = 3$, there are $C_3 = 5$ different strings of 3 pairs of balanced parentheses:
()()(), ()(()), (())(), (()()), ((()))
With four numbers, there are also $C_3$ multiplication orderings of them:
(((a·b)·c)·d), ((a·b)·(c·d)), ((a·(b·c))·d), (a·((b·c)·d)), (a·(b·(c·d)))
Davis shows how to convert a multiplication ordering of $n + 1$ terms to a string of $n$ pairs of balanced parentheses, but I would like to know how to go the other way; i.e. given a string of $n$ pairs of balanced parentheses, how can I calculate a corresponding multiplication ordering?
Best Answer
Knuth covers this in chapter 7.2.1.6 (vol. 4, fascicle 4) of The Art Of Computer Programming, where he talks about generating all trees (which is an essentially equivalent problem) and converting back and forth between representations. Have a look at http://cs.utsa.edu/~wagner/knuth/fasc4a.pdf for more details.