Check if vector of strings has matching brackets

Question

For an online screen, I had a question that would take in a vector of strings, and return a vector of strings indicating whether the input string was a valid combination of []{}(), where valid means the braces are matching and not interleaved. There are no empty string inputs.

For example, [(())] is valid, but ), {, and {[}] are invalid.

Note that input is only brackets, output is YES or NO, depending on whether or not the input is only matching brackets.

Also note using namespace std is required by the online software (hackerrank).

/*
 * Increments each value in vec by the delta.  
 */
void increment(vector<int> &vec, int delta){
    transform(vec.begin(), vec.end(), vec.begin(), [delta](int x){return x+delta;});
}

/* 
 * Checks if a bracket has been closed, and if it has, checks that it
 * was expected to be closed.  Returns true if there is an invalid close.
 * Note that vectors are in sorted order, since we only add indices when
 * a new bracket is opened.
 */
bool check(vector<int> &vec, bool expected){
    if(vec.empty()){ //if there are no open brackets, check if we expected one
        if (expected){
            return true;
        }
    }
    else if(vec.back() == 0){ //if the there is a bracket that was closed, check if we expected that
        vec.pop_back();
        if (!expected){
            return true;
        }
    }
    return false;
}

/*
 * Complete the function below.
 */
vector<string> braces(vector<string> values) {
    vector<pair<char, char>> bracket_types;
    bracket_types.push_back(pair<char, char>('{','}'));
    bracket_types.push_back(pair<char, char>('(',')'));
    bracket_types.push_back(pair<char, char>('[',']'));
    vector<string> results;
    for(auto const &str: values){
        /* Map of vectors containing integers indicating the number of opening brackets
         * seen since each bracket was first seen, minus the number of closing.  
         * When an index is zero, that means that bracket should be closed, so we
         * check it using the check method.
         */
        map<char, vector<int> > counts; 

        for(auto const &c : str){ //iterate over the string of brackets
            int incr;  
            for(auto const &type : bracket_types){  //find which bracket we are using
                if (type.first == c){  //if it's an opening bracket, add a new open bracket to the vector
                    incr = 1;
                    counts[c].push_back(0);
                    break;
                }
                if (type.second == c){  //if it's a closing bracket, set incr to decrement each value
                    incr = -1;
                    break;
                }
            }
            for(auto &cnt : counts){  //for all vectors, update values, and check if we have an invalid close.
                increment(cnt.second, incr);
                if (incr < 0 && check(cnt.second, cnt.first==c)){  //if we closed a bracket, could be invalid, check
                    cnt.second.push_back(0);  //add a bracket to a vector, so that we will have the right return
                    break;
                }
            }
        }
        //Return false if there are unclosed brackets.
        results.push_back("YES");
        for(auto const &cnt : counts){
            if (!cnt.second.empty()){
                results.back() = "NO";
            }
        }
    }
    return results;
}

Answer 1

Comments

You have overwhelming amount of comments. It looks to be too much. Usually code should document itself by having good names and intuitive behavior. Intuitive behavior would be one of standard library, for example. Other candidate is int type. In the extreme case you should write why the code does what it does, not what it does.

Implementation

It is really hard to understand what your code does, since it's not straightforward. Code should aim at correctness first, clarity second, performance third.

It's good that you're using range loops.

   if (type.first == c){  //if it's an opening bracket, add a new open bracket to the vector
                incr = 1;
                counts[c].push_back(0);
                break;
            }
            if (type.second == c){  //if it's a closing bracket, set incr to decrement each value
                incr = -1;
                break;
            }

This place of the code is very confusing. In the beginning I thought that we could use else to chain this, but then I noticed that it's type.first and type.second, which changed my opinion. But then I found that it always compares to c, so now it's pretty clear that there have to be else, since second shouldn't be checked if first condition is met. It is good both clarity and performance wise.

        int incr; 

outside loop. It should be inside, because it's logical scope belongs to the loop. If you worry about performance, compiler should be able to figure that out, so your code will be both readable and performant.

Your braces function violate single responsibility principle. The principle greatly improves the code if used correctly.

Names are ambiguous in some places.

So lets make the code better.

Suggested implementation

First of all, lets nail down the name of the "entry point" function. is_valid_brace_sequence in my opinion is alright.

std::vector<std::string> is_valid_brace_sequence(const std::vector<std::string>& input)

Notice const std::vector<std::string>&. Algorithm doesn't need a copy. Copying will probably decrease performance.

If it wouldn't be part of problem statement, I would suggest having 2 input iterators for the beginning and end of the input, and one output iterator for the beginning of the output, so algorithm wouldn't mess with allocations.

Next, the algorithm goes over input, calls checker function on every element and records the results:

std::vector<std::string> results;
results.reserve(input.size());
for (const auto& element : input)
{
    bool result = check_validity(element);
    if (result)
    {
        results.push_back("YES");
    }
    else
    {
        results.push_back("NO");
    }
}

return results;

Using reserve increases performance, since vector won't need to resize. Also, it should be used in places where the size of the input in elements is known before hand.

Next, is check_validity function. It will also preserve const correctness:

bool check_validity(const std::string& input)

The algorithm used will be the following: if either left sided brace is encountered ('(', '[','{'), right sided brace will be put into stack. If right sided brace is encountered, top of the stack is checked for the exactly same brace, if it's not, return false.

bool check_validity(const std::string& input)
{
    std::stack<char> sequence;
    for (const auto& character: input)
    {
        switch (character)
        {
        case '(':
            sequence.push(')');
            break;
        case '{':
            sequence.push('}');
            break;
        case '[':
            sequence.push(']');
            break;
        case ')':
            if (!is_expected_brace(sequence, character))
            {
                return false;
            }
            break;
        case '}':
            if (!is_expected_brace(sequence, character))
            {
                return false;
            }
            break;
        case ']':
            if (!is_expected_brace(sequence, character))
            {
                return false;
            }
            break;
        default:
            continue;       
        }
    }

    return true;
}

So the reason the algorithm works is that stack is LIFO container (last in first out). Since the type of the right sided brace should match the last left sided, so stack matches needs of the algorithm perfectly. Notice the use of switch. It increases performance because it generates jump table.

I've put all the boilerplate code of checking on encounter of right sided brace into the separate function:

bool is_expected_brace(std::stack<char>& sequence, char brace)
{
    if (sequence.empty() || sequence.top() != brace)
    {
        return false;
    }
    sequence.pop();
    return true;
}

Notice the logical OR operator (||). It provides short circuit ifs, so accessing the stack won't be undefined behavior.

Although it increases readability of the caller function, both of them has tight coupling between each other, so it limits the usability of them in case they are separated.

Put together

#include <vector>
#include <stack>
#include <string>
#include <iostream>

bool is_expected_brace(std::stack<char>& sequence, char brace)
{
    if (sequence.empty() || sequence.top() != brace)
    {
        return false;
    }
    sequence.pop();
    return true;
}

bool check_validity(const std::string& input)
{
    std::stack<char> sequence;
    for (const auto& character: input)
    {
        switch (character)
        {
        case '(':
            sequence.push(')');
            break;
        case '{':
            sequence.push('}');
            break;
        case '[':
            sequence.push(']');
            break;
        case ')':
            if (!is_expected_brace(sequence, character))
            {
                return false;
            }
            break;
        case '}':
            if (!is_expected_brace(sequence, character))
            {
                return false;
            }
            break;
        case ']':
            if (!is_expected_brace(sequence, character))
            {
                return false;
            }
            break;
        default:
            continue;       
        }
    }

    return true;
}

std::vector<std::string> is_valid_brace_sequence(const std::vector<std::string>& input)
{
    std::vector<std::string> results;
    results.reserve(input.size());
    for (const auto& element : input)
    {
        bool result = check_validity(element);
        if (result)
        {
            results.push_back("YES");
        }
        else
        {
            results.push_back("NO");
        }
    }

    return results;
}

int main()
{
    std::vector<std::string> test_input{ "{{}}", "[[[]]", "[](){}", "[[])", "{[()]}" };
    std::vector<std::string> results = is_valid_brace_sequence(test_input);
    for (const auto& element : results)
    {
        std::cout << element << " ";
    }

}