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

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

.Пример: 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; // перенести остаток входной строки

}

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