A stack that checks nested brackets
Build a bracket checker that reports the first mismatched character, keeps opening positions on a stack, and states where a real parser needs more context.
A bracket checker needs to remember which opening bracket must close next. A stack supplies that order: the most recent unmatched opener is the first one that a closer must match. If you already know lists and loops, writing a checker that returns an error position makes the stack’s job concrete and produces something more useful than a bare True or False.
Define the accepted input first. This example recognizes (), [], and {}. It ignores other characters, treats every bracket character as syntax, and returns the zero-based position of the first invalid closer. If the text ends with unmatched openers, it returns the position of the most recent unmatched opener. A valid input returns None.
That final rule is a diagnostic choice. An editor could instead point to the earliest unclosed opener, or to the end of the input. Choose one rule so that tests and error messages describe the same behavior.
Store positions with the brackets
The stack contains pairs of opening character and source position. Matching only bracket types is enough to validate an input, but keeping positions lets the caller underline the bracket that needs attention.
def bracket_error(text):
expected_open = {')': '(', ']': '[', '}': '{'}
stack = []
for position, character in enumerate(text):
if character in '([{':
stack.append((character, position))
elif character in expected_open:
if not stack:
return position
if stack[-1][0] != expected_open[character]:
return position
stack.pop()
return stack[-1][1] if stack else None
assert bracket_error('a{b[c](d)}') is None
assert bracket_error('([)]') == 2
assert bracket_error(']') == 0
assert bracket_error('([') == 1For ([)], the stack first receives ( at position zero and [ at position one. The closer ) arrives at position two, but the top opener is [. The input is already invalid at this point. Searching deeper in the stack for a matching ( would incorrectly allow crossing pairs, which are not nested brackets.
For ([]), the ] removes [, exposing ( for the next closer. The last-in, first-out behavior matches the nesting. Python’s tutorial shows the same append and end pop operations in its section on using lists as stacks.
The trace stops at the first mismatch. Any later positions are irrelevant to this function’s answer. A tool that tries to recover and report several errors would need additional rules to avoid one bad bracket producing a cascade of misleading diagnostics.
The invariant follows the consumed prefix
After reading a valid prefix of the input, the stack contains exactly its unmatched opening brackets in their original order. The final stack entry is the opener for the innermost unfinished pair. Initially the prefix and stack are both empty, so the statement holds.
Reading an ordinary character changes neither the unfinished pairs nor the stack. Reading an opener adds a new innermost unfinished pair, so pushing it preserves the statement. Reading a closer is valid only if it matches the top. Popping that pair restores the previous nesting context.
If the stack is empty when a closer arrives, the consumed prefix has no opener available. If the top has a different type, closing it with the current character would violate nesting. Both cases justify returning immediately. At end of input, an empty stack means every opener found its correctly ordered closer. A nonempty stack identifies unfinished pairs.
Counting opening and closing characters is insufficient. The strings ([]) and ([)] have the same number of each character, but only the first is properly nested. Even separate counters for each bracket type lose the order that distinguishes them. The stack stores precisely that missing information.
Depth determines memory
Each character is inspected once. Each opener is pushed once and popped at most once, so runtime is O(n) for a string of length n, assuming constant-cost character classification and amortized constant-time list append. The algorithm can return earlier on a mismatch, but its worst case still examines every character.
Auxiliary space is O(d), where d is the greatest nesting depth reached by a valid prefix. A million balanced pairs written one after another need a stack depth of one. A million consecutive opening parentheses need a million entries before the function reaches the end. A service accepting untrusted input may choose a maximum permitted depth and report it as a separate limit.
The positions produced by Python string iteration count Unicode code points. They are not byte offsets into UTF-8 and are not always user-perceived character columns. If an editor’s highlighting API expects a different unit, convert positions at that boundary. An ASCII example hides this distinction because all three units coincide there.
Keep the stack when text arrives in chunks
A file reader or network protocol may deliver ([ in one chunk and ]) in the next. Running the one-shot checker on each chunk would report an unfinished opener too early. A chunk boundary is not the end of the logical input. Preserve the stack and the absolute position between calls, then check unfinished openers only when the caller declares that input is complete.
class BracketStream:
def __init__(self):
self.stack = []
self.offset = 0
self.error = None
self.finished = False
def feed(self, chunk):
if self.finished:
raise ValueError('stream is finished')
if self.error is not None:
return self.error
expected_open = {')': '(', ']': '[', '}': '{'}
for local, character in enumerate(chunk):
position = self.offset + local
if character in '([{':
self.stack.append((character, position))
elif character in expected_open:
if not self.stack or self.stack[-1][0] != expected_open[character]:
self.error = position
break
self.stack.pop()
self.offset += len(chunk)
return self.error
def finish(self):
self.finished = True
if self.error is None and self.stack:
self.error = self.stack[-1][1]
return self.error
stream = BracketStream()
assert stream.feed('([') is None
assert stream.feed('])') is None
assert stream.finish() is None
unfinished = BracketStream()
assert unfinished.feed('([') is None
assert unfinished.finish() == 1
broken = BracketStream()
assert broken.feed('ab(') is None
assert broken.feed('[)') == 4
assert broken.feed('more text') == 4
assert broken.finish() == 4
A None result from feed means no invalid closer has been seen so far. Only finish can certify that no opener remains. Once a mismatch occurs, its position is sticky: later chunks cannot repair the prefix or replace the first error. Calling feed after finalization raises an error instead of silently starting another document. A caller processing another document should construct another stream.
The absolute offset counts the characters supplied before the current chunk. In the broken example, the second chunk begins at position three; its ) is local position one, hence global position four. The implementation may leave the rest of a failed chunk unexamined because it never resumes parsing after that first mismatch. Empty chunks preserve the state and do not mean end of input.
This interface accepts decoded Python strings. A byte stream can split a multibyte UTF-8 character between chunks, so decoding each byte chunk independently is another possible bug. The Python Unicode HOWTO distinguishes encoded bytes from Unicode text; an incremental decoder belongs before this checker when the transport supplies bytes. Changing chunk sizes must not change the logical character positions or bracket result.
As an exercise, split the same input at every possible position and compare finish with the one-shot checker. Include a mismatch exactly at a chunk boundary, an empty final chunk, and an unfinished nested prefix. These cases test the lifecycle and retained state, not just the matching table.
Brackets inside strings need lexical context
This checker regards the parenthesis inside print(")") as a closer, even though a programming-language parser would treat it as part of a string literal. The example’s contract deliberately excludes string and comment awareness. Real source-code tooling must first recognize tokens, including escapes and the language’s string forms.
Python’s lexical-analysis reference describes those rules for Python source. Copying a few quotation checks into the stack loop is not enough to handle every language. A configuration format may also permit braces inside quoted values, while a mathematical expression language may not have strings at all.
Test the contract with empty text, each closer alone, balanced mixed nesting, crossing pairs, and an unfinished nested prefix. Also include ordinary characters around brackets to confirm they are ignored. When a later feature adds strings, create new tests for brackets inside strings and escaped quotes before changing the meaning of existing inputs.