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.