#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>

using namespace std;

bool foo(const string& context, const size_t pos) {
  const auto it = next(cbegin(context), pos);
  const auto before = accumulate(cbegin(context), it, 0, [](const auto output, const auto input) {
    if(input == '{') {
      return output + 1;
    }
    else if(input == '}' && output > 0) {
      return output - 1;
    }
    else {
      return output;
    }
  });
  const auto after = accumulate(it, cend(context), 0, [](const auto output, const auto input) {
    if(input == '{') {
      return output + 1;
    }
    else if(input == '}') {
      return output - 1;
    }
    else {
      return output;
    }
  });

  return before + after >= 0;
}

int main() {
  cout << boolalpha;

  for(const auto& test : { ""s, "{"s, "}"s, "{}"s, "{{}}"s, "}{}"s, "{{}"s, "{}}"s, "{}{"s }) {
    cout << test << endl;

    for(size_t i = 0; i <= test.size(); ++i) {
      cout << '\t' << i << ": " << foo(test, i) << endl;
    }
  }
}