1

Встал перед вопросом, необходимо в введенном тексте заменить одинаковые подряд идущие символы на "сигнатуру". С использованием #include <vector> все решается довольно просто, но использовать его нельзя (размер обновляется сам). Как реализовать данное задание с использованием массива типа char или строки string?

Имеем строку аааа345рр, пользователь вводит число 2, все символы подряд идущие 2 или более раза меняются на сигнатуру {количество, символ}. Имеющаяся строка на выходе {4,а}345{2,о}

jfs
  • 52,361
  • На счет алгоритма думал поступить так: Цикл идущий по строке, каждый символ после первого сравниваем с текущим для сравнения, если он будет равен - увеличиваем счётчик символов и запоминаем позицию текущего, иначе - если счётчик повторов больше 1, то вырезать из строки все символы от текущего, который сравниваем, до текущего, который в цикле и помещаем на вырезанное место счетчик повторений, но как "динамически" тогда изменить размер массива, если я например 3 символа 'a' заменю на {3,a}? –  Nov 03 '17 at 17:46
  • @jfs, при замене части строки на сигнатуру, меняется размер массива, проблемы с обновлением размера массива. –  Nov 04 '17 at 10:34
  • @jfs, while (str[i+1]!='\0') { if (str[i] == str[i + 1]) for (int x=0;(x<"размер строки" && str[x]!='\0');x++) далее я делаю замену, где соответственно меняется размер строки, размер необходимо обновить, проблема здесь. –  Nov 04 '17 at 10:39

2 Answers2

3

Чтобы из аааа345рр получить {4,а}345{2,о}, то есть чтобы реализовать Кодирование длин серий (RLE):

template<class InputIt, class OutputIt>
OutputIt rle_encode(InputIt first, InputIt last, OutputIt d_first)
{
  if (first == last) // empty
    return d_first;

  auto prev = *first++;  // previous char
  uintmax_t count = 1;
  for ( ; first != last; ++first, ++count) {
    if (prev != *first) { // ended run of the same consecutive elements
      d_first = write_rle_run(d_first, prev, count); // write the run
      prev = *first; // start new run
      count = 0;
    }
  }
  return write_rle_run(d_first, prev, count);
}

Это трансляция из Питона rle_encode() функции.

write_rle_run() записывает найденную серию подряд идущих символов в результат:

template<class OutputIt, class C>
OutputIt write_rle_run(OutputIt d_first, C character, uintmax_t count) {
  if (count > 1) {
    *d_first++ = '{';
    for (char digit : std::to_string(count))
      *d_first++ = digit;
    *d_first++ = ',';
    *d_first++ = character;
    *d_first++ = '}';
  }
  else {
    assert(count == 1);
    *d_first++ = character;
  }
  return d_first;
}

Это работает и для массива:

const char a[] = "aaaa345pp";
char output[5*(sizeof a)/2];
rle_encode(std::begin(a), std::end(a), output);

и для string:

std::string text = "aaaa345pp";
std::string s;
rle_encode(std::begin(text), std::end(text), std::back_inserter(s));

и для потоков ввода/вывода:

std::istream_iterator<char> chars{std::cin}, eof;
rle_encode(chars, eof, std::ostream_iterator<char>(std::cout));

Полный пример кода.

В write_rle_run() можно передать желаемое число повторений от пользователя и адаптировать if (count > 1) условие.

Чтобы выполнить преобразование в обратную сторону, можно использовать rle_decode().

jfs
  • 52,361
  • а как используя этот алгоритм вернуть текст в исходное состояние, то есть декодировать текст? –  Nov 04 '17 at 22:03
  • 1
    @LokenGarvel' это уже отдельный [простой] вопрос. Вот пример для похожего формата на Питоне. Не имеет значения какой алгоритм данные генерирует. Как обратить зависит в первую очередь от формата данных и в каком виде вы их получаете. Можно регулярные выражения использовать или можно руками серии {count,char} искать и распаковывать. Пример как по одной цифре на Си числа распознаются. Попробуйте реализовать решение и если возникнут конкретные сложности, задайте отдельный Stack Overflow вопрос. – jfs Nov 04 '17 at 22:23
0

C использованием string все решается небольшой функцией. Вопрос закрыт

   while (first != str.end()) 
    {
        string::const_iterator second = first + 1;

        while (second != str.end() && *first == *second)
            ++second;

        size_t n = second - first;

        if (n > 1) {
            stringstream ss;
            ss << n;
            ret +=  string("{")+ss.str() + string(",") + *first + string("}");
            first = second;
        }
        else {
            ret += *first++;
        }
    }
Qwertiy
  • 123,725