CSP CCF： 201912-3 化学方程式 （C++）

目录

• 题目来源
• “名词说明”
• 20分 但得了 30分
• 40分
• 60
• 80
• 100

题目来源

化学方程式

“名词说明”

1. 系数： 一个表达式的最前边的数字。 比如 3A2(B5)4 中系数为3。
2. 项数：一个表达式中在元素或左右括号括起来的化学式后的数字。比如 3A2(B5)4 中系数为2、5、4。

20分 但得了 30分

数据特点： 只包含大写字母和等号
解决方案： 记录左右两边大写字母及对应的个数
1. 使用 map exprL, exprR 来存储化学方程式左右两边的表达式
2. 使用 map elemL, elemR 来存储化学方程式左右两边的元素及个数
3. 使用 getExpr() 函数 获得等式左右表达式
4. 使用 getElem() 函数 获得等式左右元素及个数
5. 最后判断elemL、elemR中元素个数是否相等。 若相等，那每个元素的个数是否相同。

#include 
#include 
#include 
#include 

using namespace std;

string formula;                    // 化学方程式
vector<string> exprL, exprR;       // 化学方程式左右的表达式
map<string, int> elemL, elemR;     // 化学方程式左右两边元素及个数


//  获取化学方程式左右两边表达式
void getExpr() {
    int index = 0;

    string str = "";
    while (formula[index] != '=') {  // 左边
        str = "";
        str.push_back(formula[index++]);
        exprL.emplace_back(str);
    }
    ++index;
    while (index < formula.size()) {  // 右边
        str = "";
        str.push_back(formula[index++]);
        exprR.emplace_back(str);
    }
}

// 获得等式左右的元素及个数
void getElem(int equaIndex) {

    // 左边
    for (string str: exprL) {
        int indexL = 0;

        while (indexL < str.size()) {
            string s = "";  // 使用 push_back() 间接将 Char 转换成 String
            s.push_back(str[indexL++]);
            ++elemL[s];
        }
    }

    // 右边
    for (string str: exprR) {
        int indexR = 0;

        while (indexR < str.size()) {
            string s = "";  // 使用 push_back() 间接将 Char 转换成 String
            s.push_back(str[indexR++]);
            ++elemR[s];
        }
    }
}

int main() {

    int N;
    cin>>N;

    while (N-- > 0) {
        // 清理 全局数据中 上一个化学方程式的数据
        exprL.clear();
        exprR.clear();
        elemL.clear();
        elemR.clear();


        cin>>formula;

        int equaIndex = 0;  // 等号下标
        while (formula[equaIndex] != '=') {
            ++equaIndex;
        }

        getExpr();  // 获取化学方程式左右两边表达式

        // 对左右两边元素计数
        getElem(equaIndex);

        // 判断等式左右元素是否守恒
        if (elemL.size() != elemR.size()) {
            cout<<'N'<<endl;
        }
        else {
            bool flag = true;
            for (pair<string, int> p: elemL) {
                if (elemR[p.first] != p.second) {
                    cout<<'N'<<endl;
                    flag = false;
                    break;
                }
            }

            if (flag) {
                cout<<'Y'<<endl;
            }
        }
    }

    return 0;
}

40分

数据特点： 包含 大写字母、小写字母、等号、加号。
解决方案： 识别出“+”，根据“+”找出各个表达式，最后分别记录化学表达式左右表达式中的元素。
1. 修改 getExpr() 函数： 添加判断“+” 、识别有大小写的元素 以及 一个表达式中多个元素的代码。
2. 修改 getElem() 函数：添加 获取有小写字母的元素 的功能。

/* 40 */
#include 
#include 
#include 
#include 

using namespace std;

string formula;                    // 化学方程式
vector<string> exprL, exprR;       // 化学方程式左右的表达式
map<string, int> elemL, elemR;     // 化学方程式左右两边元素及个数


//  获取化学方程式左右两边表达式
void getExpr() {
    int index = 0;

    string str = "";
    while (formula[index] != '=') {  // 左边
        if (formula[index] != '+') {
            str.push_back(formula[index]);
        }
        else {
            exprL.emplace_back(str);
            str = "";
        }
        index++;
    }
    exprL.emplace_back(str);
    ++index;
    str = "";
    while (index < formula.size()) {  // 右边
        if (formula[index] != '+') {
            str.push_back(formula[index]);
        }
        else {
            exprR.emplace_back(str);
            str = "";
        }
        index++;
    }
    exprR.emplace_back(str);
}

