Фундаментальные алгоритмы и структуры данных в Delphi

Dispose(Choice);

end;

function IsValidNumberNFA(const S : string): boolean;

var

StrInx: integer;

State : TnfaState;

Ch : AnsiChar;

Move : integer;

ChoiceStack : TtdStack;

begin

{предположим, что число является недопустимым}

Result :- false;

{инициализировать стек вариантов}

ChoiceStack := TtdStack.Create(DisposeChoice);

try

{подготовиться к сканированию}

Move := 0;

StrInx := Instate := StartScanning;

{считывание всех символов строки}

while StrInx <= length(S) do

begin

{извлечь текущий символ}

Ch := S[StrInx];

{обработать в зависимости от состояния}

case State of

StartScanning : begin

case Move of

0 : {переход к ScannedSign по ветви +}

begin

if (Ch = '+') then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScannedSign;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

1 : {переход к ScannedSign по ветви -}

begin

if (Ch = '-') then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScannedSign;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

2 : {бесплатный переход к ScannedSign}

begin

PushChoice(ChoiceStack, StrInx, Move, State);

State ScannedSign;

Move := 0;

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScannedSign : begin

case Move of

0 : {переход x Scanlnteger с использованием цифры}

begin

if TDIsDigit(Ch) then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := Scanlnteger;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

1 : {переход к ScanLeadDigits с использованием цифры}

begin

if TDIsDigit (Ch) then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScanLeadDigits;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

2 : {переход к ScanLeadDigits с использованием десятичного разделителя}

begin

if (Ch = DecimalSeparator) then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScanLeadDecPoint;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

Scanlnteger : begin

case Move of

0 : {сохранить данное состояние для текущей цифры}

begin

if TDIsDigit(Ch) then

inc(StrInx) else inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScanLeadDigits : begin

case Move of

0 : {сохранить данное состояние для текущей цифры}

begin

if TDIsDigit(Ch) then

inc(StrInx) else

inc(Move);

end;

1 : {переход к ScanDecPoint с использованием десятичного разделителя}

begin

if (Ch = DecimalSeparator) then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScannedDecPoint;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScannedDecPoint : begin

case Move of

0 : {сохранить данное состояние для текущей цифры}

begin

if TDIsDigit(Ch) then

inc(StrInx) else inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScanLeadDecPoint : begin

case Move of

0 : {переход к ScanDecPoint с использованием цифры}

begin

if TDIsDigit(Ch) then begin

PushChoice(Choicestack, StrInx, Move, State);

State := ScanDecimalDigits;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScanDecimalDigits : begin

case Move of

0 : {сохранить данное состояние для текущей цифры}

begin

if TDIsDigit(Ch) then

inc(StrInx) else inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

end;

{если для конкретного состояния допустимые переходы отсутствуют, выполнить отход за счет отказа от последнего выбора, и выполнить переход со следующим номером}

if (Move = -1) then begin

{если стек пуст, возможность выполнения отхода отсутствует}

if Choicestack.IsEmpty then

Exit;

{отказаться от последнего выбора, выполнить следующий по порядку переход}

PopChoice(ChoiceStack, StrInx, Move, State);

inc(Move);

end;

end;

{в этой точке число допустимо, если текущее состояние является конечным}

if (State = Scanlnteger) or

(State = ScannedDecPoint) or (State = ScanDecimalDigits) then

Result := true;

finally

ChoiceStack.Free;

end;

end;

Исходный код подпрограммы IsValidNumberNFA можно найти на web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.pas.

Из листинга 10.3 видно, что базовая структура кода реализации всех состояний одинакова. Предполагается, что для каждого состояния существует ряд переходов, начиная с 0 (на рис. 10.3 переходы пронумерованы по ходу часовой стрелки). Для каждого состояния поочередно выполняется проверка возможности выполнения каждого из переходов. Если переход можно выполнить, сделанный выбор заталкивается в стек, после чего переход выполняется. Если переход невозможен, предпринимается попытка выполнения следующего перехода.

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

Для сравнения на рис. 10.4 показана блок-схема детерминированного автомата, который выполняет эту же проверку, а код, реализующий его, приведен в листинге 10.4.