CCF小白刷题之路---201912-3 化学方程式（C/C++ 100分）

一、题目描述





二、题目讲解
下面我们针对每个测试点进行讲解，应该怎么处理各种情况

（1）只包含大写字母和等号

这一步我们只需要统计好每个大写字母的个数即可，但是这里要注意可能会出现重复的大写字母，例如：AAAA=AAAB

（2）加入小写字母和加号

这一步我们要针对每个化学式进行处理，同时我们要注意有的元素是同时包含了大小写字母，在处理的时候要把这些合在一起构成一个元素。

（3）加入数字

这一步就要判断数字的情况了，数字如果位于化学式的前面，则代表这个化学式的系数，意味着里面每一个元素都要乘以这个系数；如果数字位于这个元素的后面，则只需要这个元素乘以这个数字就行；如果数字位于一对括号的后面，则需要把这个括号里面的所有元素都乘以这个系数。

（4）加入括号

这一步我们可以进行倒序遍历，去挨个计算每一个括号内的元素，这里要注意的是括号嵌套的情况，具体的实现方法在下面的代码都有详细注释，方便大家理解。
三、代码实现

#include<iostream>
#include<sstream>
#include<vector>
#include<ctype.h>
#include<map>
using namespace std;
//结构体，便于存储每一个化学式中的每一个元素
struct Elem{
    string name;//元素名称
    int num;//元素个数
    //构造函数，便于直接赋值，注意最后没有分号
    Elem(string n1,int n2):name(n1),num(n2){}
};
//便于获取系数和化学式下标
int number(string &str,int &i)
{
    int num = 0;
    while(isdigit(str[i]))
    {
        num = num * 10 + str[i] - '0';
        i++;
    }
    return num;
}
//分别处理化学方程式等号两边
void calculate(string &str,map<string,int> &mp)
{
    stringstream ss(str);
    string item;
    //以加号为标志分割方程式，处理每一个化学式
    while(getline(ss,item,'+'))
    {
        int factor = 1;//化学式初始系数，默认为1
        int i = 0;
        vector<Elem> elem;
        //如果化学式前面的系数不为0，则进行计算，赋值给factor
        if(isdigit(item[i])) factor = number(item,i);
        //开始处理每个化学式
        while(i<item.size())
        {
            if(isdigit(item[i]))
            {
                int num = number(item,i);
                //开始处理一对括号
                if(elem[elem.size()-1].name==")")
                {
                    int j = elem.size() - 1;
                    //把倒数第一个有括号赋值为*，防止括号嵌套时混淆
                    elem[j].name = "*";
                    //元素倒序处理，当出现第一个左括号时，配对成功
                    while(elem[--j].name != "(")
                    {
                        //给这对括号里面的每个元素赋值个数
                        elem[j].num *= num;
                    }
                    //把这个左括号也赋值为*，代表这对括号处理完毕
                    elem[j].name = "*";
                }
                else elem[elem.size()-1].num *= num;
            }
            //如果是（的话，加入elem，num赋值为0
            else if(item[i]=='(')
            {
                elem.push_back(Elem("(",0));
                i++;
            }
            //如果是）的话，加入elem，num赋值为0
            else if(item[i]==')')
            {
                elem.push_back(Elem(")",0));
                //这里可能会出现）是最后一个字符，所以我们要添加一个字符串“1，以便进行下标计算”
                if(i+1 == item.size() || !isdigit(item[i+1]))
                {
                    item.insert(i+1,"1");
                }
                i++;
            }
            //如果是大写字母
            else if(isupper(item[i]))
            {
                string name = "";
                name += item[i];
                i++;
                //如果大写字母后面紧跟小写字母，凑个一个元素
                if(islower(item[i]))
                {
                    name += item[i];
                    i++;
                }
                //把元素加入elem中
                elem.push_back(Elem(name,1));
            }
        }
        //把这个化学式内的元素乘以化学式前的系数
        for(int j=0;j<elem.size();j++)
        {
            //忽略*，因为*代指的是之前处理时的括号
            if(elem[j].name == "*") continue;
            mp[elem[j].name] += elem[j].num * factor;
        }
    }
}
//左右两边进行比较
bool judge(map<string,int> &mp1,map<string,int> &mp2)
{
    if(mp1.size() != mp2.size()) return false;
    //挨个比较每个元素的个数，个数一致则化学方程式成立
    for(map<string,int>::iterator it = mp1.begin();it!=mp1.end();it++)
    {
        if(mp2[it->first]!=it->second) return false;
    }
    return true;
}

int main()
{
    int n;
    cin>>n;
    string str,str_left,str_right;
    while(n--)
    {
        cin>>str;
        stringstream ss(str);
        getline(ss,str_left,'=');//赋值化学方程式等号左边
        getline(ss,str_right);//赋值化学方程式等号右边
        map<string,int> left,right;
        calculate(str_left,left);//处理化学方程式的左半部分
        calculate(str_right,right);//处理化学方程式的右半部分
        if(judge(left,right)) cout<<"Y"<<endl;
        else cout<<"N"<<endl;
    }
    return 0;
}