                 Транслятор?.. Это очень просто!
                      (часть 3 и последняя)

Дуванов Александр Александрович
duvanov@robotland.users.botik.ru
Осень, 1999 Переславль-Залесский


                                       И все доступно уж, эхма!
                                       Теперь для нашего ума!

                                  Николай Носов (стихи Цветика)


   Дорогой читатель! Вы еще со мной? Если это  так, то усаживай-
тесь поудобнее и  пристегните  ремни: виражи сегодня будут очень
крутые!
   Для начала  мы построим примитивный безыдейный транслятор для
перевода записи арифметического примера в число  - результат вы-
числений. Это  для  разминки.  Никаких  открытий, только здравый
смысл.
   Затем, разогревшись, мы вступим в сферы  перевода на польский
и вычислений на стеке.
   Если Вы ограничите свое чтение только "примитивным транслято-
ром", я не обижусь.  Ну, а если, пойдете за мной до  конца, буду
аплодировать как союзникам! (Ведь можно было  отложить в сторону
трансляторы, пойти в  баню  попариться, попить пива. Ладно, буду
делать это на гонорар, который выдаст мне Сергей Львович!)

Примитивный транслятор
----------------------

   Вторая часть этих публикаций содержала конкурсную задачу Кор-
ректора под номером 4. Рассмотрим ее решение.

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

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

   В начальный момент окошко расположено перед записью.

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

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

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

Решение.

 Диаграмма переходов здесь очень проста:

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


   Однако, нам нужно не просто проверить выражение, но и вычис-
лить его.  Поэтому в программе появляются дополнительные проце-
дуры, связанные не  с переходом в другие состояния алгоритма, а
с вычислениями.

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


   Вероятно вас немного удивило замечание 2 в условии задачи:

   Замечание 2. Предполагается, что результат вычислений выраже-
ния меньше числа, равного длине алфавита Корректора.

   Теперь, конечно, понятна причина этого ограничения!
   Ведь обычная  операция  "+1"  подменяется  в среде Корректора
операцией ПЛЮС, которая совсем не арифметическая:
1)  ПЛЮС (от ПУСТО) = 0
2)  ПЛЮС (от 0)     = 1
3)  ПЛЮС (от 1)     = 2
    ....
11) ПЛЮС (от 9)     = а
12) ПЛЮС (от а)     = б
....
l)  ПЛЮС (от последнего символа алфавита) = "Не могу"

   Видно, что "сумматор" Корректора переполняется на l-ой опера-
ции ПЛЮС (l - число символов в алфавите Корректора).

   Пожалуй, самое интересное место в приведенной выше программе -
процедура "плюс1". Она добавляет к целому числу на ленте единицу.
   Вот примеры ее работы:

Начальное состояние                 После работы процедуры
┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┐               ┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┐
│░│░│░│1│2║7║░│░│░│░│    ─────>     │░│░│░│1│2║8║░│░│░│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┘               ┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┘

Начальное состояние                 После работы процедуры
┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░│░│1│2║9║░│░│░│░│    ─────>     │░│░│░│1║3║0│░│░│░│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘

Начальное состояние                 После работы процедуры
┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┐               ┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░│░│9│9║9║░│░│░│░│    ─────>     │░│░║1║0│0│0│░│░│░│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┘               ┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘

   Заметьте, что процедура "плюс1" работает на  основе цикла ПО-
КА, хотя можно было бы  предложить  и  рекурсивный вариант.
   Однажды эта задача решалась в семье Куков, знакомых читателям
