Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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 : {бесплатный
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 переходы пронумерованы по ходу часовой стрелки). Для каждого состояния поочередно выполняется проверка возможности выполнения каждого из переходов. Если переход можно выполнить, сделанный выбор заталкивается в стек, после чего переход выполняется. Если переход невозможен, предпринимается попытка выполнения следующего перехода.