Цель занятия.  Целью занятия является практическое изучение программной реализации стека с исользованием контейнерных классов системы программирования С++ на примере алгоритма синтаксического анализа расстановки скобок в алгеброическом выражении.

       Формулировка задания.  Тенбуется разроботать программу brackets для синтаксического анализа произвольного алгеброическог выражения с целью проверки правильности расстановки в нем круглых, квадратных и фигурных скобок.
  Исходными данными програм мы brackets является строка символов, содержащее скобочное алгеброическое выражение. Строка алгеброического выражения должны передоваться программе brackets из потока стандартног ввода (stdin).
  Результатом работы программы brackets является оценка соответствия открывающих и закрывающих скобок во входном алгеброическом выражении. Результат оценки должен визуализироваться соответствующим по смыслу, но произвольном по форме информационном сррбщением, которое должно отображаться символьной строкой в потоке стандартного вывода (stdout).
  Для синтаксического анализа расстановки скобок требуется применить стековый алгоритм анализа скобок, использующий стек с фиксированным буфером. Программа brackets должна быть составлена в системе программирования С++ с использованием контейнерных классов.

 Стек (stack) это абстрактная структура данных для хранения набора элементов, обработка которого допустима только с одного конца, называемого вершиной стека. Положение вершины в стеке отображает указатель стека sp (stack pointer). Через вершину в стеке можно добавить (протолкнуть) новый элемент или извлечь (вытолкнуть) последний добавленный элемент, изменяя при этом соответствующим образом указатель стека. Извлекать элементы из стека и добавлять элементы в стек можно не однократно, пока стек не пуст и не переполнен, соответственно. Реализуемая стеком дисциплина обслуживания набора данных называется LIFO (LastIn, FirstOut - последним пишел, первым обслужен).
  Для хранения данных в стеке выделяется специальный вуфет sbuf (stack buffer). В простейшем случае буфер стека реализуется одномерным массивом, длина которого априори устанавливает предельный размер стека ssize (stack size), задаваемый при создании стека. Такая организация стека называется стеком с фиксированным буфером (FixStack). Указатель стека в нем интерпретируется как целочисленный индекс массива, представляющего буфер стека. Логическую структуру стека с фиксированным буфером, в котором содержатся 3 элемента: A, B, C отображает следующий рисунок.

    Рис. Логическая структура стека с фиксированным буфером.

  Для работы состеком используются 3 примитивные процедуры: PUSH, POP и STATE, которые обеспечивают извлечение данных из стека, загрузку данных в стек и оценку состояния стека, соответственно.
  Примитив PUSH загружает (проталкивает) новый элимент в вершину стека и увеличивает на 1 значение указателя стека. Псевдокод процедуры PUSH выражают следующие операнды:

    Sbuf[sp] <- V;
    sp <- sp+1;
    RETURN;

где V обозначает элимент данных, добовляемый в стек. Работу приметива PUSH отображает следующая диаграмма загрузки данных в стек.

    Рис. Диаграмма загрузки в стек.

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

       sp <- sp-1;
       RETURN (Sbuf[sp]);

  Работу пимитива POP иллюстрирует следующая диаграмма извлечения (выталкивания) данных из стека.

       Рис. Диаграмма выталкивания данных из стека.

  Для стека с фииксированным быуфером обмена процедура извлечения данных необязательно является деструктивной операцией, т.е. вытолкнутые элименты не уничтожаются в буфере стека, по-крайней мере до загрузки новых данных. Очевидно, что процедура протолкивания данных в стек имеет деструктивный эффект, модификаиця содержания буфера стека. Рассмотренные примитивы PUSH и POP обеспечивают желаемую обработку стека с фиксиксированным буфером, когда он не переполнен (sp < ssize) и не пуст (sp=0), соответственно.
 Для оценки текущего состония стека используется примитив STATE. Он обеспечивает оценку состояния стека повозвращаемому значению его указателя. Целесообразной представляется следующая кодировка возврата примитива STATE. Если при оценке в в буфере стека нет свободного места для размещения новых данных, т.е. буфер заполнен полностью, возвращается отрицательный код. В противном случае, когда в буфере стека есть свободное пространство для размещения новых элиментов, при оценке стека примитивом STATE возвращается текщее щзначение указателя стека. Очевидно, когда стек пуст примитив STATE будет возвращать нуливое значение.
