Просто о сложном. Стек.

Стек — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. (Википедия). Все компьютеры работают со стеком, память организована в виде стека, поэтому просто нельзя не знать, что это такое. Сегодня мы поговорим о его реализации и применении.
Реализация

Первое, что приходит в голову С++ программисту это написать класс, с перегрузкой операторов, динамическим выделением памяти, обработкой исключений и тому подобных фишек данного языка. Но этим мы займемся как-нибудь в другой раз. А что если весь код программы, в которой он может потребоваться, будет занимать меньше чем код класса? Сегодня мы поговорим именно о таких задачах, и о простой реализации этой структуры данных.
Но никак нельзя обойтись без двух составляющих реализации:

1. Две простые функции для работы с данными: снять данные с вершины, и положить их на вершину.
2. Что-то, где будут храниться данные, и указателя на вершину.

Начнем мы именно со второго пункта. Мы даже не будем выделять память динамически, а используем статический массив, с фиксированной, но быстро изменяемой длинной. Да все будет предельно просто.
Функции

PUSH

Функция для погрузки данных на вершину стека. Я сразу приведу код, а потом мы его обсудим.

int Push(char Ch)
{
	if (Top>=MaxS)
		return 0;
	Stack[Top++]=Ch;
	return 1;
} 

Предположим для начала, что стек содержит символы. В качестве параметра мы передадим функции символ, который нужно положить на вершину. Далее могут возникнуть вопросы, что за непонятные переменные тут используются?

Top – указатель на вершину стека. В нашем случае это индекс первой свободной ячейки в массиве.

MaxS – максимальный размер стека.

Stack – собственно сам стек, массив с элементами типа char.

Теперь поговорим о работе функции. Сначала смотрим, есть ли на стеке свободное место. Хоть какой-то контроль быть должен. Если места нет Top>=MaxS, тогда возвращаем 0, что сигнализирует об ошибке. Если оно есть то, кладем символ на вершину и увеличиваем указатель на вершину, именно в таком порядке, так как стоит постфиксный инкремент. И возвращаем 1, что сигнализирует успешность выполнения операции.

POP

Функция для снятия данных с вершины.

int Pop(char *pCh)
{
	if (Top<=0)
		return 0;
	*pCh=Stack[--Top];
	return 1;
}

В общем, все предельно просто. Если снимать уже нечего Top<=0, возвращаем 0. Если же снятие имеет смысл, то сначала уменьшаем указатель на вершину, как вы помните он указывал на первое свободное место, а затем записываем последний символ по адресу, который записан с pCh. Ну и возвращаем 1, что сигнализирует о том, что все прошло удачно. Собственно говоря, вот и весь стек, не такой уж он и сложный, как кажется на первый взгляд. Теперь поговорим о том, зачем это нужно.

Задача

Не надолго представим, что мы пишем калькулятор, в котором нужен анализатор формул и математических выражений. Например, пользователю понадобилось вычислить значение выражения (2+3)*5. Посмотрев на него, любой человек может сказать, что оно построено правильно. А потом наш пользователь случайно ошибся и ввел что-то типа, 8-6)*4. Естественно это неверно потому, что не хватает скобки в начале. Но как компьютер может отличить верное выражение от неверного? Для начала проверим расстановку скобок. Если бы у нас были только круглые () скобки, то все просто. Но у нас будут не только круглые, но еще квадратные [] и фигурные {}. Если честно, то фигурными я не разу не пользовался, а вот квадратные применяю часто. При трех видах скобок решить, что правильно, а что нет довольно сложно. Именно для этого мы и применим наш стек. Как же мы будем это делать?

Если встретилась одно из открывающих скобок (, [ или {, то положим ее на вершину стека. Если же встретилась закрывающая то есть ), ] или }, то узнаем, что лежит на вершине стека. Если там ничего нет, то это явно ошибка. Если там симметричная открывающая скобка для встреченной закрывающей, то все хорошо и идем дальше. Когда мы дошли до конца, нужно посмотреть, не осталось ли на стеке не закрытых открывающих скобок. Вот и весь алгоритм, простой и действенный. Теперь код.

#include <stdio.h>
#include <conio.h>
#define MaxS 255  //размер стека
#define OK 1      //коды ошибок
#define NotOK 0
 
char Stack[MaxS]; //сам стек
int Top;          //указатель на вершину
int Push(char Ch)
{
	if (Top>=MaxS)
		return NotOK;
	Stack[Top++]=Ch;
	return OK;
}
int Pop(char *pCh)
{
	if (Top<=0)
		return NotOK;
	*pCh=Stack[--Top];
	return OK;
}
void main()         //главная функция
{
	char c,       //переменная для снятия с вершины 
           ch[255]; //строка для анализа
	int i=0, x;
	Top=0;
	printf("Vvedite virajenie\n");
	scanf("%s", ch);
	while (ch[i]!='\0')
	{
		if (ch[i]=='('||ch[i]=='['||ch[i]=='{')
			Push(ch[i]); //если скобка открывающая то кладем ее на стек
		else
		{
		if (ch[i]==’)’||ch[i]==’]’||ch[i]==’{’)
		{  //если закрывающая скобка то снимаем со стека открывающую
			x=Pop(&c);
			if (x==NotOK) //если на стеке ничего не было
			{
			    printf("NO");
			    getch();
			    return;
			}
			if ((ch[i]==')'&&c=='(')||(ch[i]==']'&&c=='[')||(ch[i]=='}'&&c=='{'))
				;
			else
			{  //если на стеке была скобка но она не соответствует
   //введенной
				printf("NO");
				getch();
				return;
			}
		}
		}
		i++; //переходим к следующему символу
	}
	if (Top==0) //если мы дошли до конца и на стеке ничего не осталось то 
//ошибок нет
		printf("YES");
	else
		printf("NO");
	getch();
	return;
}

Если что-то не понятно, то читай комментарии в коде или напиши мне на почту

Written by: Крылов Егор
E-mail: