| | end;
| end else if state = IntPart then begin
| | if Digit (Next) then begin
| | | state := IntPart; Move;
| | end else if Next = '.' then begin
| | | state := DecPoint; {после десятичной точки}
| | | Move;
| | end else begin
| | | state := Accept;
| | end;
| end else if state = DecPoint then begin
| | if Digit (Next) then begin
| | | state := FracPart; Move;
| | end else begin
| | | state := Error; {должна быть хоть одна цифра}
| | end;
| end else if state = FracPart then begin
| | if Digit (Next) then begin
| | | state := FracPart; Move;
| | end else begin
| | | state := Accept;
| | end;
| end else if
| | {такого быть не может}
| end;
end;
Заметьте, что присваивания state:=Accept и state:=Error не соп-
ровождаются сдвигом (символ, который не может быть частью числа,
не забирается).
Приведенная программа не запоминает значение прочитанного
числа.
5.2.2. Решить предыдущую задачу с дополнительным требовани-
ем: если прочитанный кусок является десятичной записью, то в пе-
ременную val:real следует поместить ее значение.
Решение. При чтении дробной части используется переменная
step - множитель при следующей десятичной цифре.
state := Initial; val:= 0;
while (state <> Accept) or (state <> Error) do begin
| if state = Initial then begin
| | if Next = ' ' then begin
| | | state := Initial; Move;
| | end else if Digit(Next) then begin
| | | state := IntPart; {после начала целой части}
| | | val := DigitValue (Next);
| | | Move;
| | end else begin
| | | state := Error;
| | end;
| end else if state = IntPart then begin
| | if Digit (Next) then begin
| | | state := IntPart; val := 10*val + DigitVal(Next);
| | | Move;
| | end else if Next = '.' then begin
| | | state := DecPoint; {после десятичной точки}
| | | step := 0.1;
| | | Move;
| | end else begin
| | | state := Accept;
| | end;
| end else if state = DecPoint then begin
| | if Digit (Next) then begin
| | | state := FracPart;
| | | val := val + DigitVal(Next)*step; step := step/10;
| | | Move;
| | end else begin
| | | state := Error; {должна быть хоть одна цифра}
| | end;
| end else if state = FracPart then begin
| | if Digit (Next) then begin
| | | state := FracPart;
| | | val := val + DigitVal(Next)*step; step := step/10;
| | | Move;
| | end else begin
| | | state := Accept;
| | end;
| end else if
| | {такого быть не может}
| end;
end;
5.2.3. Та же задача, если перед число может стоять знак
"минус" или знак "плюс" (а может ничего не стоять).
Формат чисел в этой задаче обычно иллюстрируют такой кар-
тинкой:
----- ---------
---| + |---->-| цифра |-------->--------------------->
| ----- | | --------- | | |
| ----- | | | | ----- --------- |
|-| - |--| |----<------| |-| . |->---| цифра |--|
| ----- | ----- | --------- |
| | |-----<-----|
|--->----|
5.2.4. Та же задача, если к тому же после числа может сто-
ять показатель степени десяти, как в 254E-4 (=0.0254) или в
0.123E+9 (=123000000). Нарисуйте соответствующую картинку.
5.2.5. Что надо изменить в программе задачи 5.2.2, чтобы
разрешить пустые целую и дробную части (как в '1.', '.1' или да-
же '.' - последнее число считаем равным нулю)?
Мы вернемся к конечным автоматам в главе 10 (Сравнение с
образцом).
Глава 6. Типы данных.
6.1. Стеки.
Пусть Т - некоторый тип. Рассмотрим (отсутствующий в паска-
ле) тип "стек элементов типа Т". Его значениями являются после-
довательности значений типа Т.
Операции:
Сделать_пустым (var s: стек элементов типа Т).
Добавить (t: T; var s: стек элементов типа Т).
Взять (var t: T; var s: стек элементов типа Т).
Пуст (s: стек элементов типа Т): boolean
Вершина (s: стек элементов типа Т): T
(Мы пользуемся обозначениями, наполняющими паскаль, хотя в
паскале типа "стек" нет.) Процедура "Сделать_пустым" делает стек
s пустым. Процедура "Добавить" добавляет t в конец последова-
тельности s. Процедура "Взять" определена, если последова-
тельность s непуста; она забирает из неё последний элемент, ко-
торый становится значением переменной t. Выражение "Пуст(s)" ис-
тинно, если последовательность s пуста. Выражение "Вершина(s)"
определено, если последовательность s непуста, и равно последне-
му элементу последовательности s.
Мы покажем, как моделировать стек в паскале и для чего он
может быть нужен.
Моделирование ограниченного стека в массиве.
Будем считать, что количество элементов в стеке не превос-
ходит некоторого числа n. Тогда стек можно моделировать с по-
мощью двух переменных:
Содержание: array [1..n] of T;
Длина: integer;
считая, что в стеке находятся элементы Содержание [1],...,Содер-
жание [длина].
Чтобы сделать стек пустым, достаточно положить
Длина := 0
Добавить элемент t:
{Длина < n}
Длина := Длина+1;
Содержание [Длина] :=t;
Взять элемент в переменную t:
t := Содержание [Длина];
Длина := Длина - 1;
Стек пуст, если Длина = 0.
Вершина стека равна Содержание [Длина].
Таким образом, вместо переменной типа стек в программе на паска-
ле можно использовать две переменные Содержание и Длина. Можно
также определить тип стек, записав
const N = ...
type stack = record
Содержание: array [1..N] of T;
Длина: integer;
end;
(Мы позволяем себе использовать имена переменных из русских
букв, хотя обычно паскаль этого не любит.) После этого могут
быть - в соответствии с правилами паскаля - описаны процедуры
работы со стеком. Например, можно написать
procedure Добавить (t: T; var s: stack);
begin
| {s.Длина , N}
| s.Длина := s.Длина + 1;
| s.Содержание [s.Длина] := t;
end;
Использование стека.
Будем рассматривать последовательности открывающихся и зак-
рывающихся круглых и квадратных скобок ( ) [ ]. Среди всех таких
последовательностей выделим правильные - те, которые могут быть
получены по таким правилам:
1) пустая последовательность правильна.
2) если А и В правильны, то и АВ правильна.
3) если А правильна, то [A] и (A) правильны.
Пример. Последовательности (), [[]], [()[]()][] правильны,
а последовательности ], )(, (], ([)] - нет.
6.1.1. Проверить правильность последовательности за время,
не превосходящее константы, умноженной на её длину. Предполага-
ется, что члены последовательности закодированы числами:
( 1
[ 2
) -1
] -2
Решение. Пусть a[1]..a[n] - проверяемая последовательность.
Рассмотрим стек, элементами которого являются открывающиеся
круглые и квадратные скобки (т. е. 1 и 2).
Вначале стек делаем пустым. Далее просматриваем члены пос-
ледовательности слева направо. Встретив открывающуюся скобку
(круглую или квадратную), помещаем её в стек. Встретив закрыва-
ющуюся, проверяем, что вершина в стеке - парная ей скобка; если
это не так, то можно утверждать, что последовательность непра-
вильна, если скобка парная, то заберем её (вершину) из стека.
Последовательность правильна, если в конце стек оказывается
пуст.
Сделать_Пустым (s);
i := 0; Обнаружена_Ошибка := false;
{прочитано i символов последовательности}
while (i < n) and not Обнаружена_Ошибка do begin
| i := i + 1;
| if (a[i] = 1) or (a[i] = 2) then begin
| | Добавить (a[i], s);
| end else begin {a[i] равно -1 или -2}
| | if Пуст (s) then begin
| | | Обнаружена_Ошибка := true;
| | end else begin
| | | Взять (t, s);
| | | Обнаружена ошибка := (t <> - a[i]);
| | end;
| end;
end;
Правильно := (not Обнаружена_Ошибка) and Пуст (s);
Убедимся в правильности программы. (1) Если последова-
тельность построена по правилам, то программа даст ответ "да".
Это легко доказать индукцией по построению правильной последова-
тельности. Надо проверить для пустой, для последовательности AB
в предположении, что для A и B уже проверено - и для последова-
тельностей [A] и (A) - в предположении, что для A уже проверено.
Для пустой очевидно. Для AB действия программы происходят как
для A и кончаются с пустым стеком; затем все происходит как для
B. Для [A] сначала помещается в стек открывающая квадратная
скобка и затем все идет как для A - с той разницей, что в глуби-
не стека лежит лишняя скобка. По окончании A стек становится
пустым - если не считать этой скобки - а затем и совсем пустым.
Аналогично для (A).
(2) Покажем, что если программа завершает работу с ответом
"да", то последовательность правильная. Рассуждаем индукцией по
длине последовательности. Проследим за состоянием стека в про-
цессе работы программы. Если он в некоторый промежуточный момент
пуст, то последовательность разбивается на две части, для каждой
из которых программа дает ответ "да"; остается воспользоваться
предположением индукции и определением правильности. Пусть стек
все время непуст. Это значит, что положенная в него на первом
шаге скобка будет вынута на последнем шаге. Тем самым, первый и
последний символы последовательности - это парные скобки, и пос-
ледовательность имеет вид (A) или [A], а работа программы (кроме
первого и последнего шагов) отличается от ее работы на A лишь
наличием лишней скобки на дне стека (раз ее не вынимают, она ни-
как не влияет на работу программы). Снова ссылаемся на предполо-
жение индукции и определение правильности.
6.1.2. Как упростится программа, если известно, что в пос-
ледовательности могут быть только круглые скобки?
Решение. В этом случае от стека остается лишь его длина, и
мы фактически приходим к такому утверждению: последовательность
круглых скобок правильна тогда и только тогда, когда в любом на-
чальном ее отрезке число закрывающихся скобок не превосходит
числа открывающихся, а для всей последовательности эти числа
равны.
6.1.3. Реализовать с помощью одного массива два стека, сум-
марное количество элементов в которых ограничено длиной массива;
все действия со стеками должны выполняться за время, ограничен-
ное константой, не зависящей от длины стеков.
Решение. Стеки должны расти с концов массива навстречу друг
другу: первый должен занимать места
Содержание[1] ... Содержание[Длина1],
а второй -
Содержание[n] ... Содержание[n - Длина2 + 1]
(вершины обоих стеков записаны последними).
6.1.4. Реализовать k стеков с элементами типа T, общее ко-
личество элементов в которых не превосходит n, с использованием
массивов суммарной длины C*(n+k), затрачивая на каждое действие
со стеками (кроме начальных действий, делающих все стеки пусты-
ми) время, ограниченное некоторой константой.
Решение. Применяемый метод называется "ссылочной реализаци-
ей". Он использует три массива:
Содержание: array [1..n] of T;
Следующий: array [1..n] of 0..n;
Вершина: array [1..k] of 0..n.
Массив Содержание будем изображать как n ячеек с номерами
1..n, каждая из которых содержит элемент типа T. Массив Следу-
ющий изобразим в виде стрелок, проведя стрелку из i в j, если
Следующий[i] = j. (Если Следующий[i] = 0, стрелок из i не прово-
дим.) Содержимое s-го стека (s из 1..k) хранится так: вершина
