                     Решения задач
                     -------------

6.2.4. Задача 4 (9 баллов)
Средний бал решений: 6.5 (72%)

 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> | <выражение>+<число> | <выражение>-<число>
<число>   ::= 0 | 1 | 2

   Задание. Напишите программу, которая вычисляет выражение, ес-
ли оно правильное,  или записывает на ленту сообщение "ош", если
запись содержит  ошибку. Если запись ошибочная, то дополнительно
к сообщению "ош" окошко должно указывать на первый неверный сим-
вол.
   Замечание 1. Значение выражения должно быть записано на ленте
в виде обычного целого десятичного числа.
   Замечание 2. Предполагается, что конечный и промежуточные ре-
зультаты вычислений  не  превышают числа, равного длине алфавита
Корректора.
   Замечание 3. Если конечный или промежуточный результат вычис-
ления выражения окажется меньше нуля, записать  на ленту сообще-
ние "ав" (авария)  и установить окошко на знак операции, которая
приводит к отрицательному результату.
   В начальный момент окошко расположено перед записью.

   Примеры работы программы:

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╥─┬─╦═╦─┬─┐
│░│░║░║1│-│1│+│2│░│░│    ─────>     │░│░│░│1│-│1║+│2║=║2│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╨─┴─╩═╩─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░║░║1│░│░│░│░│░│░│    ─────>     │░│░│░│1║=║1│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│.│7│+│1│░│░│    ─────>     │░│░│░│1║.║7│+│1│░│о│ш│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│-│2│+│1│░│░│    ─────>     │░│░│░│1║-║2│+│1│░│а│в│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘

Решение.

   Диаграмма переходов  практически повторяет аналогичную  схему
предыдущей задачи:


           ПУСТО                0,1,2         остальное
 (ответ) <────── (выражение) <──────── (вход) ──────────> (ошибка)
                     │   │               ^
                     │   │ +,-           │
            остальное│   │               │
(ошибка) <───────────┘   └───────────────┘

   Особенности этой задачи по отношению к  предыдущей связаны с
новым знаком "-" в записи:

   - В выражении  возможна операция вычитания, значит, это надо
учесть при работе с ящиком - накопителем результата.
   - Операция "-" заставляет нас проверять содержимое ящика пе-
ред "вычитанием". Ведь  если в ящике ПУСТО, команда МИНУС  приве-
дет к аварии "Не могу", а этого допустить нельзя.
   - В случае  предполагаемой аварии при вычитании окошко нужно
установить на соответствующий знак "-" в записи.

ЭТО вход0                             │Эта процедура подготавливает ящик перед
 ОБМЕН                                │входом в состояние (вход) алгоритма.
 ПИШИ ПУСТО                           │
 ОБМЕН                                │
 вход                                 │
КОНЕЦ                                 │
                                      │
ЭТО вход                              │Состояние (вход)
 ВПРАВО                               │Смотрим следующий символ.
 ЕСЛИ       0 ТО выражение            │Если это 0, переходим в состояние
 ИНАЧЕ ЕСЛИ 1 ТО добавить1            │(выражение) без вычислений. Если 1 или 2,
 ИНАЧЕ ЕСЛИ 2 ТО добавить2            │перед переходом в состояние (выражение)
 ИНАЧЕ ошибка                         │"добавим" число в ящик. Любой другой
КОНЕЦ                                 │символ в состоянии (вход) - ошибка.
                                      │"Добавление" числа в ящик происходит
                                      │с учетом предыдущего знака.  Если
                                      │перед числом ПУСТО или знак "+", оно
                                      │"складывается" с ящиком, если "-" -
                                      │"вычитается."
                                      │
ЭТО выражение                         │Состояние (выражение)
 ВПРАВО                               │Смотрим следующий символ.
 ЕСЛИ       +     ТО вход             │Если это "+" или "-", переходим в
 ИНАЧЕ ЕСЛИ -     ТО вход             │состояние (вход) - выражение продолжается.
 ИНАЧЕ ЕСЛИ ПУСТО ТО ответ            │Если это ПУСТО, выражение закончилось.
 ИНАЧЕ ошибка                         │Любой другой символ - ошибка.
КОНЕЦ                                 │
                                      │
ЭТО добавить1                         │Добавить к ящику 1 или вычесть из ящика
 ВЛЕВО                                │1 в зависимости от предыдущего
 ЕСЛИ  ПУСТО  ТО { ОБМЕН ПЛЮС д }     │символа:
 ИНАЧЕ ЕСЛИ + ТО { ОБМЕН ПЛЮС д }     │ПУСТО, "+" - добавить
 ИНАЧЕ                                │"-"        - вычесть
 {                                    │
   ОБМЕН                              │
   ЕСЛИ ПУСТО ТО { ОБМЕН авария }     │Если в ящике ПУСТО, обработать
   ИНАЧЕ         { МИНУС д }          │аварийную ситуацию
 }                                    │
