The challenge
Return whether all brackets are correctly paired and nested.
Input contains only ()[]{}. The empty string is valid.
Example
([{}]) → true; ([)] → false.
Use the walkthrough below to inspect the input and each state change.
See Valid Parentheses, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 8
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: ["(","[","{","}","]",")"]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Push openings; a closer must match the top.
Indices are zero-based. C++ uses C++17 or later.
def solve(values):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for c in values:
if c in '([{':
stack.append(c)
elif not stack or stack.pop() != pairs[c]:
return False
return not stack
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
bool solve(const vector<string>& values) {
vector<string> stack;
for (const auto& c : values) {
if (c == "(" || c == "[" || c == "{") stack.push_back(c);
else {
string opening = c == ")" ? "(" : c == "]" ? "[" : "{";
if (stack.empty() || stack.back() != opening) return false;
stack.pop_back();
}
}
return stack.empty();
}