Stack: resolve the newest first
Learn LIFO and use it to check all three kinds of bracket nesting.
The newest unfinished item is on top
std::stack follows LIFO: last in, first out. push adds to the top; top reads that item; pop removes it without returning a value. Check nonemptiness before top or pop. There is no indexing, ordinary iteration, front, or back.
With the default deque backing and fixed-cost elements, these operations take O(1). Pushing 4, 9, 2 exposes 2, regardless of numerical order. A vector can also act like a stack with push_back, back, and pop_back when direct access to the resulting sequence is useful.
Matching totals are not enough
For ([{}]), the most recent unmatched opening bracket must close first. A stack remembers these openings. Push an opening; for a closing bracket, require a nonempty stack and a matching top, then pop.
The sequence ([)] has matching totals but invalid nesting. The sequence (() leaves an opening at the end. The sequence )( closes before anything is open. Correctness requires valid prefixes, matching types, and final emptiness.
A short-circuit guard protects top()
Check pending.empty() || !matches(pending.top(), c). If empty is true, the right side is not evaluated, so top is never called on an empty stack. These examples promise input contains only the six bracket characters.
Each character causes at most one push or pop, giving O(n + 1) time. A prefix of only openings can store n characters, so the helper’s worst-case auxiliary space is O(n + 1). The explicitly created std::stack is different from the implementation’s call stack used by recursion.
Container workbench
Insert values, then remove the next accessible item. Priority queue values are shown sorted for explanation, not as an internal heap.
Next removal: 5. Size: 3.
Guided simulation · Change the inputs to test your understanding.
Why does counting equal numbers of opening and closing brackets fail for ([)]?
Turn the idea into code
Read one line containing only (), [], and {}. Print YES if it is balanced, otherwise NO. The empty line is balanced. Test ([]), ([)], ((), and )(.
Give me a hint
Store unmatched openings. Every closing bracket must match the top, and the stack must be empty at the end.
Show the explained solution
After each accepted prefix, the stack is precisely its unmatched openings in order. Rejecting an empty or mismatched top detects invalid prefixes; final emptiness ensures every opening was closed.
// Complete C++23 program. Input: one bracket-only line, length <= 200000.
#include <iostream>
#include <stack>
#include <string>
bool matches(char open, char close) {
return (open == '(' && close == ')') ||
(open == '[' && close == ']') ||
(open == '{' && close == '}');
}
bool balanced(const std::string& text) {
std::stack<char> pending;
for (char c : text) {
if (c == '(' || c == '[' || c == '{') pending.push(c);
else {
if (pending.empty() || !matches(pending.top(), c)) return false;
pending.pop();
}
}
return pending.empty();
}
int main() {
std::string text;
std::getline(std::cin, text);
std::cout << (balanced(text) ? "YES\n" : "NO\n");
}Your notes
Mark complete when you can explain it yourself.