Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Однако для реализации этого алгоритма потребуется реализация очереди с двусторонним доступом (deque). Очередь с двусторонним доступом - это двусторонняя очередь, в которой постановку в очередь и исключение из очереди можно выполнять с любого конца. Нам потребуется возможность постановки элементов в конец очереди и их заталкивания в начало и из начала очереди (иначе говоря, исключение элементов из очереди должно выполняться только из ее начала и никогда из ее конца). Элементы, которые нужно будет ставить в очередь, представляют собой целочисленные значения (фактически, номера состояний). Код реализации этой простой очереди с двусторонним доступом показан в листинге 10.14 (его
Листинг 10.14. Класс очереди целочисленных значений с двусторонним доступом type
TtdIntDeque = class private
FList : TList;
FHead : integer;
FTail : integer;
protected procedure idGrow;
procedure idError(aErrorCode : integer;
const aMethodName : TtdNameString);
public
constructor Create(aCapacity : integer);
destructor Destroy; override;
function IsEmpty : boolean;
procedure Enqueue(aValue : integer);
procedure Push(aValue : integer);
function Pop : integer;
end;
constructor TtdIntDeque.Create(aCapacity : integer);
begin
inherited Create;
FList := TList.Create;
FList.Count := aCapacity;
{для облегчения задачи пользователя очереди с двусторонним доступом поместить указатели начала и конца очереди в ее середину - вероятно, это более эффективно}
FHead := aCapacity div 2;
FTail := FHead;
end;
destructor TtdIntDeque.Destroy;
begin
FList.Free;
inherited Destroy;
end
procedure TtdIntDeque.Enqueue(aValue : integer);
begin
FList.List^[FTail] := pointer(aValue);
inc(FTail);
if (FTail = FList.Count) then
FTail := 0;
if (FTail = FHead) then
idGrow;
end;
procedure TtdIntDeque.idGrow;
var
OldCount : integer;
i, j : integer;
begin
{увеличить размер списка на 50%}
OldCount := FList.Count;
FList.Count := (OldCount * 3) div 2;
{распределить данные по увеличенной области, поддерживая при этом очередь с двусторонним доступом}
if (FHead= 0) then
FTail := OldCount else begin
j := FList.Count;
for i := pred(OldCount) downto FHead do
begin
dec(j);
FList.List^[j] := FList.List^[i] end;
FHead := j;
end;
end;
function TtdIntDeque.IsEmpty : boolean;
begin
Result := FHead = FTail;
end;
procedure TtdIntDeque.Push(aValue : integer);
begin
if (FHead = 0) then
FHead := FList.Count;
dec(FHead);
FList.List^[FHead] := pointer(aValue);
if (FTail = FHead) then
idGrow;
end;
function TtdIntDeque.Pop : integer;
begin
if FHead = FTail then
idError(tdeDequeIsEmpty, 'Pop');
Result := integer(FList.List^[FHead]);
inc(FHead);
if (FHead = FList.Count) then
FHead := 0;
end;
Алгоритм работает следующим образом. Поставим значение -1 в очередь с двусторонним доступом. Это специальное значение, которое указывает о необходимости выполнить считывание входной строки
После того, как подготовка закончена, мы входим в цикл. На каждом этапе выполнения цикла выполняется одно и то же действие: выталкивание верхнего значения из очереди. Если этим значением является -1 (как, естественно, это будет вначале), мы увеличиваем индекс текущего символа и извлекаем этот символ из сопоставляемой строки. Снова поставим значение -1 в очередь, чтобы знать, когда нужно выполнить считывание следующего символа. Если это значение не -1, оно должно быть реальным номером состояния. Взглянем на запись состояния в таблице переходов. Если текущий входной символ соответствует шаблону символов этого состояния, значение NextStatel состояния нужно поставить в очередь. Понятно, что если шаблоном символов состояния был е, символ не соответствовал шаблону. В этом случае в очередь с двусторонним доступом мы заталкиваем значение NextStatel, а затем значение NextState2.
Выполнение цикла прекращается, как только очередь с двусторонним доступом оказывается пустой (ни один путь не соответствует входной строке) или при считывании всех символов из сопоставляемой строки (в этом случае очередь содержит набор состояний, достигнутых на момент достижения конца строки, которые можно выталкивать из очереди до тех пор, пока в зависимости от конкретной ситуации не будет найдено или не найдено одно единственное конечное состояние).
Общий результат применения этого алгоритма состоит в том, что в очередь с двусторонним доступом помещается значение "извлечь следующий символ" (-1). "Слева" от него располагается набор состояний, с которым нам по-прежнему необходимо сравнить текущий символ (мы постоянно выталкиваем из очереди эти состояния и помещаем в нее те, которых можно достичь за счет выполнения бесплатного перехода). "Справа" от него находятся состояния, полученные из тех, которые уже соответствуют текущему символу. Переход к ним будет осуществляться сразу после выталкивания значения -1 из очереди и извлечения следующего символа. Как видите, алгоритм одновременно проверяет все пути обхода конечного NFA-автомата.
Подпрограмма сопоставления приведена в листинге 10.15. Она была создана в качестве метода машины обработки регулярных выражений. Ей передается строка, с которой должно быть выполнено сопоставление, и значение индекса. Значение индекса указывает позицию в строке, начиная с которой предположительно должно начинаться совпадение. Это позволяет использовать регулярное выражение для сопоставления с любой частью строки, а не со всей строкой, как делалось в приведенных простых примерах конечных автоматов. Метод будет возвращать значение true, если таблица переходов регулярного выражения соответствует строке, начиная с данной позиции.
Листинг 10.15. Сопоставление подстрок с таблицей переходов
function TtdRegexEngine.rcMatchSubString(const S : string;
StartPosn : integer): boolean;
var
Ch : AnsiChar;
State : integer;
Deque : TtdIntDeque;
StrInx : integer;
begin
{предположить, что сопоставление будет неудачным}
Result := false;
{создать очередь с двусторонним доступом}
Deque := TtdIntDeque.Create(64);
try
{поставить в очередь специальное значение, означающее начало сканирования}