// 获得等式左右的元素及个数
void getElem(int equaIndex) {

    // 左边
    for (string str: exprL) {
        int indexL = 0;

        while (indexL < str.size()) {
            string s = "";  // 使用 push_back() 间接将 Char 转换成 String
            s.push_back(str[indexL++]);
            while (str[indexL] <= 'z' && str[indexL] >= 'a') {
                s.push_back(str[indexL++]);
            }
            ++elemL[s];
        }
    }

    // 右边
    for (string str: exprR) {
        int indexR = 0;

        while (indexR < str.size()) {
            string s = "";  // 使用 push_back() 间接将 Char 转换成 String
            s.push_back(str[indexR++]);
            while (str[indexR] <= 'z' && str[indexR] >= 'a') {
                s.push_back(str[indexR++]);
            }
            ++elemR[s];
        }
    }
}

int main() {
    ifstream cin("in.txt");

    int N;
    cin>>N;

    while (N-- > 0) {
        // 清理 全局数据中 上一个化学方程式的数据
        exprL.clear();
        exprR.clear();
        elemL.clear();
        elemR.clear();


        cin>>formula;

        int equaIndex = 0;  // 等号下标
        while (formula[equaIndex] != '=') {
            ++equaIndex;
        }

        getExpr();  // 获取化学方程式左右两边表达式

        // 对左右两边元素计数
        getElem(equaIndex);

        // 判断等式左右元素是否守恒
        if (elemL.size() != elemR.size()) {
            cout<<'N'<<endl;
        }
        else {
            bool flag = true;
            for (pair<string, int> p: elemL) {
                if (elemR[p.first] != p.second) {
                    cout<<'N'<<endl;
                    flag = false;
                    break;
                }
            }

            if (flag) {
                cout<<'Y'<<endl;
            }
        }
    }

    return 0;
}

60

数据特征： 包含 大写字母、小写字母、等号、加号、数字。
解决方法：

1. getExpr() 函数中添加 判断表达式前系数是否为空串 “”, 若是空串，则补上 “1”。
2. 构建 getNum() 函数， 计算每个元素的 系数 * 项数。
3. 对应2修改getElem() 函数。

/* 60 */
#include 
#include 
#include 
#include 

using namespace std;

string formula;                    // 化学方程式
vector<string> exprL, exprR;       // 化学方程式左右的表达式
map<string, int> elemL, elemR;     // 化学方程式左右两边元素及个数


//  获取化学方程式左右两边表达式
void getExpr() {
    int index = 0;

    string str = "";
    if (formula[index] > '9' || formula[index] < 0) {  // 下一个表达式数字部分为 ""
        str = '1';
    }
    while (formula[index] != '=') {  // 左边
        if (formula[index] != '+') {  // 非 "+"
            str.push_back(formula[index]);
        }
        else {  // "+"
            exprL.emplace_back(str);
            str = "";
            if (formula[index + 1] > '9' || formula[index + 1] < 0) {
                str = '1';
            }
        }
        ++index;
    }
    exprL.emplace_back(str);
    ++index;
    str = "";
    if (formula[index] > '9' || formula[index] < 0) {  // 表达式前为 “”
        str = '1';
    }
    while (index < formula.size()) {  // 右边
        if (formula[index] != '+') {
            str.push_back(formula[index]);
        }
        else {
            exprR.emplace_back(str);
            str = "";
            if (index + 1 < formula.size() && (formula[index + 1] > '9' || formula[index + 1] < 0)) {  // 表达式前为 “”
                str = '1';
            }
        }
        index++;
    }
    exprR.emplace_back(str);
}


// 找出每个元素 （累计个数， 记得 系数 * 项数）
void getNum(string str, int &index, string &elem, int &digits) {
    // 获取元素
    elem.push_back(str[index++]);
    while (str[index] <= 'z' && str[index] >= 'a') {
        elem.push_back(str[index++]);
    }

    // 获取项数
    //int digits = 0;
    while (str[index] >= '0' && str[index] <= '9') {
        digits = digits * 10 + (str[index++] - '0');
    }
    if (digits == 0) {  // 如果没有项数， 则默认为 1
        digits = 1;
    }
}


// 获得等式左右的元素及个数
void getElem(int equaIndex) {

    // 左边
    for (string str: exprL) {
        int indexL = 0;

        int coef = 0;
        // 获取表达式前系数
        while (str[indexL] >= '0' && str[indexL] <= '9') {
            coef = coef * 10 + (str[indexL++] - '0');
        }
        // 找出每个元素 （累计个数， 记得 系数 * 项数）
        while (indexL < str.size()) {
            string elem = "";
            int digits = 0;
            getNum(str, indexL, elem, digits);
            elemL[elem] = elemL[elem] + coef * digits;  // 累计
        }
    }

    // 右边
    for (string str: exprR) {
        int indexR = 0;

        int coef = 0;
        // 获取表达式前系数
        while (str[indexR] >= '0' && str[indexR] <= '9') {
            coef = coef * 10 + (str[indexR++] - '0');
        }
        // 找出每个元素 （累计个数， 记得 系数 * 项数）
        while (indexR < str.size()) {
            string elem = "";
            int digits = 0;
            getNum(str, indexR, elem, digits);
            elemR[elem] = elemR[elem] + coef * digits;  // 累计
        }
    }
}

int main() {
    ifstream cin("in.txt");

    int N;
    cin>>N;

    while (N-- > 0) {
        // 清理 全局数据中 上一个化学方程式的数据
        exprL.clear();
        exprR.clear();
        elemL.clear();
        elemR.clear();


        cin>>formula;

        int equaIndex = 0;  // 等号下标
        while (formula[equaIndex] != '=') {
            ++equaIndex;
        }

        getExpr();  // 获取化学方程式左右两边表达式

        // 对左右两边元素计数
        getElem(equaIndex);

        // 判断等式左右元素是否守恒
        if (elemL.size() != elemR.size()) {
            cout<<'N'<<endl;
        }
        else {
            bool flag = true;
            for (pair<string, int> p: elemL) {
                if (elemR[p.first] != p.second) {
                    cout<<'N'<<endl;
                    flag = false;
                    break;
                }
            }

            if (flag) {
                cout<<'Y'<<endl;
            }
        }
    }

    return 0;
}

80

数据特征： 包含 大写字母、小写字母、等号、加号、数字、圆括号（圆括号不会嵌套）。
解决方法： 单独处理括号的内容。先记录括号后的项数，再将括号内的字符串按原先的方式处理。
1.修改 getElem()，因为等式左右两边的处理方式一致，就修改几个变量名，修改一下传的参数，降低他们的耦合性。
2.在getElem() 函数中添加处理无嵌套的括号的内容。先将括号内的元素字符串单独拿出来，记录他们的下标。再记录括号后边的项数num，将num和表达式最前边的系数相乘，构成新的项数。最后将字符串放到getNum()中计算系数（和原先的一样）。

/* 80 */
#include 
#include 
#include 
#include 

using namespace std;

string formula;                    // 化学方程式
vector<string> exprL, exprR;       // 化学方程式左右的表达式
map<string, int> elemL, elemR;     // 化学方程式左右两边元素及个数


//  获取化学方程式左右两边表达式, 每个表达式的格式都是 数字+元素/(元素)
void getExpr() {
    int index = 0;

    string str = "";
    if (formula[index] > '9' || formula[index] < '0') {  // 下一个表达式数字部分为 ""
        str += "1";
    }
    while (formula[index] != '=') {  // 左边
        if (formula[index] != '+') {  // 非 "+"
            str.push_back(formula[index]);
        }
        else {  // "+"
            exprL.emplace_back(str);
            str = "";
            if (formula[index + 1] > '9' || formula[index + 1] < '0') {
                str += "1";
            }
        }
        ++index;
    }
    exprL.emplace_back(str);
    ++index;
    str = "";
    if (formula[index] > '9' || formula[index] < '0') {  // 表达式前为 “”
        str += "1";
    }
    while (index < formula.size()) {  // 右边
        if (formula[index] != '+') {
            str.push_back(formula[index]);
        }
        else {
            exprR.emplace_back(str);
            str = "";
            if (index + 1 < formula.size() && (formula[index + 1] > '9' || formula[index + 1] < '0')) {  // 表达式前为 “”
                str += "1";
            }
        }
        index++;
    }
    exprR.emplace_back(str);
}

// 找出每个元素 （累计个数， 记得 系数 * 项数）
void getNum(string str, int &index, string &elem, int &digits) {
    // 获取元素
    elem.push_back(str[index++]);
    while (str[index] <= 'z' && str[index] >= 'a') {
        elem.push_back(str[index++]);
    }

    // 获取项数
    while (str[index] >= '0' && str[index] <= '9') {
        digits = digits * 10 + (str[index++] - '0');
    }
    if (digits == 0) {  // 如果没有项数， 则默认为 1
        digits = 1;
    }
}


// 获得等式左右的元素及个数
void getElem(vector<string> &expr, map<string, int> &elem) {
    for (string str: expr) {
        int index = 0;

        int coef = 0;
        // 获取表达式前系数
        while (str[index] >= '0' && str[index] <= '9') {
            coef = coef * 10 + (str[index++] - '0');
        }

        // 找出每个元素 （累计个数， 记得 系数 * 项数）
        while (index < str.size()) {
            if (str[index] == '(') {  // 遇到括号， 处理一个括号的内容

                // 获得括号内内容左、右下标
                int strL = index + 1, strR = index + 1;
                while (str[strR] != ')') {  // （xxx）
                    ++strR;
                }
                --strR;

                // 获得括号内内容数字 ———— num
                int numEnd = strR + 2, num = 0;
                while (str[numEnd] >= '0' && str[numEnd] <= '9') {  // 括号外的数字
                    num = num * 10 + (str[numEnd] - '0');
                    ++numEnd;
                }
                --numEnd;
                if (num == 0) {  // 默认值 1
                    num = 1;
                }

                // 记录括号内元素的个数
                while (strL <= strR) {
                    string e = "";
                    int digits = 0;
                    getNum(str, strL, e, digits);
                    elem[e] = elem[e] + coef * num * digits;  // 累计
                }

                index = numEnd + 1;  // indexL 需要跳离 括号
            }
            else {  // 没遇到括号, 记录元素的个数
                string e = "";
                int digits = 0;
                getNum(str, index, e, digits);
                elem[e] = elem[e] + coef * digits;  // 累计
            }
        }
    }

}


int main() {
    ifstream cin("in.txt");

    int N;
    cin>>N;

    while (N-- > 0) {
        // 清理 全局数据中 上一个化学方程式的数据
        exprL.clear();
        exprR.clear();
        elemL.clear();
        elemR.clear();

        cin>>formula;

        int equaIndex = 0;  // 等号下标
        while (formula[equaIndex] != '=') {
            ++equaIndex;
        }

        getExpr();  // 获取化学方程式左右两边表达式
    
        // 对左右两边元素计数
        getElem(exprL, elemL);  // 左
        getElem(exprR, elemR);  // 右

        // 判断等式左右元素是否守恒
        if (elemL.size() != elemR.size()) {
            cout<<'N'<<endl;
        }
        else {
            bool flag = true;
            for (pair<string, int> p: elemL) {
                if (elemR[p.first] != p.second) {
                    cout<<'N'<<endl;
                    flag = false;
                    break;
                }
            }

            if (flag) {
                cout<<'Y'<<endl;
            }
        }
    }
    return 0;
}

100

数据特征： 包含 大写字母、小写字母、等号、加号、数字、圆括号（圆括号会嵌套）。
解决方法： 将嵌套的括号使用递归的方法进行处理。
1. 修改getElem() 。将处理字符的部分全分给getKuo来做。先记录本表达式的系数（coef），再将剩余的部分看成一个括号内的内容，放到getKuo()中处理。
2. 增加getKuo() 用于递归来处理括号嵌套问题。基本上和80分的getElem()中有点像。改动的部分主要是处理括号的部分。现在是先记录当前遇到的左括号'('以及对应的右括号')'中字符串的下标，记录该括号后的项数，并更新括号内字符串的系数coef。再递归使用getKuo() 来更新系数coef，从而成功处理字符串的内容。

/* 100 */
#include 
#include 
#include 
#include 

using namespace std;

string formula;                    // 化学方程式
vector<string> exprL, exprR;       // 化学方程式左右的表达式
map<string, int> elemL, elemR;     // 化学方程式左右两边元素及个数


