Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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.
Рисунок 10.4. DFA-автомат для проверки, является ли строка числом
Листинг 10.4: Проверка того, что строка является числом, с помощью DFA-автомата
function IsValidNumber(const S : string) : boolean;
type
TStates = (StartState, GotSign,
GotInitDigit, GotInitDecPt, ScanDigits);
var
State : TStates;
Inx : integer;
Ch : AnsiChar;
begin
{предположим, что число является недопустимым}
Result := false;
{подготовиться к сканированию}
State := StartState;
{считывание всех символов строки}
for Inx := 1 to length(S) do
begin
{извлечь текущий символ}
Ch := S[Inx];
{обработать в зависимости от состояния}
case State of
StartState : begin
if (Ch = '+') or (Ch = '-') then
State := GotSign else
if (Ch = DecimalSeparator) then
State := GotInitDecPt else
if TDIsdigit(Ch) then
State := GotInitDigit else
Exit;
end;
GotSign : begin
if (Ch = DecimalSeparator) then
State := GotInitDecPt else
if TDIsDigit(Ch) then
State := GotInitDigit else Expend;
GotInitDigit : begin
if (Ch = DecimalSeparator) then
State := ScanDigits else
if not TDIsDigit(Ch) then
Exit;
end;
GotInitDecPt : begin
if TDIsDigit(Ch) then
State := ScanDigits else Expend;
ScanDigits : begin
if not TDIsDigit (Ch) then
Exit;
end;
end;
end;
{в этой точке число допустимо, если текущее состояние является конечным}