In addition to all these more than adequate replies, let me point out there was a discussion about this a while ago that led to both Perl and JavaScript Keyboard Maestro macros. You can specify a regex to parse the existing selected file names and you'll see a preview of the change, which you can sign off on or modify on the fly. I've used the Perl version since.
The prompt (with the regex for your case) would look like this:
And you would see this for confirmation:
