化学方程式

题目描述

化学方程式，也称为化学反应方程式，是用化学式表示化学反应的式子。给出一组化学方程式，请你编写程序判断每个方程式是否配平（也就是方程式中等号左右两边的元素种类和对应的原子个数是否相同)。

本题给出的化学方程式由大小写字母、数字和符号（包括等号=、加号+、左圆括号(和右圆括号))组成，不会出现其他字符（包括空白字符，如空格、制表符等)。化学方程式的格式与化学课本中的形式基本相同（化学式中表示元素原子个数的下标用正常文本，如 $H_2O$ 写成 $H2O$)，用自然语言描述如下:

• 化学方程式由左右两个表达式组成，中间用一个等号=连接，如2H2+O2=2H2O；
• 表达式由若干部分组成，每部分由系数和化学式构成，部分之间用加号+连接,如2H2+O2、2H2O；
• 系数是整数或空串，如为空串表示系数为 $1$；
• 整数由一个或多个数字构成；
• 化学式由若干部分组成，每部分由项和系数构成，部分之间直接连接，如H2O、CO2、Ca(OH)2、Ba3(PO4)2；
• 项是元素或用左右圆括号括起来的化学式，如 H、Ca、(OH)、(PO4):
• 元素可以是一个大写字母，也可以是一个大写字母跟着一个小写字母，如H、O、Ca。

用巴科斯范式(Backus-Naur form，BNF)给出的形式化定义如下：

<equation> ::= <expr> "=" <expr>
<expr> ::= <coef> <formula> | <expr> "+" <coef> <formula>
<coef> ::= <digits> | ""
<digits> ::= <digit> | <digits> <digit>
<digit> ::= "0" | "1" | ... | "9"
<formula> ::= <term> <coef> | <formula> <term> <coef>
<term> ::= <element> | "(" <formula> ")"
<element> ::= <uppercase> | <uppercase> <lowercase>
<uppercase> ::= "A" | "B" | ... | "Z"
<lowercase> ::= "a" | "b" | ... | "z"

输入格式

从标准输入读入数据。
输入的第一行包含一个正整数$n$，表示输入的化学方程式个数。接下来 $n$ 行，每行是一个符合定义的化学方程式。

输出格式

输出到标准输出。
输出共 $n$ 行，每行是一个大写字母 Y 或 N，回答输入中相应的化学方程式是否配平。

子任务

• $1 \leq n \leq 100$
• 输入的化学方程式都是符合题目中给出的定义的，且长度不超过 $1000$
• 系数不会有前导零，也不会有为零的系数
• 化学方程式的任何一边，其中任何一种元素的原子总个数都不超过 $10^{18}$

测试用例

输入

11
H2+O2=H2O
2H2+O2=2H2O
H2+Cl2=2NaCl
H2+Cl2=2HCl
CH4+2O2=CO2+2H2O
CaCl2+2AgNO3=Ca(NO3)2+2AgCl
3Ba(OH)2+2H3PO4=6H2O+Ba3(PO4)2
3Ba(OH)2+2H3PO4=Ba3(PO4)2+6H2O
4Zn+10HNO3=4Zn(NO3)2+NH4NO3+3H2O
4Au+8NaCN+2H2O+O2=4Na(Au(CN)2)+4NaOH
Cu+As=Cs+Au

输出

N
Y
N
Y
Y
Y
Y
Y
Y
Y
N

#include <bits/stdc++.h>
using namespace std;

vector<string> split(string& str, char sep) {
    vector<string> v;
    stringstream ss(str);
    string s;
    while (getline(ss, s, sep))
        v.emplace_back(s);
    return v;
}

int readInt(string& str, int& pos) {
    int ans = 0;
    while (pos != str.size() && isdigit(str[pos]))
        ans = ans * 10 + (str[pos++] - '0');
    return ans == 0 ? 1 : ans;
}

string readElement(string& str, int& pos) {
    string res;
    res += str[pos++];
    if (islower(str[pos]))
        res += str[pos++];
    return res;
}
map<string, int> readFormula(string& formula, int& pos);
map<string, int> readTerm(string& term, int& pos) {
    if (term[pos] == '(') {
        pos++;
        map<string, int> res = readFormula(term, pos);
        pos++;
        return res;
    } else {
        string element = readElement(term, pos);
        map<string, int> res;
        res[element] = 1;
        return res;
    }
}

void merge(map<string, int>& res, map<string, int>& cur, int coef) {
    for (auto& i : cur)
        res[i.first] += coef * i.second;
}

map<string, int> readFormula(string& formula, int& pos) {
    map<string, int> res;
    while (pos != formula.size() && formula[pos] != ')') {
        map<string, int> cur = readTerm(formula, pos);
        int coef = readInt(formula, pos);
        merge(res, cur, coef);
    }
    return res;
}

map<string, int> parseExpr(string& expr) {
    map<string, int> res;
    vector<string> formulas = split(expr, '+');
    for (auto i : formulas) {
        int pos = 0;
        int coef = readInt(i, pos);
        map<string, int> cur = readFormula(i, pos);
        merge(res, cur, coef);
    }
    return res;
}
void solve() {
    string equation;
    cin >> equation;
    vector<string> expr = split(equation, '=');
    if (parseExpr(expr[0]) == parseExpr(expr[1]))
        cout << "Y\n";
    else
        cout << "N\n";
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}