1) Проверять коды символов, если относится к диапазону заглавных - то разделять подчёркиванием
2) Брать каждый символ, и принудительно делать его заглавным, и сравнивать с оригиналом, типа
VB : If char = UCase(char) Then ... Else ... End Id
PHP : if (char == strtoupper(char)) {} else {}
3) Юзать регулярку типа [A-ZА-Я]
a) С модом возврата смещения и по массиву смещений вхождений получаем позицию каждого заглавного символа и воротим что хотим
б) Заменять символ нижний регистр + подчёркивание