CSP化学方程式题解

题目描述

题目分析

本题主要考察栈的应用（也可以采用递归的方式，效率低），是一道与编译原理相关的题目。
首先我采用的是类似于哈希表的方法存储的元素位置及其数量，当然也可以用stl的map。
然后栈里存的是元素所在位置，进而在遇到相应符号（比如+、)、’\0’）时将对应区间里的数乘以相应的倍数。
最后便是得到各类符号时采取的相应操作，如下所示：

元素:存入链表，元素个数初始化为1

(:入栈，当前链表大小入栈

):后面若跟有数，则相应区间内的元素个数乘以此数

=:转到另一面；若前一化学式前有系数，则需要将对应区间内元素乘以此数

数:若之前符号为+、=或在起始位置，则为化学式系数；反之则将之前的元素乘以此数

+:若前一化学式前有系数，则需要将对应区间内元素乘以此数

C++源码

#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<stack> using namespace std;enum symbol{nul,sym,number,lp,rp,add,equ}; typedef enum symbol symbol; typedef vector< pair<int,int> > vec; const int MAX=1e3+4;char c[MAX]; int a[2][27*26]={0}; bool ce=0; int ind,num;symbol getsym(int &ind) {symbol symtmp;if(c[ind]=='\0')return nul;if(c[ind]=='+')symtmp=add,ind++;else if(c[ind]=='(')symtmp=lp,ind++;else if(c[ind]==')')symtmp=rp,ind++;else if(c[ind]=='=')symtmp=equ,ind++;else if(c[ind]>='A'&&c[ind]<='Z'){symtmp=sym;num=c[ind++]-'A';if(c[ind]>='a'&&c[ind]<='z')num=(num+1)*26+c[ind++]-'a';}else if(c[ind]>='0'&&c[ind]<='9'){symtmp=number;num=0;while(c[ind]>='0'&&c[ind]<='9'){num*=10;num+=c[ind++]-'0';}}return symtmp; }bool solve() {int now=0,shu=1;bool xuan=0,rpy=1;stack<int> bracket;vec v[2];symbol lsym=add;symbol Sym=getsym(ind);while(Sym){switch(Sym){case sym:v[ce].push_back(make_pair(num,1));break;case lp:bracket.push(v[ce].size());break;case rp:Sym=getsym(ind);if(Sym==number){for(int i=bracket.top();i<v[ce].size();i++)v[ce][i].second*=num;}else{lsym=rp;rpy=0;}bracket.pop();break;case equ:if(xuan){for(int i=now;i<v[ce].size();i++)v[ce][i].second*=shu;xuan=0;}ce=!ce;Sym=add;break;case number:if(lsym!=add)v[ce][v[ce].size()-1].second*=num;else{shu=num;now=v[ce].size();xuan=1;}break;case add:if(xuan){for(int i=now;i<v[ce].size();i++)v[ce][i].second*=shu;xuan=0;}break;}if(rpy){lsym=Sym;Sym=getsym(ind);}else{rpy=1;}}if(xuan){for(int i=now;i<v[ce].size();i++)v[ce][i].second*=shu;xuan=0;}for(int i=0;i<2;i++)for(int j=0;j<v[i].size();j++){a[i][v[i][j].first]+=v[i][j].second;}for(int i=0;i<27*26;i++)if(a[0][i]!=a[1][i]){return false;}return true; }int main() {int e;scanf("%d",&e);while(e--){ce=0;ind=0;memset(a,0,sizeof(a));scanf("%s",c);bool jud=solve();if(jud)puts("Y");elseputs("N");}return 0; }

不足之处敬请指正！

总结

以上是生活随笔为你收集整理的CSP化学方程式题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。