General - Looks like a tree walking problem ... and it is not.

To solve this nicely you need to know/understand named capturing groups in regex. And you need to know that you can ignore the definitions of the named groups with (?(DEFINE)...).

The regex to solve the test case looks like this ...

^ (?(DEFINE) (?Pr4a) (?Pr5b) (?Pr3((?P>r4)(?P>r5))|((?P>r5)(?P>r4))) (?Pr2((?P>r4)(?P>r4))|((?P>r5)(?P>r5))) (?Pr1((?P>r2)(?P>r3))|((?P>r3)(?P>r2))) (?Pr0((?P>r4)(?P>r1)(?P>r5))) (?Pr0((?P>r4)(?P>r1)(?P>r5))) ) (?P>r0) $

It (recursively) defines named groups and is then checking if r0 is matching the given string.

Part 1 - Go through all messages, match them against the regex and count the number of matches.

Part 2 - There was nothing to do. The implementation for part1 solves part2 (just added some/the testcases).