Check balanced brackets in a text

Question

Given an input text that is a combination of {, }, [, ], (, ) characters, check whether the input text has balanced brackets or not.

This was a question from hackerrank, and the code below solves it in a little bit complicated way while favoring generality.

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


template<typename T>
class balancedBrackets
{
    enum class bracketType { OPENING, CLOSING };
    std::unordered_map<T, bracketType> mBracketIdentifiers;//which bracket symbol is the opening character and which is the closing character
    std::unordered_map<T, T> mBracketPairs;//which bracket symbol matches with which other
public:
    balancedBrackets(){}
    balancedBrackets(std::initializer_list< std::pair<T, T> > pairs)
    {
        addBracketPairs(pairs);
    }

    void addBracketPairs(std::initializer_list< std::pair<T, T> > pairs)
    {
        for (auto elem : pairs)
        {
            if (mBracketIdentifiers.find(elem.first) != mBracketIdentifiers.end() ||
                mBracketIdentifiers.find(elem.second) != mBracketIdentifiers.end())
            {
                continue;//if any member of this bracket pair already exist, skip.
            }
            mBracketPairs.emplace(elem);
            mBracketIdentifiers.emplace(elem.first, bracketType::OPENING);
            mBracketIdentifiers.emplace(elem.second, bracketType::CLOSING);
        }
    }

    void removeBracketPairs(std::initializer_list< std::pair<T, T> > pairs) 
    {
        for (auto elem : pairs)
        {
            auto search = mBracketPairs.find(elem.first);
            if (search != mBracketPairs.end() && search->second == elem.second)//is this a valid pair?
            {
                mBracketPairs.erase(search);
                mBracketIdentifiers.erase(elem.first);
                mBracketIdentifiers.erase(elem.second);
            }
        }
    }

    void clearBracketPairs()
    {
        mBracketPairs.clear();
        mBracketIdentifiers.clear();
    }

    bool isBalanced(std::vector<T> expression) 
    {
        if (mBracketPairs.empty())//no bracket rules
        {
            throw std::logic_error("no bracket rules");
        }

        std::stack<T> myStack;
        for (auto elem : expression)
        {
            if (mBracketIdentifiers[elem] == bracketType::OPENING)
            {
                myStack.push(elem);
            }
            else
            {
                if (mBracketIdentifiers[elem] == bracketType::CLOSING)
                {
                    if (!myStack.empty() && mBracketPairs[myStack.top()] == elem)//do not call top on an empty stack
                    {
                        myStack.pop();
                    }
                    else //imbalanced text
                    {
                        return false;
                    }
                }
                else //invalid characters
                {
                    return false;
                }
            }
        }
        return myStack.empty();
    }
    bool isBalanced(std::basic_string<T> expression)//make this class work with std::string family too. 
    {
        return isBalanced(std::vector<T>(expression.begin(), expression.end()));
    }
};

int main()
{
    balancedBrackets<char> a({ { '{','}' } ,{ '[',']' },{ '(',')' } });
    a.isBalanced(std::string("{{[[(())]]}}"));
    return 0;
}

I have tried to write an idiomatic and generalized version that can easily work with new bracket styles without changing the code. Moreover, a bracket pair is not necessarily be a char in this version.

Answer 1

This is looking pretty good! But there is definitely room for improvement:

Better template parameter name

T generally refers to "any type". Since your template is based on a character type, you should use something like CharT to be more explicit.

Is there really a reason for this to be mutable?

addBracketPairs(), removeBracketPairs() and clearBracketPairs() is just extraneous api surface to me.

I would personally have favored a public API consisting entirely of:

• Construct a brackets matcher.
• Use the bracket matcher to match brackets.
• MAYBE have a join() function to combine two matchers together into 1.

On the surface, it looks less flexible, but it's as functional as your version, and takes a fraction of the time to wrap your head around.

It also means that your emptiness check can be moved to the constructor, so that you don't have to perform that check every single time isBalanced() is invoked.

isBalanced() should take a pair of iterators.

The correct signature for isBalanced() is:

template<typename IteT> bool isBalanced(IteT begin, IteT end) const;

This way, you can consume from vectors, strings, character arrays, etc... and there is no need to make a copy of the data into a vector prior.

member functions that do not mutate the class should be marked const.

Pretty simole, isBalanced() should be marked const.

Use const references when not taking posession of the data.

For example:

bool isBalanced(const std::basic_string<T>& expression)

This avoids extra copies.