Automatic brace insertion algorithm

Question

For more information, see this issue on GitHub.

I want to write an algorithm that's called when the user hits the Enter key after an opening brace. The expected behavior is detailed below.

1. Suppose we have an empty document. If we type an opening brace and hit Enter, the expected behavior is the following:

This can be described as the following simple algorithm:

1. If Enter is pressed after an opening brace, move the cursor to the next line and indent one more level beyond the opening brace's indentation.

2. If the opening brace was not paired, insert a closing brace on the next line at the same indentation level as the opening brace. Else, if it was already paired, do nothing after 1.

In other words, what we don't want is for another closing brace to be inserted if we hit Enter after the opening brace that's already paired. Instead, we simply want to keep the indentation consistent:

2. Now suppose we type another opening brace on Line 2, where the cursor is, and hit Enter. We expect a new pair to be generated, following the same algorithm described above:

3. And if we go to Line 1, hit Enter a couple times to force the braces down, and then try to create a new block up top, we want this to be paired as well:

The Problem

I'm having trouble implementing this behavior. I'm developing the text editor in C++ using Qt, but you don't have to worry about the framework specifics. It's just going to be a utility function that takes a given string named context and the index of the opening brace in question, and decides whether a closing brace should be inserted or not.

My current implementation satisfies scenarios #1 and #2, but not #3. The reason it does not satisfy #3 is because I'm using a queue for the opening braces.

I've also tried using a stack for the opening braces. Interestingly, this ends up satisfying #1 and #3, but not #2.

Question

How can I write an algorithm to determine whether a given brace already has a matching pair, in accordance with the expected behavior described above? Note that I've researched this on the site and do know how to determine whether a given opening brace has a matching closing brace. However, my current algorithm (linked above) does not work as intended (see description above for where it fails).

Clarification: you do NOT have to worry about the whole "indentation" thing. That's taken care of and works as intended. What doesn't work as intended is deciding whether a particular brace needs a matching pair.

Answer 1

This is not a complex problem to determine if there is a closing brace, it's the indentation that will be the difficult one. If there is any unmatched closing brace following the ope brace you have a match. The key in that is whether the brace is following your open brace. You could determine this by:

1. Store the location of all unmatched closing braces; if one follows your cursor you don't need to insert a closing brace
2. Dynamically evaluate the number of unmatched braces before your cursor (not counting unmatched closes) compared to the number of unmatched braces after your cursor; if you have a surplus of closing braces after your cursor then you don't need to insert a closing brace

If you're going with number 2, I've expanded this answer to your needs for counting braces before and after:

bool foo(const string& context, const size_t pos) {
    const auto it = next(cbegin(context), pos);
    const auto before = accumulate(cbegin(context), it, 0, [](const auto output, const auto input) {
        if(input == '{') {
            return output + 1;
        }
        else if(input == '}' && output > 0) {
            return output - 1;
        }
        else {
            return output;
        }
    });
    const auto after = accumulate(it, cend(context), 0, [](const auto output, const auto input) {
        if(input == '{') {
            return output + 1;
        }
        else if(input == '}') {
            return output - 1;
        }
        else {
            return output;
        }
    });

    return before + after >= 0;
}

This can be called, with the text in question (not including the inserted open brace), and the position in the string the brace is going to be inserted. Given your text is contained in const string bar and your cursor position is at const size_t baz you could call this function like: foo(bar, baz) If this returns true you need to add a closing brace.

Live Example