Программа 51. Реализация стека в виде массива
Рассмотрим стек, элементами которого являются символы. Программа состоит из трех файлов: Stack.h, Stack.cpp и Brackets.cpp. Файл Stack.h содержит объявления функций для работы со стеком.
// Файл Stack.h
#ifndef STACKH // Страж
#define STACKH // включения
void push(int c); // Поместить c в стек
int pop(); // Извлечь элемент из вершины стека
#endif
Реализация функций для работы со стеком находится в файле Stack.cpp.
// Файл Stack.cpp
#include <iostream.h>
#include ”stack.h”
static const int SZ = 100; // Максимальный размер стека
static char s[SZ]; // Массив под элементы стека
static int sp = 0; // Позиция свободного элемента массива
// push: поместить c в стек
void push(int c)
{
if(sp < SZ) // Если в массиве есть место,
s[sp++] = c; // помещаем символ в стек
else
cerr << "Стек полон," << char(c) << "не помещается \n";
}
// pop: извлечь элемент из вершины стека
int pop()
{
if(sp > 0) // Если в стеке есть символы,
return s[--sp]; // берем символ с вершины стека
else{
cerr << "Стек пуст\n";
return EOF;
}
}
В функции main организовано посимвольное чтение текста и его анализ на правильность расстановки скобок. Все открывающие скобки, встреченные в тексте, помещаются в стек. Если встречается закрывающая скобка, то из вершины стека извлекается последняя встреченная открывающая скобка и сравнивается с закрывающей. Если скобки соответствуют друг другу, продолжается анализ, если не соответствуют, то это ошибка. Ошибкой являются также случаи, когда закрывающая скобка идет раньше открывающей и когда открывающих скобок больше чем закрывающих.
// Файл Brackets.cpp
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include "stack.h"
int main()
{
int c, bro;
while((c = cin.get()) != EOF) // Чтение символов
if('(' == c || '[' == c || '{' == c) // Открывающие скобки
push(c); // помещаем в стек
else if(')' == c || ']' == c || '}' == c){ // Встретилась закрывающая
bro = pop(); // Берем из стека открывающую
if(bro == EOF || (bro == '(' && c != ')') // Проверка
|| (bro == '[' && c != ']') // соответствия
|| (bro == '{' && c != '}')){ // скобок
cerr << "Для " << char(c) << " нет открывающей\n";
exit(1);
}
}
// Чтение текста закончено
if(pop() != EOF) // Если стек не пуст
cerr << "Открывающих больше чем закрывающих \n";
else
cout << "Скобки расставлены верно \n";
return 0;
}
Поскольку данная программа состоит из двух файлов, следует создать проект, в который включить файлы Stack.cpp и Brackets.cpp. Далее приведены результаты двух запусков программы.
Первый запуск:
)(^Z
Стек пуст
Для ) нет открывающей
Второй запуск:
{[()]}^Z
Стек пуст
Скобки расставлены верно
Пространства имен
В настоящее время в C++ добавлен еще один инструмент управления именами – пространства имен, которые создаются с использованием ключевого слова namespace. Назначение пространства имен состоит в том, чтобы снизить вероятность конфликта имен при разработке больших программ. Старые компиляторы, в частности TC, не поддерживают пространства имен, но современные компиляторы, например, C++Builder их поддерживают.
Продемонстрируем использование пространства имен на примере программы 51 о стеке.
Оформим файл Stack.h в виде:
// Файл Stack.h
#ifndef STACKH // Страж
#define STACKH // включения
namespaceStack{ // Создаем пространство имен Stack
void push(int c); // Поместить c в стек
int pop(); // Извлечь элемент из вершины стека
} // Конец объявления пространства имен
#endif
Теперь имена функций push и pop принадлежат пространству имен Stack и к ним надо обращаться в виде Stack::push и Stack::pop. Если после изменения файла Stack.h выполнить компиляцию файла Brackets.cpp, то будут выданы ошибки:
Call to undefined function push (Вызов неопределенной функции push)
Call to undefined function pop (Вызов неопределенной функции pop)
При компиляции файла Stack.cpp ошибок не будет, но функции push и pop, определенные в этом файле, ничего общего не имеют с функциями Stack::push и Stack::pop, так как не входят в пространство имен Stack. Перепишем файл Stack.cpp в виде:
// Файл Stack.cpp
#include <iostream.h>
#include "Stack.h"
static const int SZ = 100; // Максимальный размер стека
static char s[SZ]; // Массив под элементы стека
static int sp = 0; // Позиция свободного элемента массива
// push: поместить c в стек
void Stack::push(int c) // Используем полное имя Stack::push
{…}
// pop: извлечь элемент из вершины стека
int Stack::pop() // Используем полное имя Stack::pop
{…}
Перепишем теперь файл Brackets.cpp в виде:
// Файл Brackets.cpp
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include "stack.h"
using namespace Stack; // Делаем доступными имена из пространства
// имен Stack
int main()
{
…
}
Теперь программа будет работать так же, как до введения пространства имен.
Директива using:
using namespaceStack;
делает доступными все имена из пространства имен Stack.
Можно было бы сделать доступными только отдельные имена из пространства имен с помощью объявлений using:
usingStack::push;
using Stack::pop;
поместив их вместо директивы using.
Можно, не используя директиву using и объявления using, просто везде писать полные имена с квалификаторами: Stack::push и Stack::pop, но это, обычно, утомительно.