Псевдоход примитива STATE выражают следующие операнды:

       IF sp<ssize THEN RETURN(sp);
          ELSE RETURN(-sp);

  На следующем рисунке представленны 3 диаграммы состояний для пустого, допустимо заполненног и переполненного стека, которые иллюстрируют принятую кодировку возврата примитива STATE.

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

  Примитив STATE следует использовать в сочетании с примитивами PUSH и POP, чтобы избежать потери значимости при переполнении стека и попытке извлечь данные из пустого стека. Следующий псевдокод блокирует потерю значимости в случае пустого стека (underflow) при использовании примитива POP для извлечения данных в переменную W:

      IF STATE() > 0 THEN
             W <- POP();
      ELSE
             UNDERFLOW();

где процедура UNDERFLOW реализует желаемую в программе последовательность обработки состояния пустого стека при попытке извлечь данные. Исключение потери значимости в случае переполнения стека (overflow) при попытке протолкнуть в стек новый элемент V, используя примитив PUSH, демонстрирует следующий псевдокод:

      IF STATE() < 0 THEN
             OVERFLOW();
      PUSH(V);

где процедура OVERFLOW содержит желаемую в программе последовательность обработки состояния переполнения стека, например, аварийное завершение, расширение буфера стека или переход к резервным буферам.

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

   {A+B*[(A+B)*(A-B)+2*A*B]}/2

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

   [(A+B)*(A-B)+B; [(A+B]) и {A-(B]}

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

  Для программирования стека целесообразно применить принцип инкапсуляции оъбектно-ориентированного программирования, сосредоточив описание стековых структур и примитивов их обработки в отдельном классе FixStack. Организация класса FixStack должна быть ориентированна на возможность постраения на его основе производных и контейнерных классов, обладающих спецификой стековой обработки данных в различных приложениях. Чтобы распространить облость применения класса FixStack на обработку различных простых типов данных без изменения его структуры целесообразно определить с помощью дерективы typedef универсальный тип для элементов стека StackType. Учитывая символьный характер обработки скобок в алгебраическом выражении, в данном случае следует определить тип элементов стека как char, используя следующую конструкцию определения типа системы программирования С++:

  typedef char StackType;

которая определяет новый тип StackType, эквивалентный типу char перед декларацией класса FixStack.
  Класс FixStack должен содержать частные (private) компаненты-данные и общедоступные (public) компонентные методы их обработки. Это обеспечивает доступ к данным класса FixStack из внешних приложений только с помощью компонентных методов и исключит возможность не посредственного обращения к частным компонентным данным класса. Таким образом, декларация логической структуры класса FixStack должна иметь следующий формат:

   class FixStack {
     private: /* спецификация компонентных данных */
     public:  /* спецификация компонентных методов */
   };

  В частнную (private) часть декларации класса FixStack целесообразно включить спецификацию следующих компонентных данных:

   StackType* sbuf; /* адрес буфера стека */
   int sp;          /* указатель стека */
   int ssize;       /* размер стека */

  Для доступа к приватным данным в классе FixStack рекомендуется предусмотреть компонентные методы, реализующие примитивы стековой обработки. Их декларация должна должна иметь следующий формат в теле класса FixStack:

   void push(StackType); /* добавление элимента типа StackType в стек */
   StackType pop();      /* извлечение элемента типа StackType из стека */
   int state();          /* оценка состояния стека */

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

    FixStack(int); /* конструктор класса */

  Конструктор класса FixStack должен обнулять указатель стека, фиксировать размер стека по значению своего аргумента и динамически выделять память из кучи для буфера стека, используя операцию new системы программирования С++.
  Для корректного удаления объектов класса FixStack в нем рекомендуется предусмотреть деструктор ~FixStack(). Он должен освобождать память, распределенную конструктором для буфера стека, используя операцию delete системы программирования C++.
  Учитывая простоту исходного кода компоненты методов класса FixStack, их спецификация может быть преведена непосредственно в теле класса. В этом случае они по умолчанию будут рассматривотся компилятором С++ как подставляемые (inline) функции. В объектном коде компилятор С++ заменяет каждую ссылку на inline-функцию ее кодом, увеличивае быстродействие программы.

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

      class FixStack { /* спецификация класса подобъекта */};
      class BracketSyntax{/* спецификация контейнерного класса */}
         public:
            FixStack stack; /* спецификация подобъекта */
         ...............
       };

  Категория доступа public разрешает обращатся к общедоступным компонентным методам подобъекта класса FixStack (push, pop, state) в компонентных методах контейнерного класса BracketSyntax и во внешних функциях (например, main()) программы, где определенн объект контейнерног класса. В обоих случаях, для их вызова нужно указывать префикс подобъекта. Например, если bex есть объект класса BracketSyntax в функчии main(), то вызов компонентног метода pop() из класса подобъекта FixStack должен иметь следующий формат: bex.stack.pop(), а в любом компонентном методе контейнерного класса тот же вызов будет иметь более короткий формат: stack.pop(). Следует отметить, что категория доступа private к подобъекту в контейнерном классе сохраняет возможность обращения к общедоступным компонентам класса подобъекта только в компонентных методах контейнерного класса.
    При любой категории доступа непосредственное обращение к частным компонентам подобъекта запрещено. Для их обработки должны использоватся общедоступные компонентным методам класса подобъекта. Таким образом, для обработки частных стековых данных (sp, ssize, sbuf) класса FixStack в объемлющем классе BracketSyntax следует применять общедоступные компонентные методы класса подобъекта (push, pop, state).
  Кроме подобъекта stack класса FixStack в декларацию контейнерного класса BracketSyntax следует включить спецификацию частных (private) компонентных данных простых типов и общедоступных (public) компонентных методов, читывающих специфику стековой обработки скобочных алгебраических выражений, а также конструктор и деструктор. Таким образом, декларация контейнерного класса BracketSyntax должна иметь следующий формат:

     class BracketSyntax {
        public: FixStack stack; /* спецификация подобъекта */
        private:                /* спецификация приватных данных */
        public:                 /* спецификация компонентных методов,
                                  конструктора и деструктора */
     };

  В спецификацию приватных данных достаточно включить объявление единственной целочисленной переменной valid, значение которой должно отображать результат разбора очередной скобки входного алгебраического выражения и итоговый результат синтаксического анализа алгебраического выражения в целом. Рекомендуется принять следующую договоренность по значению компоненты valid: нуливое значение соответствует ошибке расстановки скобок, значение больше 0, когда скобки расставлены верно.
  Вобщедоступную часть объявления класса BracketSyntax целесообразно включить декларацию следующих компонентных методов: char pair(char); int diag(char); int diag(void), а также спечификацию конструктора с целочисленным аргументом:

  BracketSyntax(int) и деструктор класса: ~BracketSyntax().

  Конструктор класса BracketSyntax должен инициализировать приватную компоненту valid ненуливым значением и вызывать конструктор касса подобъекта FixStack для инициализации стека. Конструктор класса FixStack имеет целочисленный аргумент, определяющий размер стека. Поэтому конструктор контейнерного класса BracketSyntax также должен иметь целочисленный аргумент, чтобы иметь возможность передавать его значение конструктору класса FixStack для создания стека желаемого размера. Указанные инициализирующие действия следует реализовать через список инициализаций, перечислев их после имени и двоеточия в строке определения конструктора контейнерного класса BracketSyntax(int). Поскольку все указанные действия выполняются в списки инициализации, то тело конструктора может быть пустым {}. Учитывая рассмотренные особенности построения конструктора класса BracketSyntax, его определение целесообразно включить непосредственно в декларацию класса, например, следующим образом:

    class BracketSyntax {
      ...................
      public:
        BracketSyntax(int s):   stack(s), valid(s) {};
      ...................
   };

 Чтобы всегда иметь возможность корректно завершить объекта класса BracketSyntax в нем рекомендуется предусмотреть деструктор ~BracketSyntax(). Вданном случае деструктор следует специфицировать, чтобы обеспечить неявный вызов деструктора класса подобъекта FixStack, для корректной выходной обработки его компанентных данных, в частности, с челью освободить память, динамически выделенную под буфер стека при создании подобъекта внутри контейнерного класса. Какая-либо выходная обработка собственных компонентов в классе BracketSyntax не является необходимой, поэтому тело деструктора ~BracketSyntax() можно оставить пустым {}, а его определение - включить в деструкцию класса, например, следующим образом:

   class BracketSyntax {
     ...................
     public:
       ~BracketSyntax() {};
     ...................
   };

  В отличие от конструктора, при определении деструктора контейнерного класса не следует указывать вызов деструктора подобъвекта. Он осуществляется автоматически, т.к. уничтожение контейнерного объекта означает ликвидацию всех его компонент, в том числе подобъекта, инициирую вызов его деструктора, как если бы подобъект уничтожился бы индивидуально, являясь самостоятельным объектом.
 Определение конструктора и деструктора вдекларции класса BrasketSyntax принуждает компиятор языка С++ рассматьривать их как подставляемые (inline) функции по умолчанию, обеспечивая автоматическую подстановку их объектного кода по адресам их вызовов в объектном коде программы. Рассмотренные ниже компанентные методы класса BracketSyntax в соответсткии со своей функциональной нагрузкой предполагают более представительный исходный, и следовательно, объектный код. Поэтому их целесообразно определить вне декларации класса, не превращая в inline - подстановки. Например, дефиниция компонентного метода pair должна иметь следующий вид:

  char BracketSyntax::pair(char c){/* тело метода */}

