"Valid Parentheses" is a parsing problem

In light of some events that happened recently, I realised that valid parentheses (and some other problems) are actually parsing problems.

The valid parentheses problem gives you a string of (), [], or {}. You have to return whether every opening brace is closed by a brace of the same type, in the right order. There are three bracket types, but they all work the same way, so for the rest of this post I’ll assume there’s only ().

The “standard” solution

If you do even a little bit of leetcode, you should know how to solve it. The first option would be to use a stack. Push every opening parenthesis onto the stack, and when you see a closing parenthesis, you pop from the stack (this should be an opening parenthesis). Ensure that the popped opening parenthesis matches the closing parenthesis. At the end of the loop, the stack must be empty.

The stack solution is effectively a shift-reduce parser. Pushing an opening brace is a shift, and popping it when its closing brace comes is a reduce. It parses with the following grammar.

where $\epsilon$ is the empty string.

The other direction

Recursive descent is the dual of shift-reduce parsing. It builds the parse top-down instead of bottom-up. Recursive descent can’t handle left recursion, so we flip the grammar to put the recursion on the right. Once you have the grammar, the code writes itself.

const char *parse_expr(const char *s) {
    if (!is_opening(*s)) {
        return s;
    }

    const char *rest = parse_expr(s + 1);
    if (!is_matching_paren(*s, *rest)) return s;
    return parse_expr(rest + 1);
}

bool is_valid(const char *s) { return *parse_expr(s) == '\0'; }

is_opening returns true for an opening bracket, and is_matching_paren returns true if the two characters form a pair.

An alternative

The trailing $e$ is a tail call, so it becomes a loop. The inner $e$ can’t, because the ) is still pending after it returns. Every tail call is a loop, but not every recursion is a tail call.

const char *parse_expr(const char *s) {
    while (is_opening(*s)) {
        const char *rest = parse_expr(s + 1);
        if (!is_matching_paren(*s, *rest)) break;
        s = rest + 1;
    }
    return s;
}

In grammar form, that’s

Which solution is the best?

On its own, I don’t think any have real advantages over each other. The important part is how you can view the problem as a parsing problem, and use all the tools that parsing theory has given us.

That said, if I had to pick, I’d choose the more general approach. The approach using the stack is LR parsing, and it’s strictly more expressive than LL parsing (the recursive approaches).