It’s a classic problem: given a string of parentheses, determine if they’re properly nested. The complication here is that, instead of just 1 kind of parens, we have 3 to deal with. This same problem can be found on codewars.

This is often presented as an exercise where the “solution” is to realize that a stack works perfectly for this scenario. What else can we learn from this?

Opportunities for Learning

1. Helper functions! The flip here is pretty useful and helps makes the different cases we want to deal with clearer.
2. Dealing with cases! This is an interesting question because we have a lot of branches inside the loop. Usually that’s not so.
3. An extension of that is thinking about loop invariants. What are all the different cases we can expect in our loop, and what do we want to maintain? For instance, it’s important not to push on close-parens (we’re not just pushing on every character we see, the invariants we want to maintain aren’t quite that).
4. I like the “tail” condition. We’re not just done at the end of the loop, we have to make sure we’ve matched all our open parens.

Something I’m not so excited about with this question is that, as I’ve seen, it invites a lot of complicated experiments. People seem inclined to try very “stateful” approaches (build up a complicated analysis of the string, start doing some kind of weird tree-ish thing). It seems a lot of the neat-ness of this question is from realizing that you may tempted to have a very sophisticated amount of state, but you “just” need a stack. It’s very gratifying to make those realizations, and can be very valuable for professional software development… but is answering this a useful signal?

class Solution:
    def flip(self, c):
        if c == '}': return '{'
        if c == ')': return '('
        if c == ']': return '['
        assert(False)
        
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c in {'(', '[', '{'}:
                stack.append(c)
                continue
            elif len(stack) == 0:
                return False
            elif self.flip(c) == stack[-1]:
                stack.pop()
            else:
                return False
        return len(stack) == 0

It’s a bit difficult to categorize this problem. On the one hand the input is a string, but the intended solution uses a stack. As I think the string-edness is more arbitrary, I would categorize this as a stack-based question, even though that speaks more to the solution than the nature of the problem. Here is where any other stack questions will end up.