Динамические структуры данных. Задание практикума. Язык Паскаль. Вылиток А.А - 34 стр.

if L = nil then copy:= nil
          else
            begin {создаем копию «головы» списка}
                new(head);
                head↑.elem:= L↑.elem;
                {к созданной «голове» присоединяем
                 копию «хвоста»}
                head↑.next:= copy(L↑.next)
            end
end;

Задача 9. Используя стек (тип данных и операции над стеком считать уже
описанными), описать процедуру pairs(f) для решения следующей задачи. В
текстовом файле f находится последовательность символов, сбалансированная
по круглым скобкам. Требуется для каждой пары соответствующих
открывающей и закрывающей скобок вывести на экран номера их позиций в
последовательности, упорядочив пары номеров в порядке возрастания номеров
позиций закрывающих скобок. Например, для текста A+(45-F(X)*(B-C))
надо вывести: 8 10; 12 16; 3 17 .

                                        Решение
      Опишем в процедуре переменную sym для хранения очередного
считанного из файла f символа; переменную pos для хранения номера позиции
текущего символа sym, и переменную S, представляющую стек, в который
будут помещаться номера позиций открывающих скобок.
       Алгоритм обработки последовательности таков. Сначала счётчик
позиций pos устанавливаем в ноль, создаём пустой стек (с помощью
init_stack(S)) и открываем файл f для чтения. Пока не конец файла,
повторяем следующие действия:
      1) считываем в sym очередной символ и увеличиваем pos на единицу;
      2) еcли текущий символ – открывающая скобка, то номер его позиции
         помещаем в стек (c помощью push(S, pos));
      3) если текущий символ – закрывающая скобка, то это значит, что в
         переменной pos – номер позиции этой скобки, а на вершине стека –
         номер позиции соответствующей открывающей скобки; поэтому
         берём элемент из стека, помещая его во вспомогательную
         переменную i (с помощью pop(S,i)), и печатаем пару (i, pos).
        В нашем алгоритме нет проверки стека на переполнение. В
сбалансированном по скобкам тексте количество открывающих скобок не
может превосходить половину длины текста. Поэтому размер стека должен
быть не меньше, чем половина длины обрабатываемого текста, или входной
текст должен иметь длину не более чем в два раза превосходящую размер
стека.1

1
  Если стек представлен не массивом, а динамической цепочкой (см. задачу 10), то его размер
заранее не ограничен. Стек может расти, пока у Паскаль-машины хватает ресурсов для создания
нового динамического объекта – очередного звена стека.

                                          - 34 -