Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 76 стр.

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                    .
правильное скобочное выражение “(A+B)*(A-B)+B” некорректно заключено в
[] (нет закрывающей скобки). Во втором выражении внутри [] содержится не-
правильное скобочное выражение “(A+B” (нет закрывающей круглой скобки).
     Для решения задачи применяется следующий алгоритм синтаксического
анализа, основанный на использовании стека. Выражение анализируется по-
символьно слева направо, пока не будет обнаружен признак его конца или не
нарушится пункт 2 определения. В анализируемом выражении рассматрива-
ются только скобки. При нахождении открывающей скобки заносится в стек
информация о ее типе. При обнаружении закрывающей скобки любого типа
анализируется содержание стека. Если стек пуст, то считается, что скобки в
выражении расставлены неправильно. Если стек не пуст, то из него извле-
кается последняя открывающая скобка и проверяется соответствие ее типа
типу обнаруженной закрывающей скобки. Если в рассматриваемой паре ско-
бок открывающая и закрывающая скобки имеют различный тип, выражение
считается некорректным, в противном случае, продолжается поиск следую-
щей скобки во входном выражении. При достижении признака конца строки
вновь анализируется состояние стека. Пустой стек соответствует правильной
расстановке скобок. Наличие скобок в стеке соответствует ошибке расстанов-
ки скобок.
     Синтаксический анализ расстановки скобок иллюстрируется на примере
следующего алгебраического выражения:




    Под строкой алгебраического выражения указаны номера состояний
стека при разборке скобок. Состояния стека приведены на следующей диа-
грамме состояний (рис. 4.1).




                           Рис. 4.1. Диаграммы состояний стека.


                                            76