| | 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) хранится так: вершина
равна Содержание[Вершина[s]], остальные элементы s-го стека мож-
но найти, идя по стрелкам - до тех пор, пока они не кончатся.
При этом (s-ый стек пуст) <=> Вершина[s] = 0.
Стрелочные траектории, выходящие из Вершина[1], ..., Верши-
на[k] (из тех, которые не равны 0) не должны пересекаться. Поми-
мо них, нам понадобится еще одна стрелочная траектория, содержа-
щая все неиспользуемые в данный момент ячейки. Ее начало мы бу-
дем хранить в переменной Свободная (равенство Свободная = 0 оз-
начает, что пустого места не осталось). Вот что получается:
n=8 | a | p | q | d | s | t | v | w |
k=2 | | | Свободная
Содержание = , Следующий = <3,0,6,0,0,2,5,4>
Вершина = <1, 7>, Свободная = 8
Стеки: 1-ый: p t q a (a-вершина); 2-ой: s v (v-вершина).
procedure Начать_работу; {Делает все стеки пустыми}
| var i: integer;
begin
| for i := 1 to k do begin
| | Вершина [i]:=0;
| end;
| for i := 1 to n-1 do begin
| | Следующий [i] := i+1;
| end;
| Свободная:=1;
end;
function Есть_место: boolean;
begin
| Есть Место := (Свободная <> 0);
end;
procedure Добавить (t: T; s: integer);
| {Добавить t к s-му стеку}
| var i: 1..n;
begin
| {Есть_место}
| i := Свободная;
| Свободная := Следующий [i];
| Вершина [s] :=i;
| Содержание [i] := t;
| Следующий [i] := Вершина [s];
end;
function Пуст (s: integer): boolean; {s-ый стек пуст}
begin
| Пуст := (Вершина [s] = 0);
end;
procedure Взять (var t: T; s: integer);
| {взять из s-го стека в t}
| var i: 1..n;
| begin
| {not Пуст (s)}
| i := Вершина [s];
| t := Содержание [i];
| Вершина [s] := Следующий [i];
| Следующий [i] := Свободная;
| Свободная := i;
end;
6.2. Очереди.
Значениями типа "очередь элементов типа T", как и для сте-
ков, являются последовательности значений типа T. Разница состо-
ит в том, что берутся элементы не с конца, а с начала (а добав-
ляются по-прежнему в конец).
Операции с очередями.
Сделать_пустой (var x: очередь элементов типа T);
Добавить (t: T, var x: очередь элементов типа T);
Взять (var t: T, var x: очередь элементов типа T);
Пуста (x: очередь элементов типа T): boolean;
Очередной (x: очередь элементов типа T): T.
