Valid Parentheses with a Stack
Counting openers and closers is enough for one bracket type and completely wrong for three. The moment you have to remember which kind of bracket you are inside, and in what order, you need a structure that gives back the most recent thing first — which is the clearest practical argument for a stack that exists.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
bool isValid(string s) {
vector<char> st;
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') {
st.push_back(c);
} else {
if (st.empty()) return false;
char top = st.back();
st.pop_back();
if (c == ')' && top != '(') return false;
if (c == ']' && top != '[') return false;
if (c == '}' && top != '{') return false;
}
}
return st.empty();
}
int main() {
cout << isValid("{[()]}") << endl;
cout << isValid("([)]") << endl;
return 0;
}Uses a vector as the stack so every push and pop is visible as a plain array operation; prints 1 then 0.
How it works, step by step
An opener is a promise
Pushing a bracket records an obligation to close it later. The stack holds every promise that is still outstanding, in the order they were made, with the most recent on top.
A closer must match the most recent promise
Brackets nest, so the only bracket you are allowed to close is the innermost open one — the top of the stack. That single rule is what rejects ([)], where the closer does not match the most recent opener even though the counts are balanced.
An empty stack on a closer is an immediate failure
A closing bracket with nothing outstanding means the string closes something that was never opened, as in ())(. Checking st.empty() before reading back() is both a correctness rule and a safety check against undefined behaviour.
A non-empty stack at the end is also a failure
Leftover entries mean promises that were never kept, as in ((. Returning st.empty() rather than plain true is what catches this, and it is the check most people forget.
Why a counter is not sufficient
A counter tracks how many brackets are open but not which ones. It accepts ([)] because the total rises and falls correctly. Only for a single bracket type do a counter and a stack agree — and even then the counter must be checked for going negative.
Complexity
Each character is pushed and popped at most once; the worst case for memory is a string of all openers such as ((((((, which stores every character before discovering the failure at the end.
Common bugs
Returning true instead of st.empty()
The loop only detects mismatches and unexpected closers. A string like ({[ passes every in-loop check and leaves three unmatched openers behind. Ending with return true accepts it. This is the single most common bug in this problem.
Reading back() without checking empty()
Calling back() or pop_back() on an empty vector is undefined behaviour, not an exception. On input )( it often returns garbage that happens not to match, so the function accidentally returns the right answer — until the day it does not.
Using a counter for multiple bracket types
A single integer incremented on openers and decremented on closers accepts ([)] and [{]}. It cannot distinguish types by construction. If your solution passes the simple tests and fails the interleaved ones, this is why.
Assuming the input contains only brackets
If the string can hold other characters, the else branch treats every letter as a closing bracket and immediately fails. Either filter non-bracket characters explicitly or restructure the branch to test for known closers rather than using else as a catch-all.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why does valid parentheses need a stack?
Because brackets nest, and the only bracket a closer may match is the most recently opened one that is still unclosed. A stack returns exactly that element in O(1). A counter only tracks how many brackets are open, not which types or in what order, so it wrongly accepts strings like ([)].
What is the time complexity of the valid parentheses algorithm?
O(n) time and O(n) space. Every character is examined once and pushed or popped at most once. The space is worst-case n, reached by a string consisting entirely of opening brackets, all of which must be remembered until the end.
Why check that the stack is empty at the end?
Because leftover openers are unmatched. The loop can only detect a closer that mismatches or that arrives with nothing open — it has no way to notice that ((( never closed. Returning st.empty() rather than true is what makes those cases fail correctly.
Can you solve valid parentheses without a stack?
Only for a single bracket type, where one counter that never goes negative and ends at zero is equivalent. With multiple types you need to remember the sequence of open brackets, and any structure that does that is a stack, whether you call it one or implement it with an array and an index.