parsing - Building a binary tree from a recursively defined string notation -

parsing - Building a binary tree from a recursively defined string notation -

i've been struggling several hours now, after googling incessantly , finding little go on, decided see kind of help might offer me on piece of latest cs hw.

our assignment read in , store binary trees, given in format this: ( (root) (left_subtree) (right_subtree))

each set of matching parens represents tree, first thing root, next left subtree, , right subtree. subtree doesn't need surrounded parens if it's leaf, can be. clarify mean that, see next examples, valid representations of tree pictured below code block.

(a b c) (a (b) c) (a b (c)) ((a) (b) (c))

for more complex illustration illustrates recursive nature of definition bit better, 1 possible string next tree be:

(f(b (d c e)) (g () (i (h))))

note that, in right subtree of f [i.e. "(g () (i (h)))"], "()" necessary after g denote empty left kid - note right subtree of g ["(i (h))"] have been represented more "(i h)".

i have binary tree class (and matching treenode class) completed except essential function build tree input, can't seem wrap head around how parse string. have general thought of how - @ least, how recursion works - how go breaking downwards problem smaller parts going on head.

//pseudocode musings treenode* tree::buildfromstring(string s){ treenode* temp = null if ( string doesn't represent empty tree ) temp = new treenode temp->data = part of s representing root temp->leftchild = buildfromstring( part of s representing left subtree) temp->rightchild = same above, right subtree } homecoming temp;

i'm not having problem recursion per se -- makes sense, it's not hard trace in head. base of operations case works - kick out of recursion , head calls 1 time reach leaf node, linking subtrees go back.

but can't figure out how break problem downwards smaller pieces in code, whole point of recursion. want create substrings of original pass recursive calls, can't seem wrap head around how appropriate pieces.

got ideas?

you right, missing is:

if string starts '(', starts tree, next 'a' root if is, e.g., 'b', leaf if '(', recurse if next ')', close off node started above

string parsing recursion tree binary-tree