Песни о Паскале

Наша цель: смоделировать сортировочную горку, то есть создать программу, ведущую себя подобно такой горке. Вагоны заменим символами; следовательно, и состав и стоящие в тупиках вагоны мы представим строками. Будем считать первый символ строки первым вагоном состава, – он прицеплен к локомотиву. В тупике первым будет вагон, стоящий у земляного вала. Легко догадаться, что обрабатывать вагоны будем по принципу стека, поскольку сцепщику всегда доступен только последний вагон.

Договорившись об этом, сформулируем задачу окончательно. Дана строка символов (состав), из которой надо сформировать три других. Вагоны, обозначенные большими буквами ’A’…’Z’, отправим на станцию «A»; другие, обозначенные маленькими буквами ’a’…’z’, – поедут к станции «B», а третьи, обозначенные цифрами ’0’…’9’, – к станции «C». Программа должна сформировать три строки – это вновь собранные составы. Первый символ в них, – это вагон, прицепленный непосредственно к локомотиву.

Для решения задачи надо всего лишь в точности повторить действия сцепщика и стрелочника. Будем «отцеплять» символы от строки и «заталкивать» их в стеки – это наши тупики. Значит, надо построить механизм для стеков. Он будет похож на механизм для очереди: элементы храним в строковых переменных, а для занесения и извлечения элементов из стека учредим две процедуры. По традиции программисты называют эти процедуры так: Push – затолкнуть в стек, и Pop – вытолкнуть из стека.

Процедура заталкивания в стек Push присоединяет символ к концу строки. Она точь-в-точь повторяет процедуру установки в очередь, только называется иначе.

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

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

{ P_45_2 – Сортировочная станция }

{ Помещение элемента в стек }

procedure Push(var aStack: string; arg: char);

begin

      aStack:= aStack + arg; { добавляем в конец строки }

end;

{ Извлечение элемента из стека }

function Pop(var aStack: string; var arg: char): boolean;

begin

if Length(aStack) = 0 { если стек пуст }

      then Pop:= false       { сообщаем об этом }

      else begin

      { возвращаем последний элемент }

      arg:= aStack[Length(aStack)];

      { и удаляем его из стека }

      Delete(aStack, Length(aStack), 1);

      Pop:= true; { признак того, что стек не был пуст }

      end;

end;

var S : string;       { исходный состав }

      SA, SB, SC : string; { три сортировочных тупика A,B,C}

      c : char;       { очередной вагон }

begin

S:= 'HEjd31kDJK62px912se3BKdwL9'; { Исходный состав }

Writeln('Исходный состав: '+S);

SA:=’’; SB:=’’; SC:=’’; { очистка тупиков }

{ Отцепляем вагоны от исходного состава и заталкиваем в тупики }

while Pop(S, c) do begin

      if c in ['A'..'Z'] then Push(SA, c);

      if c in ['a'..'z'] then Push(SB, c);

      if c in ['0'..'9'] then Push(SC, c);

end;

{ Теперь исходный состав пуст, то есть S='' }

{ Выкатываем вагоны из тупика A и цепляем к первому составу }

while Pop(SA, c) do Push(S, c);

Writeln('На станцию A : '+S);

S:=''; { Освобождаем пути }

{ Выкатываем вагоны из тупика B и цепляем ко второму составу }

while Pop(SB, c) do Push(S, c);

Writeln('На станцию B : '+S);

S:=''; { Освобождаем пути }

{ Выкатываем вагоны из тупика C и цепляем к третьему составу }

while Pop(SC, c) do Push(S, c);