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

Формулировка задания:
Требуется разработать программу 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 отображает следующий рисунок.

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

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

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

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

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

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

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

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

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

Примитив 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 содержит желаемую в программе последовательность обработки состояния переполнения стека, например, аварийное завершение, расширение буфера стека или переход к резервным буферам.






Стековый алгоритм анализа расстановки скобок.

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


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


нарушают 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 г.

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

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

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

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