Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл
Шрифт:
Интервал:
Закладка:
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.
Рисунок 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;
{в этой точке число допустимо, если текущее состояние является конечным}
if (State = GotInitDigit) or (State = ScanDigits) then
Result := true;
end;
Исходный код подпрограммы IsValidNumber можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.
Если сравнить коды, приведенные в листингах 10.3 и 10.4, невозможно не заметить, что код NFA-автомата значительно сложнее. Он содержит целый набор вспомогательных подпрограмм, которые необходимо закодировать и поддерживать. Он также более чреват ошибками (необходимо побеспокоиться о поддержке стека, о возврате конечного автомата к предшествующему состоянию, о выборе следующего перехода и т.п.).
В общем случае, если требуется фиксированный, заранее определенный автомат, следует попытаться разработать и использовать детерминированный автомат. Следует попытаться свести реализацию недетерминированных автоматов к автоматическим алгоритмам. Реализация их вручную - чересчур трудоемкая задача.
Конечно, в рассмотренном примере NFA-автомат (и в примере его аналога DFA-автомата) мы всего лишь проверяем, является ли строка текстовым описанием целого числа или числа с плавающей точкой. Обычно желательно также вычислить интересующее число, а это усложняет код реализации переходов. Реализация этой функции при использовании DFA-автомата достаточно проста. Мы устанавливаем значение аккумуляторной (накопительной) переменной равным 0. При декодировании каждой цифры, расположенной перед десятичной точкой, мы умножаем значение аккумуляторной переменной на 10.0 и добавляем к нему значение новой цифры. Для цифр, следующих за десятичной точкой, мы поддерживаем значение счетчика текущего десятичного разряда и увеличиваем его на единицу при считывании каждой цифры. Для каждой такой цифры мы добавляем ее значение, умноженное на 0.1 в степени, соответствующей достигнутой десятичной позиции.
А как насчет NFA-автомата? Что ж, в этом случае решить задачу достаточно трудно. Вся сложность обусловлена необходимостью реализации алгоритма отхода. В любой момент времени внезапно может оказаться, что необходимо вернуться к предыдущему состоянию. В примере преобразования строки в число с плавающей точкой это не очень страшно: при заталкивании выбора в стек достаточно сохранить в нем и текущее значение аккумуляторной переменной (и значения всех необходимых дополнительных переменных). При выполнении отхода в качестве данных для восстановления состояния в момент неудачного выбора мы вытолкнем из стека и значение накопительной переменной.
Регулярные выражения
Теперь снова обратимся к теме, в связи с которой рассматривались NFA-автоматы. Поговорим о регулярных выражениях. Прежде всего, вспомним, что они собой представляют. По существу, регулярные выражения (regular expression) - это мини-язык простого описания шаблона, предназначенного для поиска текста (или, если говорить более строго, совпадающего с ним текста). В самой простой форме регулярное выражение состоит из слова или набора символов, Однако, используя стандартные метасимволы (или символы операций регулярного выражения), можно выполнять поиск более сложных шаблонов. Стандартными метасимволами являются "." (соответствует любому символу, кроме символа новой строки), "?" (соответствует нулю или более повторений предыдущего подвыражения), "*" (соответствует нулю или более повторений предыдущего подвыражения), "+" (соответствует одному или более повторений предыдущего подвыражения) и "|" (символ операции ИЛИ, которая устанавливает соответствие с левым или с правым подвыражением). Можно определить также класс символа для установки соответствия с одним из наборов символов. Если первым символом класса символов является "^", это означает отрицание класса. Т.е. символы класса не должны совпадать с остальными символами набора.
