Встретил интересное задание на освоение рекурсии. Требуется написать рекурсивную C-функцию, которая переводит первую букву каждого слова в строке из прописной в заглавную.
Словами считается любой набор символов ограниченный знаками пробела и табуляции.
Наибольшую сложность вызывает написание такой функции без написания дополнительных функций и без использования статических переменных в самой функции.
Должна быть написана единственная функция, объявленная как
char * capitalize( char *s );
В чем именно состоит сложность написания такой функции?
Проблема в том, что при вызове функции неизвестно, предшествовал ли текущему символу строки пробельный символ или нет. А передать такую информацию через, например, аргумент функции, нет возможности, так как единственный параметр функции - это указатель на саму строку.
Теперь прервите здесь чтение этой темы и попробуйте сами самостоятельно написать такую функцию!
Получилось?
А теперь можете ознакомиться с моим решением. Оно не сразу же приходит в голову.
Мы может получить информацию о том. предшествовал ли данному символу пробельный символ при возврате из последующего рекурсивного вызова! Проблема лишь состоит в том, что для самого первого рекурсивного вызова функции нет предшествующего ему вызова.
Что делать?
Выход из положения простой. Надо при каждом рекурсивном вызове функции переводить текущий не пробельный символ из строчной буквы в прописную (заглавную). А при выходе из данного рекурсивного вызова в предшествующий рекурсивный вызов, если в предшествующем рекурсивном вызове текущий символ не пробельный, значит следующий символ в строке нужно из прописной буквы снова сделать строчную букву.
Не совсем понятно?
Ниже представлена демонстрационная программа, из текста которой будет все ясно.
#include <stdio.h>
#include <ctype.h>
char * capitalize( char *s )
{
if ( *s )
{
int blank = isblank( ( unsigned char )*s );
if ( !blank )
{
*s = toupper( ( unsigned char )*s );
}
capitalize( s + 1 );
if ( !blank && !isblank( ( unsigned char )*( s + 1 ) ) && *( s + 1 ) )
{
*( s + 1 ) = tolower( ( unsigned char )*( s + 1 ) );
}
}
return s;
}
int main(void)
{
char s[] = "hello everybody. how do you do?";
puts( s );
puts( capitalize( s ) );
return 0;
}
Вывод программы на консоль:
hello everybody. how do you do?
Hello Everybody. How Do You Do?
Определение функции можно также переписать, к примеру, и следующим альтернативным способом:
char * capitalize( char *s )
{
if ( *s )
{
capitalize( s + 1 );
if ( !isblank( ( unsigned char )*s ) )
{
*s = toupper( ( unsigned char )*s );
if ( *( s + 1 ) && !isblank( ( unsigned char )*( s + 1 ) ) )
{
*( s + 1 ) = tolower( ( unsigned char )*( s + 1 ) );
}
}
}
return s;
}
Теперь облегчим себе задание. Разрешим в функции использовать статическую переменную. Например, эта статическая переменная может содержать индекс текущего символа строки. Зная индекс, мы можем прочитать предшествующий символ по отношению к текущему символу.
Вот как может выглядеть такая функция со статической переменной.
#include <stdio.h>
#include <ctype.h>
char * capitalize( char *s )
{
static size_t i = 0;
if ( *( s + i ) )
{
if ( !isblank( ( unsigned char )*( s + i ) ) &&
( i == 0 || isblank( ( unsigned char )*( s + i - 1 ) ) ) )
{
*( s + i ) = toupper( ( unsigned char )*( s + i ) );
}
++i;
capitalize( s );
--i;
}
return s;
}
int main(void)
{
char s[] = "hello everybody. how do you do?";
puts( s );
puts( capitalize( s ) );
return 0;
}
Вывод программы такой же, как было показано выше:
hello everybody. how do you do?
Hello Everybody. How Do You Do?
Ну, и, наконец, самый простой подход к реализации функции, когда пишется вспомогательная функция, которая и является рекурсивной, а функция с одним параметром является оберткой к ней.
#include <stdio.h>
#include <ctype.h>
char * capitalize_word( char *s, int blank )
{
if ( *s )
{
if ( blank ) *s = toupper( ( unsigned char )*s );
capitalize_word( s + 1, isblank( ( unsigned char )*s ) );
}
return s;
}
char * capitalize( char *s )
{
return capitalize_word( s, !isblank( ( unsigned char )( *s ) ) );
}
int main(void)
{
char s[] = "hello everybody. how do you do?";
puts( s );
puts( capitalize( s ) );
return 0;
}
Вывод программы на консоль совпадает с выводами на консоль двух предыдущих программ:
hello everybody. how do you do?
Hello Everybody. How Do You Do?
Эта тема мною создана благодаря следующему вопросу на
Stackoverflow How can i make first letter of all words in a string uppercase recursively?