balanced-brackets/main.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>

template<typename T>
class Stack {
private:
    size_t _len;
    std::vector<T> _data;
public:
    explicit Stack(size_t alloc_size = 128);

    size_t push(T elem);

    T pop();

    size_t len();
};

template<typename T>
size_t Stack<T>::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<typename T>
Stack<T>::Stack(size_t alloc_size) : _len(0), _data(alloc_size) {};

template<typename T>
T Stack<T>::pop() {

    if (this->_len == 0) {
        std::abort();
    }

    this->_len--;

    return this->_data[this->_len];
}

template<typename T>
size_t Stack<T>::len() {
    return this->_len;
}

enum class BracketType {
    CURLY = 0,
    SQUARE,
    ROUND,
    MAX,
};

enum class BracketDirection {
    OPENING = 0,
    CLOSING,
    MAX,
};

typedef std::pair<BracketType, BracketDirection> 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<BracketType> 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<int, int>(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<int, int>(isspace))).base(),
            s.end()
    );

    return s;
}