"Информатики" по публикации "Введение  в  Интернет" ("Информати-
ка", N21, 1999).

   Давайте послушаем (из любопытства), как "тронутые" информати-
кой Куки строят свое рекурсивное решение.

   Папа. Научим Корректора выполнять арифметические операции над
числами!
   Вася. В его СКИ нет нужных команд.
   Папа. Сделаем это при помощи хитрости.
   Петя. А какие числа мы будем рассматривать?
   Папа. Давайте займемся арифметикой целых неотрицательных  чи-
сел и,  чтобы не говорить  каждый раз так длинно, будем называть
их просто числами. Вот первая задача.

   Задача. К числу на  ленте  прибавить единицу. В начальный мо-
мент в окно видна младшая цифра.

   Вася. Ну, такую задачу мы уже решали. Решением является един-
ственная команда ПЛЮС.
   Папа. В той  задаче, которую мы решали, говорилось о сложении
единицы с четным числом и это было не случайно.
   Петя. Проблема заключается в возможном окончании числа на де-
вять, ведь  в этом случае  команда ПЛЮС запишет на место девятки
букву "а" (она идет следом за символом "9" в алфавите исполните-
ля).
   Вася. Да, я поспешил... А что же делать, если младшая цифра у
числа - девять?
   Петя. Ну, понятно, вместо нее надо записать ноль, затем необ-
ходимо прибавить единицу  к следующему разряду или, что тоже са-
мое, прибавить единицу к исходному числу без последней цифры.
   Папа. Посмотри, решая исходную  задачу  ты снова пришел к ней
же самой, но с меньшим  количеством цифр в числе. Как называется
такой прием?
   Петя. Конечно это рекурсия!
   Вася. Пусть число на ленте равно 239. Вместо  цифры "9" запи-
сываем ноль и прибавляем 1 к числу 23.  Получается 240.
   Папа. А если на ленте число 299?
   Вася. Самую младшую девятку заменим нулем, и прибавим единицу
к числу 29. Здесь та же проблема: девятку в числе 29 заменим ну-
лем и прибавим один к числу 2. В итоге получается 300!
   Петя. Я придумал красивую схему. Давайте обозначим нашу зада-
чу так:
                         Плюс1(299)
   Эта запись будет показывает, что нужно прибавить один к числу
299. Теперь решение можно записать так:
          Плюс1(299) = Плюс1(29)0 = Плюс1(2)00 = 300
  Ведь, известно, что
          Плюс1(...0) = ...1
          Плюс1(...1) = ...2
          Плюс1(...2) = ...3
            ....
          Плюс1(...8) = ...9
   Папа. Схема мне  понравилась, в ней очень хорошо видна рекур-
сивность. А как решить задачу для числа 99?
   Петя. Запишем так:
               Плюс1(99) = Плюс1(9)0 = Плюс1()00
   Понятно! Нужно предусмотреть в решении "плюс  один от пустого
места" и результат должен равняться числу один. Пустое место по-
лучается как бы равнозначно нулю:

               Плюс1()   = 1 и тогда
               Плюс1(99) = Плюс1(9)0 = Плюс1()00 = 100

   Папа. Что то я не слышу ничего от Васи!
   Вася. Я успеваю  только с трудом следить за вашими схемами...
Но кажется  я  все  понял.  В  качестве доказательства записываю
программу для Корректора:

ЭТО Плюс1
 ЕСЛИ НЕ 9 ТО ПЛЮС  // Если последняя цифра не 9
   ИНАЧЕ            // задача решается командой ПЛЮС.
   {                // Когда число заканчивается на 9
     ПИШИ 0         // заменяем девятку нулем и
     ВЛЕВО          // добавляем 1 к "сокращенному" числу
     Плюс1
   }
КОНЕЦ

   Петя. В твоей программе упущен случай, когда число состоит из
одних девяток.
   Вася. Да, действительно. Такое число приводит к необходимости
обработать пустую клетку:

ЭТО Плюс1
 ЕСЛИ НЕ 9         // Если последняя цифра
   ТО              // не 9, то ...
   {
     ЕСЛИ ПУСТО    // Если пусто, то
      ТО    ПИШИ 1 // записываем 1,
      ИНАЧЕ ПЛЮС   // иначе заменяем на
   }               // следующий по алфавиту символ.
   ИНАЧЕ
   {               // Когда число заканчивается
     ПИШИ 0        // на 9, заменяем девятку
     ВЛЕВО         // нулем и добавляем один к
     Плюс1         // числу слева.
   }
КОНЕЦ

   Папа. По последнему  решению  нет никаких замечаний.
   Петя. Вася, как ты  думаешь,  сколько раз надо запустить нашу
программу, чтобы убедиться в правильности ее работы?
   Вася. Думаю, минимум 3 раза. Первый раз для числа, которое не
оканчивается девяткой, например,  для  числа 458, второй раз для
числа у которого первая цифра не девять, а  последние - девятки,
например, для числа 57999 и третий раз для  числа, состоящего из
одних девяток, например, для  числа  9999. Тем самым мы проверим
все ветвления нашей программы.
   Петя.  Молодец!  Проверка программ  называется тестированием.
Тестирование должно  быть спланировано по возможности так, чтобы
в программе проработали  все ее части во всех возможных комбина-
циях. Исходные данные которые обрабатывает проверяемая программа
называются тестами.  Для  каждого  теста  нужно подготовить кон-
трольный результат, который затем сравнивается с результатом ра-
боты программы.  Обычно результаты тестирования оформляют в виде
таблицы. Для твоих тестов таблица будет иметь вид:
    ┌──────┬───────────────────┬─────────────┬─────────────┐
    │ Тест │Что проверяется    │ Контрольный │ Результат по│
    │      │                   │ результат   │ программе   │
    ├──────┼───────────────────┼─────────────┼─────────────┤
    │ 458  │Младший разряд не 9│  459        │             │
    │ 57999│Число заканчивается│  59000      │             │
    │      │девятками          │             │             │
    │ 9999 │Число  состоит   из│  10000      │             │
    │      │одних девяток      │             │             │
    └──────┴───────────────────┴─────────────┴─────────────┘

   Вася занялся тестированием программы и все тесты прошли хоро-
шо: результаты  программы  совпали  с контрольными результатами.
   Петя. Тестирование - это очень важный  элемент труда програм-
миста. Ведь в программе очень легко допустить ошибку  и не заме-
тить  этого.  Ошибка может затаиться в какой-нибудь очень  редко
работающей ветви программы, предусмотренной для обработки особо-
го случая. Представь себе, что твоя программа является элементом
какой-нибудь очень важной системы, управляющей космическим поле-
том и ветвь обрабатывающая одни девятки содержит ошибку. На вход
программы поступают  числа,  которые  она  должна увеличивать на
один. Вероятность  того,  что  появится  число  из одних девяток
очень мала. Программа долгое время будет работать прекрасно, но,
когда на вход поступит 99, аппарат собьется с курса и упадет на
Солнце.
   Вася. Ну, а если  программу  протестировали, то теперь то уж,
все в порядке, и можно спать спокойно.
   Петя. Увы!  Программист  никогда  не спит спокойно. Представь
себе, что обработку  одних девяток ты не предусмотрел в алгорит-
ме. Тогда в  программе эта ветвь будет отсутствовать и, конечно,
"девяточный" тест  ты  заготавливать просто не будешь. Остальные
тесты пройдут нормально,  ты  уснешь спокойно, а космический ко-
рабль упадет на Солнце.
   Вася. Вот это да! А как же проверять  программы и избавляться
от ошибок?
   Папа.  Теме  тестирования программ был посвящен один из  моих
репортажей. Обычно  это происходит так. Сначала программу прове-
ряет автор. Когда он исправляет в ней "последнюю" ошибку, то пе-
редает ее эксперту - специалисту по  тестированию. В коллективе,
занимающимся разработкой программ, такие специалисты просто  не-
обходимы. Они подобно музыкальным или литературным критикам име-
ют особый склад мышления, направленный на  выявление самых неза-
метных, глубоко  спрятанных изъянов и погрешностей. Когда специ-
алист по тестированию выдыхается (все его самые изощренные тесты
проходят нормально), программа поступает в опытную эксплуатацию,
где длительное  время обрабатывает данные, приближенные к реаль-
ным. Только потом она передается потребителю и все  равно в ней,
как правило, остается некоторое количество ошибок.
   Вася. Вот это да... Все так безнадежно?
   Папа. Увы, все большие программы именитых солидных фирм с ко-
торыми  я  постоянно работаю, и компьютерная оболочка Windows, и
текстовый процессор Word  и  табличный процессор Excel, время от
времени работают  неправильно  или  попросту "зависают", то-есть
перестают  реагировать  на нажатие клавиш и перемещение мыши.  В
этом случае помогает только перезагрузка компьютера.
   Вася.  Иными  словами как не тестируй, а космический  аппарат
все равно упадет на солнце?
   Папа. В  очень  ответственных  случаях вычисления выполняются
одновременно по нескольким разным программам, написанным по раз-
ным алгоритмам и в качестве результата  принимается тот, который
выдали большинство программ.

        Извините, дорогой  читатель,  что  не прервал моих увлеченных
     Куков и они незаметно перешли от "плюс один" к вопросам тестиро-
     вания  программ!  Это потому, что третьего дня  мой  виндоус  не
     просто завис, а  умер!  Пришлось его устанавливать заново. Спра-
     ведливости ради хочу отметить, что виндоус погиб не сам по себе,
     а из  возникшего "плохого" блока  на винчестере. Два дня из моей
     жизни выпали на реанимацию компьютера. Кто-то сказал, что вопрос
     не в том, "полетит"  винт или нет, а вопрос: когда? А  Вы хорошо
     подготовились к полету?  Копии  Ваших данные хранятся в надежном
     месте?


   Ну, а теперь рассмотрим по-настоящему сложную задачу. Она то-
же предлагалась в прошлом году  на  турнире  юных программистов и,
представьте,  нашлись  дети, которые ее решили. Это меня  сильно
огорчило. Задача была  специально  предложена для того, чтобы ее
никто не решил. Думал будет повод нравоучению: "Вот  вам и прос-
той Корректор! Слабо! Дело ребята, не  в среде программирования,
а в методах, приемах и опыте".
   Меня  оконфузили  ребята  из волгоградской команды  Владимира
Анатольевича Петрова. Обычный максимальный бал в турнирных зада-
чах - 10. Для этой задачи  я смело поставил 15. И ребята его за-
работали!


Задача. (15 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> |                            (1)
                <выражение>-<выражение> |            (2)
                <выражение>+<выражение> |            (3)    (*)
                (<выражение>)                        (4)
<число>   ::=  1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9     (5)

   Задание. Напишите  программу, которая проверяет  правильность
записи выражения. Если запись правильная, то  нужно  за  ней  на
ленте записать  результат вычисления выражения, в противном слу-
чае - сообщение "ош" и установить окошко на первый неверный сим-
вол или на место обнаружения ошибки в случае ошибок со скобками.
   В начальный момент окошко расположено  перед  записью.

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

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

Начальное состояние                 После работы программы
┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐          ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┐
│░║░║8│-│(│4│-│(│1│)│)│░│  ─────>  │░│░│8│-│(│4│-│(│1│)│)║=║5│░│
┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘          ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┘
Начальное состояние                После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┐          ┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┐
│░│░║░║2│-│(│1│░│░│░│░│░│  ─────>  │░│░│░│2│-│(│1║░║о│ш│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┘          ┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┘

                             * * *

   Определение выражения, приведенное в условии задачи,  содер-
жит скачок сложности из-за наличия безобидной на первый взгляд,
строки с круглыми скобками.
   До сих пор рекурсивность определений была простой и достаточ-
но очевидной.
  В самом деле, из записи

  <число> ::= <цифра> | <цифра> <число>
  <цифра> ::= 0 | 1

совершенно понятно, что число - это любая последовательность из
нулей и единиц.
   Скромная строка  (<выражение>)  в определении (*)  позволяет
считать выражениями записи типа:

         (1+(7-(9+8)))
         7+(8)-(1-7)+6
         и так далее.

   Иными словами  определение (*) почти соответствует нашему ин-
туитивному представлению о том, какие могут  быть обычные записи
с круглыми скобками.  Почему  почти? Ну, например, запись 5-(-3)
выражением в смысле определения не будет, в то время как в обыч-
ной жизни  это  совершенно  нормальная  запись, значение которой
равно 8.
   Понять и почувствовать это не так-то и просто для новичка.
   Докажем, например, что запись 7+(6-(5)) является  выражением
в смысле определения (*).
   Из (2) следует, что запись 7+(6-(5))  будет выражением, если
выражением является запись (6-(5)).
   Из  (4)  следует, что запись (6-(5)) будет выражением,  если
выражением является запись 6-(5).
   Из (3) следует,  что запись 6-(5) будет выражением, если вы-
ражением является запись (5).
   Из (4) следует,  что запись (5) будет выражением, если выра-
жением является запись 5.
   Но  запись  5  - это выражение из (1), ведь 5 - это число из
(5).
   Поработать с  рекурсивными  определениями  очень полезно. Эта
область информатики находится на границе математики и лингвисти-
ки.

Еще несколько иллюстраций.

Примеры выражений:
1) (2)
2) ((2))
3) (2+3)
4) (2+3-7)
5) (2+3)-(7+6)
6) ((2+3)-(7+6))
7) (2)-(7)
8) ((2)-(7))
9) ((2+3)-(7+6))+5

