Valid Parentheses Check

Use a stack. Push every opening bracket you see. When you meet a closing bracket, the stack must be non-empty and its top must be the matching opening bracket; if either fails the string is invalid. At the end the stack must be empty, because an unclosed opening bracket is also a failure.

def is_valid(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack


print(is_valid("()[]{}"))
print(is_valid("([)]"))
print(is_valid(""))

The outputs are True, False and True. The second string has the right brackets in the wrong order: the closing parenthesis meets an open square bracket on top of the stack, so it fails immediately even though the counts balance.

The mechanism is that a stack enforces nesting. The most recent opening bracket is the only one that a closing bracket is allowed to close, which is exactly the nesting rule. Matching counts are not enough, and the example in the second print is the standard way to show that difference.

The trade-off to name is that you reject early, which is what you want in a real parser, but it means the function cannot tell you where the mismatch happened. If you want to report the offending position, you keep the index of each bracket on the stack rather than the bracket itself. The other detail is the empty string, which is valid by convention, and the code above returns True for it because the final check is that the stack is empty.

An empty string is valid, because there is nothing to mismatch. A string of only opening brackets is invalid, because the stack ends the scan holding unclosed brackets.

def is_valid(text):
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)
        else:
            if not stack:
                return False
            expected = {")": "(", "]": "[", "}": "{"}[char]
            if stack.pop() != expected:
                return False
    return not stack


print(is_valid(""))
print(is_valid("((("))
print(is_valid("()"))

The outputs are True, False and True. The empty string passes because the stack is empty at the end, the three opening brackets fail because the stack holds three unmatched entries, and the balanced pair passes.

The mechanism is that the final return is the emptiness of the stack rather than any particular value. Every closing bracket that was seen either popped a matching opening bracket or caused an early return, so if you reach the end, the only possible failure is a leftover opening bracket.

The trade-off to name is the convention question. Some specifications treat an empty string as invalid because it is not a valid expression, and some parsers require at least one token. That is a decision the problem statement makes rather than the algorithm, and the right move in an interview is to say which convention you are using and where it appears in the code. The empty stack check also covers the case of a string containing only closing brackets, where the early return fires on the first character because the stack is empty.

Ignore everything that is not a bracket. The check only cares about opening and closing brackets, so any other character is skipped rather than pushed or popped.

def is_valid(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
        elif char in "([{":
            stack.append(char)
    return not stack


samples = ["a(b)c[d]{e}", "(a[b)", "((a)"]
print([is_valid(s) for s in samples])

The output is the list True, False, False. The first string has three well formed bracket pairs with letters in between. The second closes a parenthesis while a square bracket is open, which fails. The third leaves one parenthesis open, which the final check catches.

The mechanism is that the two membership tests partition the alphabet into three groups: closing brackets, opening brackets and everything else. Only the first two change the stack, so the other characters are invisible to the algorithm. The order of the two branches matters for clarity but not for correctness, since a character cannot be in both sets.

The trade-off to name is that ignoring unknown characters is the right default for a validator but not for a full parser. If the input has escaped brackets inside a string literal, or if the language has other bracket-like pairs such as angle brackets, a real parser needs a context stack rather than a flat one. The other point worth making is that this function answers only one question, whether the nesting is consistent, and a real implementation would also report the position of the first mismatch so the user gets a useful error message instead of a bare false.