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

6.2.6. Задача 6 (15 баллов)
Средний бал решений: 5.8 (39%)

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

<число>   ::=  1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

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

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

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

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


Решение

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

   Решение задачи  представим в виде 4 последовательных незави-
симых друг от друга шагов:

   1. Проверка соответствия записи определению.
   2. Преобразование выражения в обратную польскую запись.
   3. Вычисление польской записи на стеке.
   4. Запись результата на ленту в виде обычного десятичного числа.

   Соответственно главная процедура программы будет иметь вид:

ЭТО выражение               │
 проверка                   │Процедура "проверка" запишет в ящик Корректора
 ОБМЕН                      │символ "#" как признак того, что ошибок в записи
 ЕСЛИ # ТО                  │нет.
 {                          │
   ОБМЕН                    │Продолжаем работу только в том случае,
   преобразование           │если ошибок в записи не было.
   вычисление               │
   результат                │
 }                          │
 ИНАЧЕ ОБМЕН                │
КОНЕЦ                       │
                            │



 1. Проверка соответствия записи определению.

   К счастью,  программа проверки написана для предыдущей зада-
чи.
   Возьмем ее целиком, изменив лишь имя главной процедуры и про-
цедуру "ответ". Теперь в процедуре "ответ" не нужно на ленту пи-
сать "ок".  Вместо этого в  ящик помещается символ "#" - признак
успешной проверки и установить окошко в исходное положение перед
записью.


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



   2. Преобразование выражения в обратную польскую запись.

   Помнится кто-то из руководителей команд сомневался в нужнос-
ти Плюсика (первая тема наших курсов) для постижения азов прог-
раммирования.
   Пристегните ремни!  Сейчас знания этого исполнителя Вам при-
годятся в полной мере.

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

Сравните:
-  обычная запись выражения:  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
                       ^ │

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

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

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

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

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

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

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

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

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

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

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

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

                    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           │
 └──────────┴─────────┴─────────────────┘
   Замечание. Скобку ")"  мы никогда не помещаем в стек. Приори-
тет открывающей  скобки  в  стеке  равен  приоритету закрывающей
скобки во входной  строке,  чтобы по формальному признаку равен-
ства приоритетов, открывающуюся  скобку  из стека можно было уб-
рать тогда, когда парная к ней закрывающаяся появится во входной
строке.

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

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

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


Прокрутим по этому алгоритму еще раз выражение 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           │
 └──────────┴─────────┴─────────────────┘

   Теперь, наконец, мы готовы к реализации алгоритма преобразо-
вания  обычного  выражения в польскую обратную запись на  ленте
Корректора.
   Стек  и  выходную строку, в которой будет формироваться  ре-
зультат преобразования,  разместим на ленте Корректора в следу-
ющем виде:
                 вход #стек  #выход

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

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

   3. Вычисление польской записи на стеке.

   Сейчас на ленте сложилась следующая обстановка:

           исходная запись  #    #обратная польская запись
                          ^
                          окошко здесь

   Окошко смотрит на первый пустой символ  за исходной записью,
стек пуст,  а на выходе (сразу  за вторым знаком  "#") обратная
польская запись исходного выражения.
   Для вычисления польской записи будем использовать стек (сей-
час он  пуст).  Для  арифметических вычислений применим команды
исполнителя ПЛЮС и МИНУС. Конечно, в итоге мы получим не десяти-
чное число, а некоторый символ из алфавита Корректора (по усло-
вию результат не превышает длины  алфавита,  то  есть  символов
Корректора нам хватит для  изображения  ответа. Преобразованием
ответа-символа в обычное десятичное число займется  специальная
процедура "результат".

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


4. Запись результата на ленту в виде обычного десятичного числа.

   Ситуация на ленте сейчас такая:

           исходная запись  #n    #обратная польская запись
                            ^
                            окошко здесь

   В стеке записан символ (на рисунке он обозначен как "n").
   Этот символ  -  результат  вычислений  нужно преобразовать в
обычное десятичное число.

   Алгоритм этого преобразования очень прост:

   занести символ-результат в ящик
   записать на ленту число 0
   пока в ящике не 0  выполнять:
     число на ленте увеличить на 1 (процедурой "плюс1")
     символ в ящике заменить на предыдущий по алфавиту

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

                       * * *

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

Авторское описание алгоритма очень "куцее":
   1. Проверим на правильность запись на ленте.
   2. Если это выражение, то найдем его значение.

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