# What is a convenient way to convert a string of balanced parentheses to a corresponding “multiplication ordering” or rooted binary tree?

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?

-
Can't you just reverse the construction? – Yuval Filmus Jan 5 '11 at 7:15