Есть вот такая задача. Вообще не понимаю как ее реализовать при помощи стека. Даже начать не знаю с чего. I need help!
Написать программу, принимающую арифметическое выражение в виде строки, и
определяющую корректность расстановки скобок в этом выражении. Учесть круглые «()»,
квадратные«[]», фигурные «{}» и угловые «<>» скобки.
Скобки считаются сбалансированными, если:
a) количество открывающихся скобок совпадает с количеством закрывающихся;
b) закрывающаяся скобка не идет раньше соответствующей ей открывающейся;
c) соблюдается принцип вложенности скобок.
Хочу попробовать оттолкнуться от этого кода.
#pragma once
template <class T>
class Stack
{
T* arr = nullptr;
int capacity = 0;
int top = -1;
public:
Stack();
Stack(int c);
Stack(const Stack& obj);
Stack(Stack&& obj)noexcept;
~Stack();
Stack<T>& operator=(const Stack& obj);
Stack<T>& operator=(Stack&& obj)noexcept;
void push(T val);
T pop();
T peek()const;
bool is_empty()const;
bool is_full()const;
};
Направьте меня в правильное русло пожалуйста!)
Кажется я понял, сейчас попробую сделать. Спасибо
Это называется “баланс скобок”, полно материалов по этой фразе )
http://mech.math.msu.su/~shvetz/54/inf/perl-problems/chBalance_sIdeas.xhtml
Будем каждую встретившуюся открывающую скобку добавлять в конец некоторого списка (изначально пустого). Если же встретится закрывающая, мы попытаемся удалить из конца этого списка последнюю добавленную туда открывающую скобку. Мы пишем «попытаемся», так как список может оказаться пустым. Это означало бы, что к только что найденной закрывающей скобке не нашлось соответствующей открывающей, и сбалансированности уже не будет. Обработку можно на этом прекратить с формулировкой «непарная закрывающая скобка». Если же список был не пуст, проверяем, образуют ли пару найденная закрывающая и удалённая из конца списка открывающая скобки. Если да, то продолжаем обработку. Если нет, прекращаем процесс всё с той же формулировкой «непарная закрывающая скобка». Если в конце работы список открывающих скобок будет непуст, сообщаем о непарной открывающей скобке.
Таким образом, со списком открывающих скобок совершаются только два вида операций: что-то добавляется в его конец, и что-то удаляется с конца. Всё это должно напомнить нам о процедурах push и pop, которые именно так и поступают с массивом.
Такие списочные структуры, в которые можно добавлять элементы в конец, и удалять их тоже с конца, очень важны в информатике. Они называются стеками (stack — стопка каких-либо предметов, сложенных один на другой, например, тарелок). Обычно из стопки берут самую верхнюю тарелку, ту, которую положили туда последней. По аналогии со стопкой тарелок начало списка называют основанием стека, а его конец — вершиной.
В С++ уже есть стандартный класс для стеков, std::stack.