#include #include #include #include #include template class Stack { private: size_t _len; std::vector _data; public: explicit Stack(size_t alloc_size = 128); size_t push(T elem); T pop(); size_t len(); }; template size_t Stack::push(T elem) { if (this->_data.size() > this->_len) { this->_data[this->_len] = elem; this->_len++; return this->_len; } this->_data.push_back(elem); this->_len = this->_data.size(); return this->_len; }; template Stack::Stack(size_t alloc_size) : _len(0), _data(alloc_size) {}; template T Stack::pop() { if (this->_len == 0) { std::abort(); } this->_len--; return this->_data[this->_len]; } template size_t Stack::len() { return this->_len; } enum class BracketType { CURLY = 0, SQUARE, ROUND, MAX, }; enum class BracketDirection { OPENING = 0, CLOSING, MAX, }; typedef std::pair Bracket_t; const std::string YES = "YES"; const std::string NO = "NO"; std::string ltrim(const std::string &); std::string rtrim(const std::string &); Bracket_t toType(char v) { switch (v) { case '[': return {BracketType::ROUND, BracketDirection::OPENING}; case '{': return {BracketType::CURLY, BracketDirection::OPENING}; case '(': return {BracketType::SQUARE, BracketDirection::OPENING}; case ']': return {BracketType::ROUND, BracketDirection::CLOSING}; case '}': return {BracketType::CURLY, BracketDirection::CLOSING}; case ')': return {BracketType::SQUARE, BracketDirection::CLOSING}; default: return {BracketType::MAX, BracketDirection::MAX}; } } /* * Complete the 'isBalanced' function below. * * The function is expected to return a std::STRING. * The function accepts std::STRING s as parameter. */ std::string isBalanced(std::string s) { if (s.empty()) { return YES; } Stack brackets; for (char i: s) { Bracket_t b = toType(i); if (b.second == BracketDirection::OPENING) { brackets.push(b.first); continue; } if (brackets.len() > 0) { auto ctx = brackets.pop(); if (ctx == b.first) { continue; } } return NO; } return brackets.len() > 0 ? NO : YES; } int main() { std::ofstream fout(getenv("OUTPUT_PATH")); std::string t_temp; getline(std::cin, t_temp); int t = stoi(ltrim(rtrim(t_temp))); for (int t_itr = 0; t_itr < t; t_itr++) { std::string s; getline(std::cin, s); std::string result = isBalanced(s); fout << result << "\n"; } fout.close(); return 0; } std::string ltrim(const std::string &str) { std::string s(str); s.erase( s.begin(), find_if(s.begin(), s.end(), not1(std::ptr_fun(isspace))) ); return s; } std::string rtrim(const std::string &str) { std::string s(str); s.erase( find_if(s.rbegin(), s.rend(), not1(std::ptr_fun(isspace))).base(), s.end() ); return s; }