Всё, я наконец-то понял, в чём была ошибка.
Когда мы разбираем выражение 3*3*3+1, после первой замены строка имеет вид 9*3+1. Но курсор находится между 9 и *, поэтому скрипт и не может найти 9*3, потому что он его уже прошёл.
В общем-то, так и должно быть. Если бы курсор после замены возвращался бы в начало заменяемого места, то "bbb".replace(/\w/g, "f") давало бы бесконечный цикл. Т.е. b заменился на f, курсор встал перед f, f заменился на f, и так до бесконечности.
Поэтому в 32-ую строку надо было поместить это:
while ( re.test(S) )
Всем спасибо, особенно
B@rmaley.e><e за наводку.