КОНЕЦ                                 │
                                      │
ЭТО д                                 │
 ОБМЕН                                │
 ВПРАВО                               │
 выражение                            │
КОНЕЦ                                 │
                                      │
ЭТО добавить2                         │Добавить к ящику 2 или вычесть из ящика
 ВЛЕВО                                │2, в зависимости от предыдущего
 ЕСЛИ   ПУСТО ТО { ОБМЕН ПЛЮС ПЛЮС д }│символа:
 ИНАЧЕ ЕСЛИ + ТО { ОБМЕН ПЛЮС ПЛЮС д }│ПУСТО, "+" - добавить
 ИНАЧЕ                                │"-"        - вычесть
 {                                    │
   ОБМЕН                              │
   ЕСЛИ ПУСТО   ТО { ОБМЕН авария }   │Если в ящике ПУСТО или символ "0",
   ИНАЧЕ ЕСЛИ 0 ТО { ОБМЕН авария }   │обработать аварийную ситуацию.
   ИНАЧЕ { ПОВТОРИ 2 МИНУС д }        │
 }                                    │
КОНЕЦ                                 │
                                      │
ЭТО ошибка                            │Идем рекурсивно от ошибочного символа
 ВПРАВО                               │до конца записи, сжимая рекурсивную
 ЕСЛИ ПУСТО                           │пружину. Записываем в конце записи
  ТО ответ_ошибка                     │сообщение об ошибке и под воздействием
  ИНАЧЕ ошибка                        │энергии пружины возвращаем окно
 ВЛЕВО                                │на место ошибки.
КОНЕЦ                                 │
                                      │
ЭТО авария                            │
 ВПРАВО                               │
 ЕСЛИ ПУСТО                           │
  ТО ответ_авария                     │
  ИНАЧЕ авария                        │
 ВЛЕВО                                │
КОНЕЦ                                 │
                                      │
ЭТО ответ_ошибка                      │
 ВПРАВО                               │
 ПИШИ о                               │
 ВПРАВО                               │
 ПИШИ ш                               │
 ПОВТОРИ 2 ВЛЕВО                      │
КОНЕЦ                                 │
                                      │
ЭТО ответ_авария                      │
 ВПРАВО                               │
 ПИШИ а                               │
 ВПРАВО                               │
 ПИШИ в                               │
 ПОВТОРИ 2 ВЛЕВО                      │
КОНЕЦ                                 │
                                      │
ЭТО ответ                             │Подготовка к записи значения выражения
 ВПРАВО ВПРАВО                        │в виде числа на ленту.
 ПИШИ 0                               │Алгоритм: к числу 0 на ленте прибавлять
 ответ1                               │1, а символ в ящике заменять на
КОНЕЦ                                 │предыдущий, пока в ящике не окажется
                                      │символ ПУСТО.
                                      │
ЭТО ответ1                            │Запись результата вычислений.
 ПОКА НЕ ПУСТО ВПРАВО                 │Установить окошко на последний символ
 ВЛЕВО                                │текущего значения результата.
 ОБМЕН                                │Посмотреть, что в ящике.
 ЕСЛИ НЕ ПУСТО                        │Если в ящике нет символа ПУСТО:
  ТО                                  │- заменить символ в ящике на предыдущий;
  {                                   │- к результату на ленте прибавить 1;
    МИНУС                             │- повторить алгоритм с самого начала.
    ОБМЕН                             │
    плюс1                             │
    ответ1                            │
  }                                   │Если в ящике символ ПУСТО, формирование
  ИНАЧЕ ответ2                        │результата закончено. Остается записать
КОНЕЦ                                 │перед ним символ "=" и закончить работу.
                                      │
ЭТО ответ2                            │
  ОБМЕН                               │
  ПОКА НЕ ПУСТО ВЛЕВО                 │
  ПИШИ =                              │
КОНЕЦ                                 │
                                      │
ЭТО плюс1                             │
 ЕСЛИ 9 ТО    девять                  │
        ИНАЧЕ ПЛЮС                    │
КОНЕЦ                                 │
                                      │
ЭТО девять                            │
 ПОКА 9 { ПИШИ 0 ВЛЕВО }              │
 ЕСЛИ НЕ ЦИФРА                        │
   ТО    ПИШИ 1                       │
   ИНАЧЕ ПЛЮС                         │
КОНЕЦ                                 │


   Большинство  программ,  присланных  на конкурс, работает  по
многопроходным алгоритмам, что, конечно, не является  оптималь-
ным.
