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

6.2.5. Задача 5 (10 баллов)
Средний бал решений: 6.0 (60%)

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

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

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

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

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

Решение

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

<выражение> ::= <число> |                            (1)
                <число>+<выражение> |                (2)
                <число>-<выражение> |                (3)       (*)
                (<выражение>)                        (4)
<число>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9  (5)

   До сих пор рекурсивность определений (по  Бэкусу) была прос-
той и достаточно очевидной.
  В самом деле, из записи

  <число> ::= <цифра> | <цифра> <число>
  <цифра> ::= 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).
   Поработать с  рекурсивными  определениями  очень полезно. Эта
область информатики находится на границе математики и лингвисти-
ки.
   Запись 5+3 - это выражение, а 5+F - нет. Это понятно. Но тог-
да (чуть сложнее) 5+3-7 - тоже выражение. Ведь 5+3 - выражение и
7 - выражение тоже. Понятно, что любая цепочка цифр, между кото-
рыми стоят знаки "+" и "-" - является выражением. Это  легко до-
казать по индукции.
  Рассмотрим объект
     Vn = <цифра><знак><цифра><знак> ....<цифра>    (**)
  (число n говорит, что в записи (**) n знаков "+" или "-").
   Объект
     V1 = <цифра><знак><цифра> - выражением  является  (база ин-
дукции).
   Пусть известно, что Vn - является  выражением. Докажем тогда,
что Vn+1 является выражением тоже (индукционный переход).
  Доказательство.
    Очевидно, что
Vn+1 = Vn<знак><цифра>                              (***)
   Но так как  Vn  - выражение (по индукционному предположению),
то объект (***) является выражением по определению (*).
   Впрочем, то, что Vn  -  является выражением, почти очевидно и
без всякого доказательства.
   Можно рассуждать так.
   V1  - это  выражение  по (*). Но  если  к выражению  добавить
<знак><цифра>,  то  опять из (*) получим выражение V2.  Следова-
тельно, если мы будем продолжать в том же духе (прибавляя  к вы-
ражению <знак><цифра>), то  всегда  будем получать выражения для
любого n. То есть всегда Vn - будет выражением.

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

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


 Типичные ошибки в решениях.

   1) Программы работают по многопроходным алгоритмам.

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

   б) В записях типа ")(", "()", "1(+2)", "1()" в качестве оши-
бочного символа  указывается  первая клетка ПУСТО после записи.
Это не верно. Верный ответ показан в следующей строке:
")(", "()", "1(+2)", "1()"
 ^      ^     ^        ^
   в) Неверно указано место ошибки в записи: (1+1
                                                ^
