up09-3 (grammar 2)

#include <iostream>
#include <map>
#include <string>
#include <cctype>
#include <array>
#include <algorithm>

void to_lower(std::string::iterator begin, std::string::iterator end)
{
    std::transform(begin, end, begin, [](unsigned char c) { return std::tolower(c); });
}


bool is_inconclusive_context_free(const std::multimap<std::string, std::string> &dict)
{
    bool flag1 = false;
    bool flag2 = false;

    for (auto &c:dict) {
        if (c.second.find("S") != std::string::npos) {
            flag1 = true;
        }
        if (c.second == "_") {
            if (c.first != "S") {
                return false;
            } else {
                flag2 = true;
            }
        }
    }
    return !(flag1 && flag2);
}

bool regular_left(const std::multimap<std::string, std::string> &dict)
{

    for (auto &c:dict) {
        if (c.second.size() == 1 && c.second[0] == '_') {
            continue;
        }
        std::string tmp(c.second);
        to_lower(tmp.begin() + 1, tmp.end());
        if (tmp != c.second) {
            return false;
        }
    }
    return true;
}

bool regular_right(const std::multimap<std::string, std::string> &dict)
{
    for (auto &c:dict) {
        if (c.second.size() == 1 && c.second[0] == '_') {
            continue;;
        }
        std::string tmp(c.second);
        to_lower(tmp.begin(), tmp.end() - 1);
        if (tmp != c.second) {
            return false;
        }
    }
    return true;
}

bool automata_left(const std::multimap<std::string, std::string> &dict)
{
    auto range = dict.equal_range("S");
    bool flag1 = false;
    bool flag2 = false;
    for (auto i = range.first; i != range.second; i++) {
        if (i->second.size() > 1) {
            continue;
        }
        if (std::isupper(i->second[0])) {
            flag1 = true;
        }
        if (i->second[0] == '_') {
            flag2 = true;
        }
    }
    if (flag1 && !flag2) {
        return false;
    }

    for (auto &c:dict) {
        if (c.second.size() > 2) {
            return false;
        }
        if (c.second.size() == 1 && std::islower(c.second[0]) == 0) {
            if (c.second != "S" && c.first == "S" && (c.second == "_" || std::isupper(c.second[0]))) {
                continue;;
            } else {
                return false;
            }
        }
        if (c.second.size() == 2 &&
            (std::isupper(c.second[0]) == 0 || std::islower(c.second[1]) == 0 || (c.second[0] == 'S' && flag2))) {
            return false;
        }
    }
    return true;
}


bool automata_right(const std::multimap<std::string, std::string> &dict)
{
    auto range = dict.equal_range("S");
    bool flag1 = false;
    bool flag2 = false;
    for (auto i = range.first; i != range.second; i++) {
        if (i->second.size() >= 2) {
            continue;
        }
        if (std::isupper(i->second[0])) {
            flag1 = true;
        }
        if (i->second[0] == '_') {
            flag2 = true;
        }
    }
    if (flag1 && !flag2) {
        return false;
    }

    for (auto &c:dict) {
        if (c.second.size() > 2) {
            return false;
        }
        if (c.second.size() == 1 && (std::islower(c.second[0]) == 0)) {
            if (c.second != "S" && c.first == "S" && (c.second == "_" || std::isupper(c.second[0]))) {
                continue;;
            } else {
                return false;
            }
        }
        if (c.second.size() == 2 &&
            (std::islower(c.second[0]) == 0 || std::isupper(c.second[1]) == 0 || (c.second[1] == 'S' && flag2))) {
            return false;
        }
    }
    return true;
}

int main()
{
    std::multimap<std::string, std::string> dict;
    std::string key, value;
    std::string t("AB");

    while (std::cin >> key >> value) {
        dict.insert({key, value});
    }
    std::array<bool, 5> ans;

    ans[0] = is_inconclusive_context_free(dict);
    ans[1] = regular_left(dict);
    ans[2] = regular_right(dict);
    ans[3] = automata_left(dict);
    ans[4] = automata_right(dict);

    if (!ans[0] && !ans[1] && !ans[2]) {
        std::cout << "2" << std::endl;
    } else if (ans[0] && !ans[1] && !ans[2]) {
        std::cout << "21" << std::endl;
    } else if (ans[1] && !ans[3]) {
        std::cout << "31" << std::endl;
    } else if (ans[3]) {
        std::cout << "311" << std::endl;
    } else if (ans[2] && !ans[4]) {
        std::cout << "32" << std::endl;
    } else if (ans[4]) {
        std::cout << "321" << std::endl;
    }
}