Extract balanced parantheses from String

[Vaibhav]

Hi community,

I am getting back to work on LabVIEW after long.

Currently implementing an algorithm and I need to work with tree like structures presented in the form of strings with parantheses.

So, for example, a string such as A(B(c,d),P(q,r),U(V(w),X(y,z,o))) has a tree with root node A, and there are three children of A, namely B, P, U, and all of them also represent a tree (sub-tree of the original tree A). So that, B is the root of the sub-tree where c and d are the two nodes. U also has two children that represent individual sub-trees, namely V (with one child) and X (with three children).

Although, there is one detail, which may actually help the process a bit. The trees are simplified, so that all the nodes that represent some tree (or sub-tree) are just called S.

To extract all these trees, I am going to check one element at a time and then build the sub-trees one by one.

Just thought to ask here if someone has a better idea (or if some function from OpenG may help here if someone has done something similar). Always ready to learn!

Thanks ahead!

[Darin.K]

A little RegExercise for the morning:

No time to expound on the limitations of finite state automata, but this limited use can be handled by the recursive capabilities of pcre.  If you start trying to anchor the regex or match more than the portion enclosed in parentheses then you are in trouble and will need something like the .NET regex framework.   Or wuss out and simply use a while loop to count opening and closing parentheses.

[Vaibhav]

Thanks Darin for the quick reply.

Yes, thought about Regular Expression as one fast way to do it. But I think I was not very elaborative in what I need as an output.

For example, for an input string such as

S(S(a,b),S(S(S(a,S(a,b)),+,S(c))))

The output could be an array like this with each element as one of the sub-trees.

S(S(a,b),S(S(S(a,S(a,b)),+,S(c))))  (the tree itself)

S(a,b)

S(S(S(a,S(a,b)),+,S(c)))

S(S(a,S(a,b)),+,S(c))

S(a,S(a,b))

S(a,b)  (repeats are allowed)

S(c)

Even if I extract these sub-trees with Reg-Ex, I will need to put extra check if the parentheses are paired (and not missing any opening or closing). I cannot simply count the number of "(" against the number of ")", because the user might also type ")(" which is invalid but will give the same number of "(" and ")".

So I think it'll be better to go char by char.

Once I implement, I will post here, but was curious, in the meantime, if there's a better way to do it.

[Vaibhav]

Ok, I just finished the function to validate the input string, extract all the valid sub-trees and list them.

The VI and the required Sub-VI are in the attachment.

This is just to show what output do I need. Any suggestions to improvements are most welcome. 🙂

And if someone finds this solution as useful, I would appreciate acknowledgement of that too (Kudos :P).

But my main objective is to know how this could be done in a smarter way.

Try to play with the function with different valid and invalid tree automata strings. Be careful with the root symbol.

In the above post I used "S" as the root symbol, and in the VI, I am using "X" by default. So just change either of them.

Try for example,

X(a,b)     - valid  - 1 tree

X(X(a,b))     - valid - 2 sub-trees

X((a,b))     - invalid

X(a,b))     - invalid

X(X(a,b)     - invalid

X(X(a),  X(X(b)),X(c,X(d )) )     - valid (it will remove the unnecessary spaces that the user might add mistakenly) - 6 sub-trees.

Could I get these results through regular expressions?

Remark: I didn't put small checks like if the user gives a multi-char string as the Root symbol or things like that, just to implement quickly. I assume the user will not make deliberate mistakes like this.

In the front panel of the main VI (Validate and Extract Sub-trees.VI), you may ignore the array A2, as it was mainly for my debugging purposes. The array A2 is filled while the program runs, and you may see my logic in those cells. But ignore otherwise.

Cheers!

[Edited 03/24/2014: Attachment with private information removed at poster's request]

[Vaibhav]

Sorry friends,

I had to ask for the removal of the program, as it is part of my ongoing PhD work so could not keep it completely open yet. Nevertheless, if somebody is interested in seeing the implementation, please write to me and I can send the VI.

But here I am uploading the program exe to show the output I need.