5.1.1. В тексте возведение в степень обозначалось двумя
идущими подряд звездочками. Решено заменить это обозначение на
'^' (так что, к примеру, 'x**y' заменится на 'x^y'). Как это
проще всего сделать? Исходный текст разрешается читать символ за
символом, получающийся текст требуется печатать символ за симво-
лом.
Решение. В каждый момент программа находится в одном из
двух состояний: "основное" и "после звездочки"
Состояние Очередной Новое Действие
входной символ состояние
основное * после нет
основное x <> '*' основное печатать x
после * основное печатать '^'
после x <> '*' основное печатать *, x
Замечание. При этом '***' заменится на '^*' (но не на '*^'). В
условии задачи мы не оговаривали деталей, как это часто делается
- предполагается, что программа "должна действовать разумно". В
данном случае, пожалуй, самый простой способ объяснить, как
программа действует - это описать ее состояния и действия в них.
5.1.2. Написать программу, удалающую из текста подслова ви-
да 'abc'.
5.1.3. В паскале комментарии заключаются в фигурные скобки:
begin {начало цикла}
i:=i+1; {увеличиваем i на 1}
Написать программу, которая удаляла бы комментарии и вставляла
бы вместо исключенного комментария пробел (чтобы '1{один}2'
превратилось бы не в '12', а в '1 2').
Решение. Программа имеет два состояния: "основное" и "внут-
ри комментария".
Состояние Очередной Новое Действие
входной символ состояние
основное { внутри нет
основное x <> '{' основное печатать x
внутри } основное печатать пробел
внутри x <> '}' внутри нет
Замечание. Эта программа не воспринимает вложенные коммен-
тарии: строка вроде
'{{комментарий внутри} комментария}'
превратится в
' комментария}'
(в начале стоят два пробела). Обработка вложенных комментариев
конечным автоматом невозможна (нужно "помнить число скобок" - а
произвольное натуральное число не помещается в конечную память).
5.1.4. В паскалевских программах бывают также строки, зак-
люченные в кавычки. Если фигурная скобка стречается внутри стро-
ки, то она не означает начала или конца комментария. В свою оче-
редь, кавычка в комментарии не означает начала или конца строки.
Как изменить программу, чтобы это учесть?
Указание. Состояний будет три: основное, внутри коммента-
рия, внутри строки.
5.1.5. Еще одна возможность многих реализаций паскаля - это
комментарии вида
i:=i+1; (* here i is increased by 1 *)
при этом закрывающая скобка должна соответствовать открываюшей
(то есть { ... *) не разрешается). Как удалять такие коммента-
рии?
Пусть десятичная запись числа подается на вход программы
символ за символом. Мы хотим "прочесть" это число (поместить в
переменную типа real его значение). Кроме того, надо сообщить об
ошибке, если число записано неверно.
Более конкретно, представим себе такую ситуацию. Последова-
тельность символов на входе делится на прочитанную и оставшуюся
части. Мы можем пользоваться функцией Next:char, которая возвра-
щает первый символ оставшей части, а также функцией Move, кото-
рая перводит забирает первый символ из оставшейся части, перево-
дя его в категорию прочитанных.
---------------------|--------------------------
прочитанная часть | Next | ? | ? | ? |
---------------------|--------------------------
Будем называть десятичной записью такую последовательность сим-
волов:
<0 или более пробелов> <1 или более цифр>
а также такую:
<0 или более пробелов> <1 или более цифр>.<1 или более цифр>
Заметим, что согласно этому определению '1.', '.1', '1. 1',
'-1.1' не являются десятичными записями. Сформулируем теперь за-
дачу точно:
5.2.1. Прочесть из входной строки максимальную часть, кото-
рая может быть началом десятичной записи. Определить, является
ли эта часть десятичной записью или нет.
Решение. Запишем программу на паскале (используя "перечис-
лимый тип" для наглядности записи: переменная state может прини-
мать одно из значений, указанных в скобках).
var state:
(Accept, Error, Initial, IntPart, DecPoint, FracPart);
state := Initial;
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; {после начала целой части}
| | | Move;
| | end else begin
| | | state := Error;
| | 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 (Сравнение с
образцом).