What a parser did is to tansfer a "plain text" representation of something to a "structured" representation. In this case, the plain text is a String representing regular expression, and the the structured thing is the data structure that has been defined for you.

build the CST (concrete syntax tree)

No issue here: you chose to override the classes in preloaded. They are there for a reason. Don't be surprised you get in undebuggable situations if you actually twist the context in which you're solving the kata.

For instance, your Or.__str__ is different from the one supposedly used.

Keep in mind that the string you see in the assertion messages are stringified versions of your CST. For instance, it seems you're returning Str(Or(...)) for that input while you're supposed to return only Or(...). So your "correct" solution is actually incorrect.

You get the discrepancy between the fixed and random tests because the supposed to be Or class is supposed to stringify itself adding parentheses around itself too. As long as your (inappropriate) definition of Or changes this behavior and that the ref solution uses your (inappropriate) classes to build the CST, the parentheses aren't there anymore in the expected result of the random tests, yes. But that's totally on you. ;)

Closing.

cheers

And I work with C++

Sorry, I have no idea about what i should do with this kata . optimize/check the regular expression?

I think the last character of str can not be compared, and it will be faster a bit ?