Batch reordering of filenames?

Hi,

I have a ton of files that I need to reorder the names of as well as adding a leading zero if it's not there and converting all spaces to underscores. Unfortunately, the filenames are not consistent as far as the number of characters per "section." For example, three files look like this:

1. Ballet Rehearsal-Edgar Degas.tif
5. Two Sisters - On the Terrace-Renoir Pierre-August.tif
33. Shot Marilyns-Andy Warhol.tif


What I would need them to be out put as is:

01_Degas_Edgar-Ballet_Rehearsal.tif
05_Renoir_Pierre-August-Two Sisters_On_the_Terrace.tif
33_Warhol_Andy-Shot_Marilyns.tif

Thanks!