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

static const std::vector<std::string> EXAMPLES = {
    	"({[{}]{}[]})",
        "({}}{[{}]{}[]})",
        "({[{}]{}[]}",
        "({[{}]{}]})",
        "({[{}{}[]})",
        "",
        "{}",
        "(i (am so [lispish]))",
};

static const char eof = char(-1);
static const std::string open_braces  = "({[";
static const std::string close_braces = ")}]";

inline char matching_brace(char c)
{
    const std::size_t i = close_braces.find(c);
    return i != std::string::npos ? open_braces[i] : eof;
}

static bool is_balanced(const std::string &s)
{
    std::string brace_stack;

    for (auto c : s) {
        if (open_braces.find(c) != std::string::npos) {
            brace_stack.push_back(c);
            continue;
        }

        const char pair = matching_brace(c);
        if (pair != eof) {
            if (!brace_stack.empty() && brace_stack.back() == pair) {
                brace_stack.pop_back();
            } else {
                return false;
            }
        }
    }

    return brace_stack.empty();
}

int main()
{
    std::cout << std::boolalpha;
    for (const auto & e : EXAMPLES) {
        std::cout << is_balanced(e) << "\n";
    }
    return 0;
}