Компонентный метод pair(char) специализируется с целью выполнения преобразования переданной в качестве аргумента открывающей скобки в возвращаемое значение кода соответствующей по типу закрывающей скобки. Это преобразование облегчает проверку соответствия скобок из стека и входного алгебраического выражения в стековом алгоритме анализа расстановки скобок.
  Компонентный метод diag(char) должен обеспечивать синтаксический анализ текущего символа входного алгебраического выражения, код которого передается как аргумент, устанавливая и возвращая значение приватной компоненты valid, соответствующее текущему результату разбора. В теле этого метода рекомендуется использовать оператор switch системы программирования С++ с 3-мя группами альтернатив, которые соответствуют обработки любых открывающих скобок, любых закрывающих скобок и выходных символов неявляющихся скобками. Для стековой обработки скобок следует применять компонеднтные методы класса подобъекта FixStack. Для сравнения типа открывающих и завкрывающих скобок рекомендуется применять собственный компонентный метод pair. Третья альтернатива (default) дожна содержать пустой оператор (;), не влияя на значение приватной компоненты valid.
  Компонентный метод diag(void) перегружает рассмотренный выше компонентный метод diag(char) для заключительной оценки результата анализа расстановки скобок, когда достигнут конец рассматриваемого алгебраического ввыражения. В соответствии со стековым алгоритмом этот метод должен присваивать нуливое значение приватной компоненты valid, если стек открываюдщих скобовк не пуст. В противном случае приватная компонента valid должна сохранять текущее значение, установленное перегруженным методом diag(char). Для оценки состояния стека следует использовать компонентный метод state подобъекта класса FixStack. Аналогично своему перегруженному варианту, компонентный метод diag(void) должен возвращать значвение приватной компоненты valid как итоговый рездультат синтаксического анализа выходного алгебраического выражения.
 Вызов перегруженных методов diag класса BracketSyntax для реализации стекового алгоритма анализа скобок удобно осуществить в основной функции main() проектируемой программы brackets. Перед их вызовом в основной функции main() необходимо создать объект класса BracketSyntax, осуществив обращение к конструктору класса, например, следующим образом:

  main() {
     BracketSyntax bex(32);
     ................
  }

  После этого созданный объект класса BracketSyntax (bex) можно использовать для обращения к компонентному методу BracketSyntax::diag(char) в цикле чтения входной строки алгебраического выражения из потока стандартного ввода (stdin), пока не обнаружена ошибка расстановки скобок (нуливой возврат метода diag) или пока не достигнут конец анализируемой входной строки (символ с кодом '\n'). Для чтения потока стандартного ввода можно использовать библиотечную функцию getchar() системы программирования С++.
  После завершения (или прерывания) цикла обработки скобок входного алгебраического выражения необходимо выполнить итоговую проверку стекового алгоритма анализа расстановки скобок, вызвав командный метод diag() через тот же объект (bex) класса BracketSyntax (bex.diag()). Его код возврата легко интерпретировать для выбора соответствующего информационного сообщения о результатах анализа расстановки скобок. Для отображения информационного сообщения в потоке стандартного вывода можно использовать библиотечную функцию puts(char*) системы программирования С++. В качестве аргумента ей необходимо передать адрес строки выбранного информационного сообщения.

  1. Модифицировать программу brackets, чтобы реализовать синтаксический анализ расстановки скобок в текстовом файле, содержащем его исходный код.
  2. Модифицировать программу barckets, чтобы обеспечить циклическую проверку  расстановки скобок для произвольного числа строк потока стандартного ввода, каждая из которых содержит отдельное алгебраическое выражение.
  3. Разработать расширенный класс XFixStack, который позволял бы сравнивать содержание 2-х стеков, инвертировать буфер стека, копировать и перемещать данные между 2-мя стеками, создовать новый стек эквивалентный заданному, оценивать предельный размер буфера стека.
  4. Разработать программу поиска текстовых палиндромов с использованием стека символов, где под текстовым палиндромом понимается последовательность символов, которая одинаково читается слево-направо и справо-налево.
  5. Составить программу контроя формата символьных наборов, в которых считается, что набор символов S имеет допустимый формат, если он образован контейнерезацией 2-х цепочек латинских букв X и Y, которые разделяет заданный сепаратор @:
                 S=X@Y,
     причем, Y является символьным палиндромом X. Для контроля формата необходимо использовать стек с фиксированным буфером.
  6. Разработать класс ReStack, в котором для уменьшения вероятности переполнения предусмотрен резервный буфер. Вслучае переполнения основного буфера информация из него должна перекачиваться в резервный буфер, освобождая основной для приема данных. Информация из резервного буфера возвращается в основной, когда основной становится пуст после соответствующего числа запросов извлечения данных. Память для резервного буфера должна динамически выделятся из кучи, когда он становится не обходим и освобождаться когда необходимость в резервировании данных исчерпана.
  7. Усложнить стековый алгоритм анализа расстановки скобок в алгеброическом выражении с учетом следующих ограничений, установленных приоритетом скобок: круглые скобки не могут окружать квадратные и фигурные, а внутри любой пары квадратных скобок не может быть фигурных.
  8. Интеллектуаризировать программу braskets так, чтобы она сообщала место и причину ошибки расстановки скобок.

  1. Й. Лэнгсам, М. Оченстайн, А. Тененбаум
     Структуры данных для персональных ЭВМ, - М., Мир, 1989 г.
  2. А. Т. Берзтисс
     Структуры данных - М., Статистика, 1974 г.
  3. Р. Вайнер, Л. Пинсон
     С++ изнутри - Киев, НПИФ "ДиаСофт", 1993 г.
 
 

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

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

  Рис. Диаграммы состояний стека
  Из приведенной диаграммы стека следует, что положительный результат
сопоставления типов скобок в состояниях 4, 5, 8, 9 и пустой стек в финальном
состоянии 10 означает правильность расстановки скобок в заданном алгебраическом
выражении.