CSP化学方程式

csp_formula.cc

#include <iostream>
#include <map>
#include <memory>

using Formula = std::map<std::string, int>;

class ParseContext {
public:
    ParseContext(const std::string& string, int position):
        string_(string), position_(position) {}

    char* NextChar() {
        if (position_ >= static_cast<int>(string_.size())) {
            return nullptr;
        }
        return &string_[position_++];
    }

    void ShiftBack() {
        position_--;
    }
private:
    std::string string_;
    int position_;
};

std::unique_ptr<int> parseDigit(ParseContext& context);
std::unique_ptr<int> parseDigits(ParseContext& context);
std::unique_ptr<int> parseCoefficient(ParseContext& context);

template <typename Predicate>
std::unique_ptr<char> parsePredicate(ParseContext& context, Predicate&& pred) {
    auto* chr = context.NextChar();
    if (!chr) {
        return nullptr;
    }
    if (pred(*chr)) {
        return std::unique_ptr<char>(new char(*chr));
    }
    context.ShiftBack();
    return nullptr;
}

std::unique_ptr<char> parseUpperCase(ParseContext& context);
std::unique_ptr<char> parseLowerCase(ParseContext& context);
std::unique_ptr<std::string> parseElement(ParseContext& context);
char* expectChar(ParseContext& context, char chr);
std::unique_ptr<Formula> parseTerm(ParseContext& context);
std::unique_ptr<Formula> parseFormula(ParseContext& context);
std::unique_ptr<Formula> parseExpr(ParseContext& context);
std::pair<Formula, Formula> parseEquation(ParseContext& context);

int main() {
    int count;
    std::cin >> count;
    std::string line;
    for (int i = 0; i < count; i++) {
        std::cin >> line;
        ParseContext context(line, 0);
        Formula left, right;
        std::tie(left, right) = parseEquation(context);
        std::cout << ((left == right) ? "Y" : "N") << std::endl;
    }
    return 0;
}

std::unique_ptr<int> parseDigit(ParseContext& context) {
    auto result = parsePredicate(context, [](char c) {
        return c >= '0' && c <= '9';
    });
    if (!result) {
        return nullptr;
    }
    return std::unique_ptr<int>(new int(*result - '0'));
}

std::unique_ptr<int> parseDigits(ParseContext& context) {
    int num = 0;
    auto result = parseDigit(context);
    while (result) {
        num = num * 10 + *result;
        result = parseDigit(context);
    }
    if (num == 0) {
        return nullptr;
    }
    return std::unique_ptr<int>(new int(num));
}

std::unique_ptr<int> parseCoefficient(ParseContext& context) {
    auto digits = parseDigits(context); 
    return digits;
}

std::unique_ptr<char> parseUpperCase(ParseContext& context) {
    return parsePredicate(context, [](char c) {
        return c >= 'A' && c <= 'Z';
    });
}

std::unique_ptr<char> parseLowerCase(ParseContext& context) {
    return parsePredicate(context, [](char c) {
        return c >= 'a' && c <= 'z';
    });
}

std::unique_ptr<std::string> parseElement(ParseContext& context) {
    std::string result = "";
    auto chr = parseUpperCase(context); 
    while (chr) {
        result += *chr;
        chr = parseLowerCase(context);
    }
    if (result.empty()) {
        return nullptr;
    }
    return std::unique_ptr<std::string>(new std::string(result));
}

char* expectChar(ParseContext& context, char chr) {
    char* ch = context.NextChar();
    if (!ch) {
        return nullptr;
    }
    if (*ch == chr) {
        return ch;
    }
    context.ShiftBack();
    return nullptr;
}

std::unique_ptr<Formula> parseTerm(ParseContext& context) {
    if (expectChar(context, '(')) {
        auto formula = parseFormula(context);
        expectChar(context, ')');
        return formula;
    }
    auto element = parseElement(context);
    if (!element) {
        return nullptr;
    }
    std::unique_ptr<Formula> formula(new Formula());
    (*formula)[*element] = 1;
    return formula;
}

std::unique_ptr<Formula> parseFormula(ParseContext& context) {
    std::unique_ptr<Formula> result(new Formula());

    auto term = parseTerm(context);
    while (term) {
        auto coeff = parseCoefficient(context);
        if (coeff) {
            for (auto& elem : *term) {
                elem.second *= *coeff;
            }
        }
        for (auto& elem : *term) {
            (*result)[elem.first] += elem.second;
        }
        term = parseTerm(context);
    }
    if (result->empty()) {
        return nullptr;
    }
    return result;
}

std::unique_ptr<Formula> parseExpr(ParseContext& context) {
    std::unique_ptr<Formula> result(new Formula());

    auto coeff = parseCoefficient(context);
    auto formula = parseFormula(context);
    while (formula) {
        if (coeff) {
            for (auto& elem : *formula) {
                elem.second *= *coeff;
            }
        }
        for (auto& elem : *formula) {
            (*result)[elem.first] += elem.second;
        }
        expectChar(context, '+');
        coeff = parseCoefficient(context);
        formula = parseFormula(context);
    }

    if (result->empty()) {
        return nullptr;
    }
    return result;
}

std::pair<Formula, Formula> parseEquation(ParseContext& context) {
    auto leftFormula = parseExpr(context);
    expectChar(context, '=');
    auto rightFormula = parseExpr(context);
    return std::pair<Formula, Formula>{*leftFormula, *rightFormula};
}