Блог

У меня возникли небольшие проблемы с пониманием того, как разделить строку на подстроку. В моей программе пользователь вводит случайную строку в string stemp, и программа сохраняет любые двойные, тройные и т.д. Буквы, Но также сохраняет любые алфавитные подстроки

Например, строки, которые я хотел бы разделить, выглядят так:

 string stemp = "AAABBCDE";
string stemp2 = "HHHHZAB"
 

Я хотел бы иметь возможность создавать подстроки с одинаковыми буквами, такими как «AAA», «BB», и любые по-прежнему сохраняют следующие за ними алфавитные строки, такие как «CDE». В stemp2 я бы сохранил «HHHH», но не сохранил бы «ZAB».

Пожалуйста, помогите указать мне правильное направление, я схожу с ума.

В итоге это оказался не такой простой синтаксический анализ. Причина в том, что вам нужно не только обрабатывать переходы от последовательности дубликатов к новой последовательности дубликатов (например, "AAABB" ) и обрабатывать переход от последовательности дубликатов к серии символов (например "AAABCDE" , ), но и обрабатывать переход обратно (например "AAAHIJKLBBCDE" , ) любое количество раз, а такжеобрабатывать дубликаты до конца (например "AAABCDEGG" ).

Там есть достаточное количество предостережений. Один из подходов заключается в обработке синтаксического анализа строки в непрерывном цикле, увеличивая индекс на основе количества дубликатов в последовательности или количества последовательных символов. Основная схема будет:

     loop continually over indexes in string {
        while (sequence of duplicates) {
            extract duplicates substring
            advance index by no. of duplicates
        }
        while (characters in series in sort-order) {
            increment counter
            advance index
        }
        if (counter > 2) {
            extract series substring
        }
 

Теперь внутри каждого из этих блоков вам также необходимо обработать конец строки. Имея это в виду и предполагая, что вы будете извлекать каждую подстроку, найденную в std::string s; , и сохранять подстроку в std::vector<std::string> vs; , вы могли бы сделать что-то похожее на следующее, используя std::basic_string::find_first_not_of, чтобы проверить последовательность дубликатов для вас:

     for (size_t i = 0; ;) {                 /* loop until string exhausted */
        bool dupsadded = false;             /* flag for whether duplicates found */
        size_t spos = 0, nchr = 0;          /* string position and number of chars */
        /* loop extracting duplicate characters */
        while ((spos = s.find_first_not_of (s[i], i)) amp;amp; 
                /* duplicates do not extend to end of string */
                ((spos != std::string::npos amp;amp; spos - i > 1) ||
                /* duplicates do extend to end of string */ 
                (s.substr(i).length() > 1 amp;amp; spos == std::string::npos))) {
            if (spos != std::string::npos) {        /* handle not through end */
                nchr = spos - i;                    /* no of chars duplicate chars */
                vs.push_back (s.substr (i, nchr));  /* add to vector of substrings */
                i  = nchr;                          /* incremnt index */
                dupsadded = true;                   /* set dupsadded flag */
                nchr = 0;                           /* zero nchr */
            }
            else {                                  /* duplicates to end of string */
                vs.push_back (s.substr (i));        /* add remaining substring */
                goto done;
            }
        }
        if (!i || dupsadded)                    /* 1st char or dups found */
            i  = 1;                             /* advance past last dup as s[i-1] */
        while (s[i] amp;amp; s[i-1]   1 == s[i]) {    /* while characters in sequance */
            nchr  = 1;                          /* increment char count */
            i  = 1;                             /* increment index */
        }
        if (nchr > 1)       /* if nchr > 1 (3 in sequence) */
            vs.push_back (s.substr (i - nchr - 1, nchr   1));
        else if (!s[i])     /* if at end */
            break;          /* break */
        else                /* otherwise */
            i  = 1;         /* increment index */
    }
    done:;
 

Кроме пользователя .find_first_not_of() , остальная часть функции просто полагается на старую добрую арифметику. Существует много разных способов написать это, но здесь, если набор символов не был серией дубликатов, тогда сравнивались значения ASCII соседних символов, чтобы определить, присутствует ли серия символов в порядке сортировки. См. Таблицу ASCII и описание.

Переход от последовательности дубликатов к серии в порядке сортировки был особенно проблематичным, поскольку сравнение порядка сортировки основывалось на сравнении s[i-1] 1 == s[i] , которое сравнивало бы последний повторяющийся символ, если бы индекс не был дополнительно скорректирован, 1 так что s[i-1] это был фактически следующий символ после последовательности дубликатов. (в этом нет ничего волшебного, это просто зависит от того, как вы проводите сравнение соседних символов, одновременно защищая конец строки). Я думаю, что правильный способ выразить это — это арифметика, требующая особого внимания для обработки этого перехода.

Собрав короткий пример, вы могли бы сделать:

 #include <iostream>
#include <string>
#include <vector>

int main (void) {
    
    std::string s{};                        /* string for user input */
    std::vector<std::string> vs{};          /* vector of string to hold substrings */
    
    std::cout << "enter string: ";
    if (!(std::cin >> s)) {
        std::cout << "(user canceled input)n";
        return 0;
    }
    if (s.length() < 2) {   /* validate at least 2 characters */
        std::cerr << "error: must have more than 1 character.n";
        return 1;
    }
    
    for (size_t i = 0; ;) {                 /* loop until string exhausted */
        bool dupsadded = false;             /* flag for whether duplicates found */
        size_t spos = 0, nchr = 0;          /* string position and number of chars */
        /* loop extracting duplicate characters */
        while ((spos = s.find_first_not_of (s[i], i)) amp;amp; 
                /* duplicates do not extend to end of string */
                ((spos != std::string::npos amp;amp; spos - i > 1) ||
                /* duplicates do extend to end of string */ 
                (s.substr(i).length() > 1 amp;amp; spos == std::string::npos))) {
            if (spos != std::string::npos) {        /* handle not through end */
                nchr = spos - i;                    /* no of chars duplicate chars */
                vs.push_back (s.substr (i, nchr));  /* add to vector of substrings */
                i  = nchr;                          /* incremnt index */
                dupsadded = true;                   /* set dupsadded flag */
                nchr = 0;                           /* zero nchr */
            }
            else {                                  /* duplicates to end of string */
                vs.push_back (s.substr (i));        /* add remaining substring */
                goto done;
            }
        }
        if (!i || dupsadded)                    /* 1st char or dups found */
            i  = 1;                             /* advance past last dup as s[i-1] */
        while (s[i] amp;amp; s[i-1]   1 == s[i]) {    /* while characters in sequance */
            nchr  = 1;                          /* increment char count */
            i  = 1;                             /* increment index */
        }
        if (nchr > 1)       /* if nchr > 1 (3 in sequence) */
            vs.push_back (s.substr (i - nchr - 1, nchr   1));
        else if (!s[i])     /* if at end */
            break;          /* break */
        else                /* otherwise */
            i  = 1;         /* increment index */
    }
    done:;
    
    for (const auto amp;ss : vs)               /* output results */
        std::cout << ss << 'n';
}
 

(примечание: там много всего, это не беглый просмотр и понимание логики. Возьмите карандаш на листе бумаги и запишите входную строку, а затем прорабатывайте каждую итерацию, отслеживая значение i (индекс), помещая метку под текущим символом и отмечая значения для spos возвращаемых из .find_first_not_of() , nchr и отмечая значение, используемое для извлечения символов с использованием .substr() . Это, вероятно, лучший способ приблизиться к пониманию того, что происходит в каждой точке — подобно разговору с уткой из «Как отлаживать небольшие программы«)

Пример использования / вывода

Ваш первый пример:

 $ /bin/str_substr_dup_or_seq
enter string: AAABBCDE
AAA
BB
CDE
 

Ваш второй пример:

 $ ./bin/str_substr_dup_or_seq
enter string: HHHHZAB
HHHH
 

Расширение, проверяющее дополнительные переходы:

 $ ./bin/str_substr_dup_or_seq
enter string: AAAHIJKLBBCDE
AAA
HIJKL
BB
CDE
 

С последовательностью дубликатов в конце:

 $ ./bin/str_substr_dup_or_seq
enter string: AAABCDEGG
AAA
BCDE
GG
 

С последовательностью дубликатов с тем же символом, что и последний в серии:

 $ ./bin/str_substr_dup_or_seq
enter string: AAABCDEEE
AAA
BCDE
EE
 

(существует небольшая двусмысленность, хотите ли вы "BCD" и "EEE" вместо этого — оба будут удовлетворять вашим ограничениям. Дальнейшая реализация для изменения поведения остается за вами)

Или немного сложнее с "ISHKABIBBLE" (на идише для бессмыслицы), вставленной внутри "AAAHIJKLBBCDE" , с "IE" добавлением другого конца в конец:

 $ ./bin/str_substr_dup_or_seq
enter string: AAAHIJKLISHKABIBBLEBBCDEIE
AAA
HIJKL
BB
BB
CDE
 

Просмотрите все и дайте мне знать, если у вас возникнут дополнительные вопросы.