String parser for Lie words

[inakleinbottle]

A Lie word is either a single "letter" (i.e. an integer, e.g. 1) or nested brackets containing two previous Lie words (e.g. [1, 2], [1,[2,3]], or [[1, 2], [1, [2,3]]].) Amongst these "words" are some special Hall words that for a basis for the free Lie algebra. For instance, [1,[1,2]] is a Hall word, but [[1,2], 1] is not.

Internally, Lie words and the subclass of Hall words, will be represented by a "flat tree" structure, which is an array containing entries that are either letters (positive) or offsets (negative). In the special case where the array contains a single element, then it represents a letter, otherwise each entry appears as a pair in the ith and (i+1)th place. Brackets are replaced by offsets, which direct from the current position to the pair that appear within those brackets. For example, the Lie word [[1, 2], [1,[2,3]]] is represented in flat tree for as the following array

                     -2    -4    -1    1    2    -1    1    -1    2    3
                      o     o     o    l    l     o    l     o    l    l
                                       ^    ^          ^          ^    ^
                                       |    |          |          |    |
                      +-----------+    |    |          |          |    | 
                                  +----x----x          |          |    |
                                                       |          |    |
                            +---------------------+    |          |    |
                                                  +----x-----+    |    |
                                                             +----x----x

This tree structure has a very desirable property: they are trivially composable. Take two trees, a and b that you wish to combine, Then the tree structure of [a, b] is

-2 -len(a) a... b... 

where a... and b... denotes the expansion of a and b respectively.

This tree structure is semi-represented in RoughPy, currently residing only in the Python interface (roughpy/src/algebra/lie_key.h) but will eventually be moved into the Algebra module to act as keys for sparsely represented free Lie algebra objects. The task then is to parse the strings that contain valid nested brackets and convert this to a flat tree structure. For the moment, I would ignore the actual implementation of Lie key and just worry about the parser, putting the offsets and letters into a vector.