CSP化学方程式

unordered_map(基于哈希表的map)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#define x first
#define y second
​
using namespace std;
​
typedef unordered_map<string,int> MPSI;
​
//Na(Au(CN)2)
MPSI dfs(string&str,int& u){
    MPSI res;
    while(u < str.size()){
        if(str[u]=='('){
            u++;//过滤掉 '('
            MPSI t=dfs(str,u);
            u++;//过滤掉)
            //判断后面的系数
            int cnt=1,k=u;
            while(k<str.size()&&isdigit(str[k])) k++;
            if(k>u){
                cnt=stoi(str.substr(u,k-u));
                u=k;
            }
            for(auto c:t){
                res[c.x]+=c.y*cnt;
            }
        }
        else if(str[u]==')') break;
        else{
            int k=u+1;
            //跳过小写字母
            while(k<str.size()&&str[k]>='a'&&str[k]<='z') k++;
            string key=str.sbustr(u,k-u);//分解到该元素 如Na
            //u未下次开始的位置
            u=k;
            //看该元素的下标如Na2
            int cnt=1;
            while(k<str.size()&&isdigit(str[k])) k++;
            //如果有下标元素
            if(k>u){
                cnt=stoi(str.substr(u,k-u));
                u=k;
            }
            res[key]+=cnt;
        }
    }
    return res;
}
​
MPSI work(string str)
{
    MPSI res;
    //双指针找出每个物质
    for(int i=0;i<str.size();i++){
        int j=i+1;
        while(j<str.size()&&str[j]!='+') j++;
        //取得+号之前的这个元素
        string item=str.substr(i,j-i);
        //j指向的是+ 让i指向后一个物质的第一个字母
        i=j+1;
        //该元素之前的系数
        int cnt=1,k=0;
        while(k<item.size()&&isdigit(item[k])) k++;
        if(k) cnt=stoi(item.substr(0,k));
        //这个物质里面可能有好几个括号,递归遍历这个物质 
        //k 代表这个物质的起始字母
        MPSI t=dfs(item,k);
        for(auto c:t){
            res[c.x]+=c.y*cnt;
        }
        return res;
    } 
}
​
int main()
{
    int n;
    cin>>n;
    while(n--){
        string str;
        cin>>str;
        int k=str.find('=');
        auto left =work(str.substr(0,k)),right=work(str.substr(k+1));
        if(left==right) cout<<"Y"<<endl;
        else cout<<"N"<<endl;
    }
    return 0;
}