Oops, massive overlap, looks like a whole conversation went on while I was typing. (.*)$/(.*)$
#1 Oh, dear. No 500-class error? No, I guess it would just be a silent failure: RegEx error, not Apache error. You can only have one $ because it means "the end of the entire string". Here you don't even need or want
one $ sign, because you'll be capturing the last part of the string. By default, a regular expression goes on for as long as it can; you don't have to tell it to continue until the end.
#2 You certainly don't want .* because that would permit a null string. And if you're really getting requests for
/directory//morestuff
-- which I sure hope you're not --you don't want to redirect them. (Matter of fact your server may not even perceive // as two directory slashes, but that is neither here nor there.)
#3 You don't want .+ either, because the whole point is to stop at each directory boundary. The usual pattern is
^[^/]+/[^/]+/
But if all your directory names just use plain text, you can say \w or [a-z] instead. I find it easier to read; you may not care. I'll say \w from here on, assuming none of the directory names contain hyphens. (The shorthand \w covers alphanumerics and lowlines but not hyphens.)
#4 You don't need to capture the two directory names, because you won't be reusing them. You
do need to capture the filename. But not all of the filename, since you're concurrently going extensionless. So now we're as far as
^\w+/\w+/([^./]+)\.php
Can't use \w here since your examples show that you do use hyphens. But can I please assume that your filenames don't contain literal periods other than the extension delimiter? (Periods are bad enough in directory names. In filenames they're hell.) You can leave off the closing anchor, because if there
is extraneous garbage after the ".php" you may as well get rid of it in the same redirect.
#5 Always include the full protocol-plus-domain in a rewrite target, in case someone typed-in the wrong form of your domain name-- or a search engine intentionally asked for the wrong name to see what happens.
#6 [NC] is very seldom appropriate. Easy to type, but more work for the server. Here there's no reason at all for it.
So putting it all together
RewriteRule ^\w+/\w+/([^./]+)\.php http://www.example.com/shop/$1 [R=301,L]
But wait. Are you really redirecting absolutely every single php URL on your entire site, in all directories everywhere, so long as the directories are nested two deep? I can't help but feel that what you're really looking at is something more like
^(?:men|women|children|pets)/\w+/([^./]+)\.php
where the ?: means "we're not capturing this bit, so we don't have to keep count of $1 and $2 later".