Выделение вложенных фрагментов

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

.Пример: a{b{c}b}a{d{e{g}e}d}a => {c}{b1b}{g}{e3e}{d4d}a2a5a

Предварительное решение задачи начнем с разработки функции, которая обязательно потребуется: поиск открывающейся скобки для самого внутреннего вложенного фрагмента. Для этого можно использовать переменную-счетчик, которая увеличивает свое значение на 1 на каждую из открывающихся скобок и уменьшает на 1 на каждую из закрывающихся. При этом фиксируется максимальное значение счетчика и позиция элемента, где это происходит.

// функция возвращает индекс скобки “{” для самой внутренней // пары {}

int find(char c[])

{

int i; // Индекс в строке

int k; // Счетчик вложенности

int max; // Максимум вложенности

int b; // Индекс максимальной “{”

for (i=0, max=0, b=-1; c[i]!=0; i++)

{

if (c[i]==’}’) k--;

if (c[i]==’{’)

{

k++;

if (k>max) { max=k; b=i; }

}

}

if (k!=0) return 0; // Защита “от дурака”, нет парных скобок

return b;

}

Другой вариант функции ищет первую внутреннюю пару скобок. Запоминается позиция открывающейся скобки, при обраружении закрывающейся скобки возвращается индекс последней открывающейся. Заметим, что его также сожно использовать, просто последовательность извлечения фрагментов будет другая.

// функция возвращает индекс скобки “{” для первой внутренней пары {}

int find(char c[])

{

int i; // Индекс в строке

int b; // Индекс максимальной “{”

for (i=0, b=-1; c[i]!=0; i++)

{

if (c[i]==’}’) return b;

if (c[i]==’{’) b=i;

}

return b;

}

Идея основного алгоритма заключается в последовательной нумерации “выкусываемых” из входной строки фрагментов, при этом на место каждого помещается его номер – значение счетчика во внешней форме представления.

void copy(char c1[], char c2[])

{

int i=0; // Индекс в выходной строке

int k; // Индекс найденного фрагмента

int n; // Запоминание начала фрагмента

int m; // Счетчик фрагментов

for (m=1; (k=find(c1))!=-1; m++) // Пока есть фрагменты

{

for (n=k; c1[k]!=’}’; k++, i++) c2[i]=c1[k];

c2[i++] = c1[k++]; // Переписать фрагмент

if (m/10!=0) c1[n++] = m/10 + ’0’; // На его место – две цифры

c1[n++] = m%10 + ’0’; // номера во внешней форме

for (;c1[k]!=0; k++, n++) c1[n]=c1[k];

c1[n]=0; // сдвинуть “хвост” к началу

}

for (k=0; c1[k]!=0; k++, i++) c2[i]=c1[k];

c2[i]=0; // перенести остаток входной строки

}

Практический совет – избегать сложные вычисления над индексами. Лучше всего для каждого фрагмента строки заводить свой индекс и перемещать их независимо друг от друга в нужные моменты. Что, например, сделано выше при “уплотнении” строки.

Форматирование строки

Форматирование строки -размещение ее в выходном массиве заданной размерности таким образом, чтобы интервалы между соседними словами отличались не более, чем на 1.

Шаг 1: Исходные данные и результат. Входная строка произвольной длины в массиве IN[], отформатированная строка длины n в массиве OUT[]. Выходная строка отвечает следующим требованиям:

• слово -любая последовательность символов, кроме пробела ;

• после форматирования число пробелов между словами различается не более чем на 1;

• первое и последнее слово расположены по краям строки. Шаг 2: Форматирование включает в себя последовательность из трех действий:

void format(char IN[], char OUT[], int n)

{

// Собрать исходные данные по строке,

// необходимые для форматирования;

// Проверить возможность форматирования;

// Разместить слова в выходной строке.

}

Шаг 3: Данные по строке, необходимые для форматирования: -количество слов в строке -nw; -общее количество символов во всех словах -ns; -стандартное количество пробелов между словами при форматировании -np; -оставшееся количество пробелов, добавляемых по одному между словами -nr. На этом шаге детализируется проверка возможности форматирования и определяются взаимосвязанные параметры.

void format(char IN[], char OUT[], int n)

{ int nw, ns, np, nr;

// Определение nw, ns ...

OUT[0] = '\0';

if (nw < 2) return; // Мало слов в строке

np = (n - ns) / (nw - 1);

if (np <= 0) return; // Много символов в словах

nr = (n - ns) % (nw - 1);// Остаточное число пробелов

// Размещение слов в выходной строке

}

Шаг 4: Просмотр строки при определении параметров и форматировании можно выполнить, используя:

• -цикл в цикле: цикл просмотра всех слов, в который включен цикл посимвольного просмотра интервала между словами и самого слова;

• -цикл посимвольного просмотра строки, с использованием признака нахождения внутри слова или вне его - inword.

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

Шаг 5: Определение ns,nw:

for (i=0,ns=0,nw=0,inword =0; ; i++)

{

// Анализ символа IN[i] и подсчет параметров;

if (IN[i] =='\0') break;

}

Шаг 6: Размещение слов в выходной строке:

{

for (i=0,j=0,inword =0; ; i++)

{

// Анализ символа IN[i] и форматирование

// (перенос в OUT[j]);

}

if (IN[i] =='\0') break;

}}

Шаг 7: Анализ символа состоит в выделении 4 вариантов по двум сравнениям -признака inword и типа символа IN[i] - разделителя или символа слова:

{

if (IN[i]==' ' || IN[i]=='\0')

if (inword)

{ nw++; inword =0; } // Конец слова

else

{} // Продолжение разделителя

else

{ ns++;

if (inword)

{} // Продолжение слова

else

{ inword =1; } // Начало слова

}}

Шаг 8: Анализ символа IN[i] и форматирование:

{

if (IN[i]==' ' || IN[i]=='\0')

if (inword)

{ // Конец слова

for (k=0; k<np; k++) // Включение "np"

OUT[j++]=' '; // пробелов

if (nr-- >0) // Включение

OUT[j++]=' '; // дополнительного пробела

}

else

{} // Продолжение разделителя

else

if (inword)

OUT[j++]=IN[i]; // Продолжение слова

else

{ // Начало слова

OUT[j++]=IN[i];

inword =1;

}}

Окончательный вариант с оптимизацией (исключение лишних ветвей):

//-----Форматирование строки

void format(char IN[], char OUT[], int n)

{

int nw, ns, np, nr, i, j, k, inword;

for (i=0,ns=0,nw=0,inword =0; ; i++)

{

if (IN[i]==' ' || IN[i]=='\0')

{ if (inword) { nw++; inword =0; } }

else

{ ns++; inword=1; }

if (IN[i] =='\0') break;

}

OUT[0] = '\0';

if (nw < 2) return;

np = (n - ns) / (nw - 1);

if (np <= 0) return;

nr = (n - ns) % (nw - 1);

for (i=0,j=0,inword=0; ; i++)

{

if (IN[i]==' ' || IN[i]=='\0')

{ if (inword)

{

for (k=0; k<np; k++) OUT[j++]=' ';

if (nr-- >0) OUT[j++]=' ';

}

}

else

{ OUT[j++]=IN[i]; inword =1; }

if (IN[i] =='\0') break;

}

}