well formed parentheses to .dot file

[szakos]

Hi all,

I want to generate a .dot file (to graphwiz) from well formed paretheses, but haven't figured yet how can I convert them.
example:

1  2  3  4  5  6
(  (   )  (   )  )
1  1  0  1  0  0
 
     1
    / \
   2  *7
  / \
*3  4
    /  \
  *5  *6

1  2  3  4  5  6
(  (   )  (   )  )
1  1  0  1  0  0

     1
    / \
   2  *7
  / \
*3  4
    /  \
  *5  *6

To copy to clipboard, switch view to plain text mode 

So the '('s mean 1s and they are nodes. ')' mean 0s and they are leaves. The order is preorder, if i am not wrong.
My question is, how create from 1100100 to 1--2, 2--*3, 2--4, 4--*5, 4--*6, 1--*7.
I see the left connections but not the right ones. Left (i,i+1), if i==1.

[DanH]

I predict that the answer will involve recursion.

But I don't really understand your example. Your tree contains 4 leaves, but line 3 contains only 3 zeros.

[szakos]

Sorry, I forgot to mention, the well formed parentheses form doesn't contain the last leaf. In this example *7 is the additional leaf.
and this is a typo: "My question is, how create from 1100100 to .." it is "...from 110100 to.."

[DanH]

Well, let's see. For this simple case, when you see a "(" you create a node, link it to the prior node, and make it the new "prior" node. When you see a ")" you create a leaf node, link it to the "prior" node, but don't make it the new "prior" node.

But I'm not sure that algorithm works for more complex cases.