//  获取化学方程式左右两边表达式, 每个表达式的格式都是 数字+元素/(元素)
void getExpr() {
    int index = 0;

    string str = "";
    if (formula[index] > '9' || formula[index] < '0') {  // 下一个表达式数字部分为 ""
        str += "1";
    }
    while (formula[index] != '=') {  // 左边
        if (formula[index] != '+') {  // 非 "+"
            str.push_back(formula[index]);
        }
        else {  // "+"
            exprL.emplace_back(str);
            str = "";
            if (formula[index + 1] > '9' || formula[index + 1] < '0') {
                str += "1";
            }
        }
        ++index;
    }
    exprL.emplace_back(str);
    ++index;
    str = "";
    if (formula[index] > '9' || formula[index] < '0') {  // 表达式前为 “”
        str += "1";
    }
    while (index < formula.size()) {  // 右边
        if (formula[index] != '+') {
            str.push_back(formula[index]);
        }
        else {
            exprR.emplace_back(str);
            str = "";
            if (index + 1 < formula.size() && (formula[index + 1] > '9' || formula[index + 1] < '0')) {  // 表达式前为 “”
                str += "1";
            }
        }
        index++;
    }
    exprR.emplace_back(str);
}

// 找出每个元素 （累计个数， 记得 系数 * 项数）
void getNum(string str, int &index, string &elem, int &digits) {
    // 获取元素
    elem.push_back(str[index++]);
    while (str[index] <= 'z' && str[index] >= 'a') {
        elem.push_back(str[index++]);
    }


    // 获取项数
    while (str[index] >= '0' && str[index] <= '9') {
        digits = digits * 10 + (str[index++] - '0');
    }
    if (digits == 0) {  // 如果没有项数， 则默认为 1
        digits = 1;
    }
}


void calKuo(map<string, int> &elem, string &str, int indexL, int indexR, int coef) {
    // 找出每个元素 （累计个数， 记得 系数 * 项数）
    while (indexL <= indexR) {
        if (str[indexL] == '(') {  // 遇到括号
            int tmpIndex = indexL + 1;
            int lr = -1; // -1 代表 左括号 +1 代表右括号

            // 记录此次括号的边界
            while (lr != 0) {
                if (str[tmpIndex] == '(') {
                    lr -= 1;
                }
                else if (str[tmpIndex] == ')') {
                    lr += 1;
                }
                ++tmpIndex;
            }
            int tmpL = indexL + 1, tmpR = tmpIndex - 2;

            // 记录括号外项数
            int num = 0;
            while (tmpIndex < str.size() && str[tmpIndex] <= '9' && str[tmpIndex] >= '0') {
                num = num * 10 + (str[tmpIndex] - '0');
                ++tmpIndex;
            }
            if (num == 0) {
                num = 1;
            }

            // 处理括号内的内容
            calKuo(elem, str, tmpL, tmpR, coef * num);

            indexL = tmpIndex;  //
        }
        else {  // 没遇到括号, 记录元素的个数
            string e = "";
            int digits = 0;
            getNum(str, indexL, e, digits);
            elem[e] = elem[e] + coef * digits;  // 累计
        }
    }
}

// 获得等式左右的元素及个数
void getElem(vector<string> &expr, map<string, int> &elem) {
    for (string str: expr) {
        int index = 0;

        int coef = 0;
        // 获取表达式前系数
        while (str[index] >= '0' && str[index] <= '9') {
            coef = coef * 10 + (str[index++] - '0');
        }

        // 将整个表达式看成一个被括号包裹的表达式
        calKuo(elem, str, index, str.size() - 1, coef);
    }
}


int main() {
    ifstream cin("in.txt");

    int N;
    cin>>N;

    while (N-- > 0) {
        // 清理 全局数据中 上一个化学方程式的数据
        exprL.clear();
        exprR.clear();
        elemL.clear();
        elemR.clear();

        cin>>formula;

        int equaIndex = 0;  // 等号下标
        while (formula[equaIndex] != '=') {
            ++equaIndex;
        }

        getExpr();  // 获取化学方程式左右两边表达式

        // 对左右两边元素计数
        getElem(exprL, elemL);  // 左
        getElem(exprR, elemR);  // 右

        // 判断等式左右元素是否守恒
        if (elemL.size() != elemR.size()) {
            cout<<'N'<<endl;
        }
        else {
            bool flag = true;
            for (pair<string, int> p: elemL) {
                if (elemR[p.first] != p.second) {
                    cout<<'N'<<endl;
                    flag = false;
                    break;
                }
            }

            if (flag) {
                cout<<'Y'<<endl;
            }
        }
    }

    return 0;
}