language agnostic - Using regex to add leading zeroes

Question

I would like to add a certain number of leading zeroes (say up to 3) to all numbers of a string. For example:

Input: /2009/5/song 01 of 12

Output: /2009/0005/song 0001 of 0012

What's the best way to do this with regular expressions?

Edit:

I picked the first correct answer. However, all answers are worth giving a read.

Answer 1

In Perl:

s/([0-9]+)/sprintf('%04d',$1)/ge;