Стек в C++ через std::stack — как проверить правильность скобок?
Дали учебную задачу: проверить, правильно ли расставлены скобки в строке, например (()()) — верно, (() — нет. Понимаю, что нужен стек, и в C++ есть std::stack, но не разобрался с методами.
Как положить элемент, как посмотреть верхний и как удалить? И почему у стека, как и у очереди, pop() похоже ничего не возвращает?
2 ответа
Да, у std::stack ровно та же логика, что у queue: pop() удаляет верхний элемент и ничего не возвращает, а смотреть нужно через top(). Стек работает по принципу LIFO (последний зашёл — первый вышел).
Вот решение твоей задачи про скобки:
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isBalanced(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(') {
st.push(c); // открыли скобку — кладём
} else if (c == ')') {
if (st.empty()) return false; // закрывающая без пары
st.pop(); // нашли пару — снимаем
}
}
return st.empty(); // если стек пуст — все скобки закрылись
}
int main() {
cout << isBalanced("(()())") << "\n"; // 1
cout << isBalanced("(()") << "\n"; // 0
return 0;
}
Методы std::stack:
st.push(x)— положить наверхst.top()— посмотреть верхнийst.pop()— удалить верхнийst.empty()— пустой лиst.size()— размер
Идея алгоритма: каждую ( кладём в стек, на каждую ) снимаем одну. Если в какой-то момент снимать нечего или в конце стек не пуст — баланс нарушен.
Частая ошибка — вызвать top() или pop() у пустого стека. Это UB (неопределённое поведение), может крашнуть, а может выдать мусор. Всегда проверяй if (!st.empty()) перед top()/pop(), как в принятом ответе с if (st.empty()) return false;.
