The parenthesis flattening rules could be a little clearer. In fact,

    parse_regexp('(((a)bc))d') == parse_regexp('(abc)d')
    parse_regexp('(abcd)') == parse_regexp('abcd')
    parse_regexp('(abc)d') != parse_regexp('abcd')

The rule seems to be: The argument of a Str object must contain at least 2 elements.

• Str([regex]) should be replaced by regex.

Please use spoiler flag, comments are visible from the dashboard. I added it for you this time.

doesn't seem to be covered in the spec - is a** a valid regex term here?

edit: I'm illiterate, that's one of their example invalid terms

nub in your solution has pitiful perfomance.

I implemented something similar but with array indexes. Didn't know about first and last. Awesome solution!

in c++, how do I do it without the definition of RegExp or the helper functions?

I don't think this behavior still occurs. Random tests have been updated some while ago. Is this still an issue?

The adjustment method mentioned above is no longer required as random tests have been cleaned up (already 2 years ago).
Unfortunately, the instructions remain unclear and incorrect method signatures are provided in the description.

Once I figured out a key concept, how and when to use Str and Add, I managed to pass it in C# without much trouble.
The fact the description mentions "Exp", though in some occasions more specifically requires "Str" doesn't help :s
However, the "core" example test shows how to use these classes. Let's say you have "abcd" (a sequence of 4 x normal). This should be treated as a fold of Add with the seed being the first list item wrapped with Str: Add(Add(Add(Str(a),b),c),d).

Nope, issue with your code very likely ~~

I know the test cases don't cover it, but what if at least one of them was 0? ;-)

Yeah yours is instant (278 ms including starting the python interpreter, running the python test code, http, de/serialization)

My solution should be not very slow. Could you test it?

The haskell reference solution takes minutes to pass the python tests - the performance requirements are very different.
(the haskell reference, and presumably many submitted solutions, including my own, choke on nested expressions, presumably they end up doing a bunch of horrific backtracking - can they (parser combinator solutions) be written to be fast?)