Примеры записей с ошибками:
1)  ()
2)  (2 (+3))
3)  (2+3))
4)  )2(
5)  (2+3
6)  1+(-5)

   Докажем, что запись 6) выражением  не  является.  Она была бы
выражением по (*), если бы выражением была запись (-5). А запись
(-5) была  бы выражением, если  бы выражением была запись -5. Но
последняя запись выражением не является, ибо ни одна часть опре-
деления (*) под разборку записи "-5" не подходит.
   Последний пример расходится с нашим представлением о правиль-
ных выражениях со  скобками. Это происходит потому, что число со
знаком в обычном понимании не является числом в смысле определе-
ния (*). По определению (*) число  - это цифра и знака не содер-
жит.

   Лексический анализатор  основан на диаграмме переходов из од-
ного состояния  в  другие  плюс  дополнительный  подсчет баланса
круглых скобок (на схеме он не отражен):

                                        (ошибка)
                                           ^
                                  остальное│
                                           │ ┌──┐
                                           │ │  │)
                       ┌─────────────────┐ │ │  │
                       │                 V │ │  V  ПУСТО
                       │                 (скобка)) ────────── (ответ)
                       │)                  │+,-
                       │                   │
                       │                   │
           ПУСТО       │        цифра      V      остальное
 (ответ) <──────── (число) <───────── (  вход  ) ──────────> (ошибка)
                     │   │              ^ │   ^
                     │   │ +,-          │ │   │
            остальное│   │              │ │   │
