It seems to me that you are going to have to approach this problem with algorithmic logic that goes beyond the simple use of regular expressions. You are actually parsing this string, and therefore I would consider using a parse-engine ... say Parse::RecDescent a Perl front-end wrapper for a “real, and advanced,” non-recursive parser. (This problem does not permit a recursive-descent solution ... see below.)
From a grammar point-of-view, your input strings consist of “identifiers,” being fixed literal strings such as u, a, d, b, c, and productions, such as e. Thus, a grammar for this .. abstractly speaking .. might go something like this:
e ::= 'u'
| 'u' 'a' <e>
| <e> 'd' <e> 'f' <e>
| <e> 'b' <e>
| <e> 'c'
... with the fact that the last three rules are
“head recursive being a very-serious problem that would immediately exclude the use of many parsers. (If a production begins with an instance of itself, the parser falls down a rabbit-hole and never comes out, if it attempts a “depth-first” approach as many parsers do. Some parsers such as Bison provide convoluted means for parsing head-recursive grammars but they are difficult compromises.
It also seems to me that this definition, however expressed, will have a lot of potential for ambiguity: there could be many valid parses of the same string.
Certainly, the use of a parser algorithm is called-for here, of some sort. Quietly give-up on the notion of trying to do this with regex calisthenics. And, also, give up on the notion that you will be able to efficiently solve this with “only a screwdriver.”