(ошибка) <───────────┘   └──────────────┘ │   │
                                          │(  │
                                          │   │
                                          └───┘

   Для слежения  за  балансом  круглых скобок можно использовать
ящик -  Корректора  (изначально пустой). На каждой открывающейся
скобке нужно применить к ящику операцию ПЛЮС, а на каждой закры-
вающейся - МИНУС. Если  после  просмотра всего выражения ящик не
будет пуст, это ошибка - баланс скобок в записи нарушен.
   Итак, диаграмма состояний будет  "следить"  за правомочностью
появления круглой скобки в данном месте записи, а ящик -  за ба-
лансом скобок во всей записи в целом.
   Если, например, за числом  расположена  открывающаяся скобка
(ошибка!), то диаграмма состояний этот случай предусматривает.
   А вот распознать ошибку в записи  "2+3)" диаграмма бессильна!
Ведь закрывающаяся скобка  за  числом - ситуация вполне нормаль-
ная. Но эта ошибка не "пройдет" после анализа содержимого ящика.

   Основываясь  на  высказанных  выше идеях, записать  программу
анализатора очень легко, и поэтому здесь не она приводится.
   Сейчас нас больше всего интересует не  лексический анализ вы-
ражения, а его вычисление. Вот  уж  здесь  действительно  скачок
сложности сразу на несколько порядков!

   Первый вариант  решения (который, кстати и реализовали ребята
Владимира Анатольевича) выглядит так. Нужно искать в записи пару
круглых скобок (...), таких,  которые  внутри себя скобок уже не
содержат. Далее нужно  вычислить  выражение внутри этих скобок и
вставить результат на  ленту,  заменив им всю конструкцию (...).
Такие действия нужно повторять до тех пор, пока в исходном выра-
жении скобок уже не останется.
   Алгоритмы, которые просматривают запись много раз, называются
многопроходными. Описанный выше алгоритм ОЧЕНЬ многопроходной, а
значит, не оптимальный.
   В "большой" информатике используют другой метод:
   - переводят исходное выражение в обратную польскую запись;
   - вычисляют польскую запись на стеке.
   Этот алгоритм  популярен  еще  по одной существенной причине:
один раз переведя выражение в польскую  (бесскобочную) запись, в
дальнейшем можно  многократно производить по нему быстрые вычис-
ления. Это  особенно актуально, если выражение содержит перемен-
ные (параметры).

Запись выражения по-польски и стековые вычисления
-------------------------------------------------

   Самой первой темой  в  нашем университетском курсе "Азы прог-
раммирования" обозначен блок, связанный с исполнителем Плюсик.

   (В этом  месте моя собака  Мики, следящая за тем, что пишется
на экране, удивленно посмотрела на меня и покачала головой: "Ни-
чего себе АЗЫ! Для пятиклассников!")

   Помнится мне, что кто-то из руководителей команд сомневался в
нужности Плюсика для этих самых азов программирования. Мол, Плю-
сик с "настоящим" программированием никак не связан!
   Однако в именно  в настоящем трансляторе без Плюсика никак не
обойтись.

   Плюсик - это модель стекового калькулятора. Среда исполните-
ля состоит из стека и вычислителя:

               ┌───────┐   ┌───────────┐
               │ Стек  │   │Вычислитель│
               └───────┘   └───────────┘

   Стек служит для хранения чисел.  Числа  помещаются  в стек по
одному, подобно  тому, как кольца детской пирамидки нанизываются
на стержень. За один раз взять из стека можно только  одно число
с вершины числовой пирамиды. Копия числа в стеке не сохраняется,
зато становится доступным следующее число, расположенное  "ниже"
взятого.

                 Система команд Плюсика

ЗАПОМНИ число - Число, записанное в команде отправляется на хра-
                нение в стек.

              │ Все  эти  команды  работают одинаково: из  стека
              │ последовательно извлекаются два  числа и отправ-
              │ ляются в вычислитель для выполнения соответству-
 СЛОЖИ        │ ющей арифметической  операции. Результат помеща-
 ВЫЧТИ        │ ется в стек.
 УМНОЖЬ       │ Второе число  из  извлеченной из стека пары, вы-
 ДЕЛИ         │ числитель считает первым операндом операции.
              │ Ситуация отказа возникает когда: в  стеке
              │ меньше двух  чисел;  результат вычислений -
              │ отрицательное число; или  выполняется деление на
              │ 0.
              │ Команда ДЕЛИ выполняет деление нацело.

ОЧИСТИ        - Выполнение этой команды приводит к  автоматичес-
                кому удалению всех чисел из стека.


   Сосчитать выражение типа 8-(2+3) задача не из легких! Практи-
чески все трансляторы для вычисления таких выражений сначала пе-
реводят его в обратную польскую запись, а уж потом, подобно Плю-
сику, вычисляют на стеке.

   Прошу прощения!  Я до сих  пор еще не объяснил устройство об-
ратной польской записи арифметических выражений!
   В обычной  записи знак операции располагается между операнда-
ми, а в обратной польской - после. Вот и все!

  Обычная запись операции:  a+b
  Обратная польская запись: ab+

  Обычная запись выражения:  a + b * (c + d/e)/f
  Обратная польская запись того же выражения: abcde/+*f/+

        Запись типа  +ab  выражения  a+b называется польской потому,
     что впервые была  введена  польским философом (!) Лукашевичем в
     связи с формулами символической  логики.  Соответственно запись
     типа ab+ для  суммы двух чисел называется обратной польской за-
     писью.
        Иными словами прямая польская запись базируется на структуре:

               <операция> <операнд> <операнд>

        А обратная  польская  запись  (которая  нас  интересует)  на
     структуре:

               <операнд> <операнд> <операция>

        В некоторых источниках обратная  польская  запись называется
     постфиксной, а  прямая  - префиксной. Этимология таких названий
     совершенно прозрачна.
        У.Маккиман, Дж.Хорнинг, Д.Уортман в книге "Генератор  компи-
     ляторов" называют обычную запись выражений - инфиксной записью,
     а польскую - суффиксной.

Сравните:
-  обычная запись выражения:  2 + 5 * (1 + 3/2)/7
-  обратная польская запись выражения:  2 5 1 3 2 / + * 7 / +
-  программа для Плюсика:
                         ЗАПОМНИ 2
                         ЗАПОМНИ 5
                         ЗАПОМНИ 1
                         ЗАПОМНИ 3
                         ЗАПОМНИ 2
                         ДЕЛИ
                         СЛОЖИ
                         УМНОЖЬ
                         ЗАПОМНИ 7
                         ДЕЛИ
                         СЛОЖИ

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

                      2 5 1 3 2 / + * 7 / +

он должен рассматривать как запись программы работы со стеком
и вычислителем

   Алгоритм работы нового Плюсика должен быть таким:

В начальный момент стек пуст.
Продолжать, пока запись-программа  не закончится:
   - Если очередной элемент записи -  число,  поместить  его  в
     стек и перейти к следующему элементу записи.
   - Если очередной  элемент  записи  -  операция, выполнить ее
     следующим образом:
     - извлечь из стека  два числа и выполнить над ними операцию,
       считая при этом последнее извлеченное число первым операндом.
     - результат операции поместить в стек.
   После  завершения  программы в стеке останется одно число  -
результат вычислений.

     Пошаговое выполнение программы 2 5 1 3 2 / + * 7 / +
                   исполнителем Плюсик+


Выполнение программы     │ Стек
─────────────────────────┼────────────────────────────
  2 5 1 3 2 / + * 7 / +  │стек пуст, исполнитель - перед записью
^                        │
  2 5 1 3 2 / + * 7 / +  │2
  ^                      │
  2 5 1 3 2 / + * 7 / +  │2 5
    ^                    │
  2 5 1 3 2 / + * 7 / +  │2 5 1
      ^                  │
  2 5 1 3 2 / + * 7 / +  │2 5 1 3
        ^                │
  2 5 1 3 2 / + * 7 / +  │2 5 1 3 2
          ^              │
  2 5 1 3 2 / + * 7 / +  │2 5 1 3/2
           ^             │
  2 5 1 3 2 / + * 7 / +  │2 5 1+3/2
              ^          │
  2 5 1 3 2 / + * 7 / +  │2 5*(1+3/2)
                ^        │
  2 5 1 3 2 / + * 7 / +  │2 5*(1+3/2) 7
                  ^      │
  2 5 1 3 2 / + * 7 / +  │2 5*(1+3/2)/7
                    ^    │
  2 5 1 3 2 / + * 7 / +  │2+5*(1+3/2)/7
                      ^  │
  2 5 1 3 2 / + * 7 / +  │2+5*(1+3/2)/7
                       ^ │

   Итак,  если  выражение  записано "по-польски", вычислить  его
совсем не трудно. Даже Корректором.
   А вот как перевести обычную запись в польскую?

   В методичке по Плюсику написаны такие  рекомендации для пос-
троения программ (читай для перевода  обычной  записи  в  поль-
скую):

        Для преобразования обычного выражения в программу для Плюсика
     можно просматривать выражение последовательно слева направо, за-
     писывая команды
                           ЗАПОМНИ число
        Если после  очередной  записи команды ЗАПОМНИ выяснится, что
     над последними двумя числами в стеке  можно выполнить арифмети-
     ческую операцию, то записывается соответствующая команда.

   Очень хорошая  рекомендация! Но для человека. Как запрограм-
мировать:
   "Если после  очередной записи команды ЗАПОМНИ выяснится, что
над последними двумя числами в стеке  можно выполнить арифмети-
ческую операцию, то записывается соответствующая команда."

   Как проверить условие "можно выполнить арифметическую опера-
цию"?

   Непросто это! Особенно мешают круглые скобки. Тем более, что
вложение их друг в друга носит рекурсивный характер.

Посмотрите на выражение:

                    7 - (1 + 3)

Как перевести его в польскую запись?

   Сложность в том, что  исполнитель  не видит запись целиком! В
каждый момент ему виден только один символ (который  в нашей за-
даче одновременно является и лексемой).
   Следовательно, нужно  придумать, как перемещаясь от символа к
символу, сформировать обратную польскую запись выражения не видя
его целиком.

   Вы правы,  это  невозможно без хитрости! Нужно дополнительное
средство, которое расширит "кругозор" исполнителя за пределы од-
ного символа и позволит осуществить отложенные действия.
   Конечно, первый символ записи "7" можно сразу поместить в ре-
зультирующую строку. Следующий символ "-" - уже нельзя. Его нуж-
но где-то временно  запомнить. Чтобы потом в нужный момент вста-
вить в польскую запись.
   Когда  же  наступит подходящий момент для знака "-"?  Тогда,
когда за первым операндом  "7",  будет переведен в польскую за-
пись второй операнд  операции "-". В нашем случае таким операн-
дом будет польская запись выражения (1+3).

входная строка: 7-(1+3)   │
польский выход:           │
хранилище:                │
                          │
входная строка: -(1+3)    │  Число помещаем на выход
польский выход: 7         │
хранилище:                │
                          │
входная строка: (1+3)     │  Операцию помещаем в хранилище
польский выход: 7         │
хранилище: -              │
                          │

   Теперь на входе символ "(". Что с ним  делать? Придется тоже
его запомнить  и хранить до  тех пор, пока не встретится парный
знак ")". После этого знак "(" из хранилища можно убрать.

входная строка: 1+3)      │  Открывающуюся скобку помещаем в хранилище
польский выход: 7         │
хранилище:      - (       │

   Объект "1" помещаем в  выходную  польскую запись, а знак "+"
запоминаем до "лучших" времен:

входная строка: +3)       │  Число помещаем на выход
польский выход: 7 1       │
хранилище:      - (       │
                          │
входная строка: 3)        │  Операцию помещаем в хранилище
польский выход: 7         │
хранилище:      - ( +     │

   Продолжая действовать в том же духе, получим:

входная строка: )         │  Число помещаем на выход
польский выход: 7 1 3     │
хранилище:      - ( +     │
                          │
входная строка: )         │  Операцию из хранилища  помещаем на выход
польский выход: 7 1 3 +   │
хранилище:      - (       │
                          │
входная строка:           │  Закрывающуюся скобку удаляем из хранилища
польский выход: 7 1 3 +   │
хранилище:      -         │
                          │
входная строка:           │  Операцию из хранилища помещаем на выход
польский выход: 7 1 3 + - │
хранилище:                │

   Наши действия  над "хранилищем" наглядно показывают, что эта
память является стеком.
   Второй вывод, который можно сделать из наших опытов, позволит
написать формальный алгоритм преобразования обычного выражения в
польскую запись.  Вывод  такой:  символы перемещались из входной
строки в выходную или в стек, а из стека в выходную строку в за-
висимости от их приоритетов.
   Понятие приоритета можно формализовать, если ввести  числовые
характеристики, соответствующие нашим опытам:
 ┌──────────┬─────────┬─────────────────┐
 │ Объект   │приоритет│ приоритет во    │
 │          │в стеке  │ входной строке  │
 ├──────────┼─────────┼─────────────────┤
 │ +,-      │   2     │     1           │
 │ число    │   4     │     3           │
 │  (       │   0     │     5           │
 │  )       │         │     0           │
 └──────────┴─────────┴─────────────────┘
   Замечание 1. Скобку ")"  мы никогда не помещаем в стек.
   Замечание 2. Приоритет открывающей скобки в  стеке равен при-
оритету закрывающей скобки во входной строке, для того, чтобы по
формальному признаку равенства приоритетов, открывающуюся скобку
из стека можно было убрать тогда, когда парная к ней закрывающа-
яся появится во входной строке.

   Теперь алгоритм преобразования можно записать следующим  об-
разом:
┌─────────────────────────────────────────────────────────────────────┐
│Поместить символ "(" в стек, а символ ")" в конец входного выражения.│
└──────────────────────────────┬──────────────────────────────────────┘
                               │
┌──────────────────────────────┴──────────────────────────────────────┐
│Пока входное выражение не будет исчерпано повторять:                 │
├─────────────────────────────────────────────────────────────────────┤
│      Если на входе число, добавить его к выходу                     │
│      и перейти к следующему символу на входе                        │
│                                                                     │
│      Иначе, если вход > стека, поместить символ со входа в стек     │
│      и перейти к следующему символу на входе                        │
│                                                                     │
│      Иначе, если вход < стека, поместить символ со стека на выход   │
│                                                                     │
│      Иначе, если вход = стеку, удалить символ со стека              │
│      и перейти к следующему символу на входе                        │
│                                                                     │
└─────────────────────────────────────────────────────────────────────┘
   Инициализация перед  входом  в  цикл введена для единообразия
действий внутри цикла (когда не надо  обрабатывать отдельно пус-
той стек и пустую входную строку).

   Заметим также, что без первой  ветви  переключателя  в  цикле
вполне можно  обойтись (правда ценой лишних действий исполнителя
алгоритма): число в выходную строку может передаваться не сразу,
а единообразно через стек:

┌─────────────────────────────────────────────────────────────────────┐
│Поместить символ "(" в стек, а символ ")" в конец входного выражения.│
└────────────────────────────────┬────────────────────────────────────┘
                                 │
┌────────────────────────────────┴────────────────────────────────────┐
│Пока входное выражение не будет исчерпано повторять:                 │
├─────────────────────────────────────────────────────────────────────┤
│      Если вход > стека, поместить символ со входа в стек            │
│      и перейти к следующему символу на входе                        │
│                                                                     │
│      Иначе, если вход < стека, поместить символ со стека на выход   │
│                                                                     │
│      Иначе, если вход = стеку, удалить символ со стека              │
│      и перейти к следующему символу на входе                        │
│                                                                     │
└─────────────────────────────────────────────────────────────────────┘


Прокрутим по этому алгоритму еще раз выражение 7 - (1 + 3)


вход: 7-(1+3))       │ вход=3 > стек=0
выход:               │ Помещаем число в стек
стек: (              │
                     │
вход: -(1+3))        │ вход=1 < стек=4
выход:               │ Помещаем число на выход
стек: (7             │
                     │
вход: -(1+3))        │ вход=1 > стек=0
выход: 7             │ Помещаем операцию в стек
стек: (              │
                     │
вход: (1+3))         │ вход=5 > стек=2
выход: 7             │ Помещаем скобку в стек
стек: (-             │
                     │
вход: 1+3))          │ вход=3 > стек=0
выход: 7             │ Помещаем число в стек
стек: (-(            │
                     │
вход: +3))           │ вход=1 < стек=4
выход: 7             │ Помещаем число на выход
стек: (-( 1          │
                     │
вход: +3))           │ вход=1 > стек=0
выход: 7 1           │ Помещаем операцию в стек
стек: (-(            │
                     │
вход: 3))            │ вход=3 > стек=2
выход: 7 1           │ Помещаем число в стек
стек: (-(+           │
                     │
вход: ))             │ вход=0 < стек=4
выход: 7 1           │ Помещаем число на выход
стек: (-(+ 3         │
                     │
вход: ))             │ вход=0 < стек=2
выход: 7 1 3         │ Помещаем операцию на выход
стек: (-(+           │
                     │
вход: ))             │ вход=0 < стек=0
выход: 7 1 3 +       │ Удаляем скобку из стека
стек: (-(            │
                     │
вход: )              │ вход=0 < стек=2
выход: 7 1 3 +       │ Помещаем операцию на выход
стек: (-             │
                     │
вход: )              │ вход=0 < стек=0
выход: 7 1 3 + -     │ Помещаем операцию на выход
стек: (              │ Удаляем скобку из стека
                     │
вход:                │ вход=0 < стек=0
выход: 7 1 3 + -     │ Помещаем операцию на выход
стек:                │ Удаляем скобку из стека
                     │

   Замечание. Если бы кроме операций "+" и "-"  в записи присут-
ствовали бы более "старшие" операции "*" и "/", то алгоритм пре-
образования остался бы прежним, а вот  таблицу приоритетов приш-
лось бы изменить:
 ┌──────────┬─────────┬─────────────────┐
 │ Объект   │приоритет│ приоритет во    │
 │          │в стеке  │ входной строке  │
 ├──────────┼─────────┼─────────────────┤
 │ +,-      │   2     │     1           │
 │ *,/      │   4     │     3           │
 │ число    │   6     │     5           │
 │  (       │   0     │     7           │
 │  )       │         │     0           │
 └──────────┴─────────┴─────────────────┘


   Пожалеем газетное место и не будем  приводить программу этого
транслятора для  Корректора!  Код получается не слишком сложный,
но длинный.

   Основные идеи  рассмотрены и теперь легко написать транслятор
на Си или Паскале.  Пусть  Корректор займется любимым делом: ро-
ботландским чаем с сухариками!

Азы программирования в Роботландском Университете
-------------------------------------------------
   Наверное Вы решили, что "Азы программирования"  - это неболь-
шой курс по трансляторам. Это не так. Трансляторы  - это, конеч-
но, самая сложная тема курса и,  вероятно,  самая  интересная  с
точки зрения  практического введения в информатику. Другая люби-
мая тема Азов - построение необычных геометрий в средах Кукарачи
и Корректора. Ребятам  эта тема часто нравится даже больше тран-
сляторов.
   Вот пример  задачи (все геометрические определения даются от-
дельным текстом и здесь не приводятся в расчете  на интуицию чи-
тателя) из репертуара Кукарачи:

Задача (8 баллов)
   Исполнитель расположен где-то внутри горизонтального отрезка
ab. Сместить его  вниз из исходного положения на Pab. Известно,
что столбец точки a больше 2.
   Пример начальной установки среды:
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │ │a│ │ │¤│ │b│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

   Среда после выполнения программы:
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │ │a│ │ │ │ │b│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 6 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 7 │ │ │ │ │ │¤│ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼


   А вот два примера из "геометрии" Корректора:

   Задача 1. (3 балла)
   Окно установлено  в  центр окружности. Закрасить пробелом все
точки окружности  (кроме центра), если радиус окружности помещен
в клетку-центр в виде  символа  из алфавита Корректора. При этом
числовое значение радиуса равно порядковому номеру символа в ал-
фавите  исполнителя.

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

Начальное состояние                 После работы программы
┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░│░│░║2║░│░│░│░│░│    ─────>     │░│░│ │ ║2║ │ │░│░│░│
┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘

   Задача 2. (8 баллов)
   На ленте Корректора заданы две окружности с центрами в разных
точках a  и b.  Известно, что a < b  и радиусы обеих окружностей
меньше 50.
   В клетках, изображающих центры окружностей, записаны символы,
задающие радиусы окружностей (как в условии задачи 7).
   Написать программу,  которая  закрасит  пробелами все клетки
пересечения окружностей (кроме точек a и b, даже если они попа-
дают в пересечение).
  В начальный момент окошко установлено в точке a.

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

Начальное состояние                 После работы программы
┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│░│░│░║4║░│1│░│░│░│░│    ─────>     │░│░│░│4│ │1│ │░│░│░│
┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

   Вы  уже поняли  для  кого наши Азы?  Они  для ребят,  которые
по-настоящему увлечены программированием и для учителей, которые
склонны поддерживать и развивать этот интерес.
   Написать на Бейсике несколько строчек для вывода на экран ка-
кой-нибудь бредятины -  не  слишком большое достижение для прог-
раммирования.
   Изучить язык  Си - это тоже  не достижение. Вы  же понимаете,
чем мясорубка отличается от кулинарии! И старые, добрые Кукарача
и Корректор наглядно это демонстрируют.

   Если у Вас  есть группа ребят, которым подобные вещи интерес-
ны, то Роботландский Университет может быть полезен.
   Нам можно  написать по адресу:  kurs@robotland.users.botik.ru
и заглянуть на сайт http://www.botik.ru/~robot
   У нас есть для Вас! (Кое-что в подарок!)

                             Александр Александрович Дуванов
                             руководитель Роботландского Университета,
                             куратор курса "Азы программирования"
