PTA Easy chemistry 化学方程式等价判定 string 状态机
7-5 Easy chemistry
In this question, you need to write a simple program to determine if the given chemical equation is balanced. Balanced means that the amount of elements on both sides of the “=” sign is the same.
H2O+CO2=H2CO3
We guarantees that each chemical equation satisfies the basic rules.
If you don’t know the basic rules of chemical equation writing, you can refer to the following conditions:
- The chemical equation contains exactly one “=” sign.
- For every chemical element, the first letter of each element is uppercase, and the rest of the letters are lowercase.
- The number at the end of the element represents the amount of this element needed, If there is no number, it means only one element is needed.
- Every chemical object may contain several chemical elements like NaCl.
The number at the beginning of every chemical object represents the number of this object, If there is no number, it means only one object is needed. - Every chemical object will be connected by “+” sign.
- Chemical reaction is considered to rearrange the atoms after they are broken up
Input
The first line contains a single integer T(1≤T≤100), indicating the number of test cases.
In the next T lines, each line contains a string S(1≤∣S∣≤100), representing a Chemical equation.
It is guaranteed that S only contains uppercase letters, lowercase letters, “=” sign and “+” sign, the sum of the amount of all elements will not exceed 2147483647.
Output
If the given chemical equation is balanced, please output “Easy!”, otherwise output “Hard!” (Without quotes).
Sample Input
3
H2O+CO2=H2CO3
2NaHCO3=Na2CO3+H2O+CO2
3Cu+8HNO3=3CuNO3+2NO+4H2O
Sample Output
Easy!
Easy!
Hard!
作者
tt
单位
浙江大学城市学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
题意 : 给定一个化学方程式字符串,判断左右两边原子个数是否相等
- 字符串有且仅有一个等于号 "="
- 等号两边是 "物质A+物质B+...物质N"
- 物质i由大小写字母和数字组成,形如 2NaCO3
- 对于 2NaCO3,发现个数为: Na=2∗1,C=2∗1,O=2∗3
- 多组样例
这题看似别扭,但其实很简单,
2NaCO3可以看成是 [numL][Name1][numR1][Name2][numR2]....[NameN][numRN]
用两个map统计等号左右两边的原子个数,最后比较两个map是否全等
把状态机画出来,再对着状态机写代码即可 1A (调代码调了一上午)
状态图如下:
#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)
using namespace std;
#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif
#ifndef debug
namespace FIO {
template <typename T>
void read(T& x) {
int f = 1; x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{ if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9')
{ x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
};
using namespace FIO;
#endif
int n, m, Q, K;
char buf[MAXN];
map<string, int> mp1, mp2; //map1代表等号左边的原子个数表
//map2代表等号右边
#define ch (buf[i])
#define Big(x) (x>='A' && x<='Z')
#define Small(x) (x>='a' && x<='z')
#define NUML (numL ? numL : 1)
#define NUMR (numR ? numR : 1)
#define Num(x) (x>='0' && x<='9')
#define mp (*ptr)
//to0是跳回状态0
#define to0 {name.clear();\ status = numL = numR = 0;}
void slove() {
map<string, int>* ptr = &mp1; //初始状态为左边的map
int status = 0, numL = 0, numR = 0;
string name = "", ptag = "map1 : ";
//状态 : 0-初始状态, 1-读物质名字name,
// 2-读原子个数numR, 3-读物质个数numL
for(int i=0; buf[i]; ) { //注意这里不要i++
if(status == 0) { //起始状态
if(Big(ch)) { //遇到大写 转化为1状态,读name
status = 1;
} else if(Num(ch)) { //遇到数字 转化为3状态, 读物质个数numL
status = 3;
}
} else if(status == 1) { //1状态是读取名字
if(Big(ch)) {
if(!name.empty()) { //更新上一个名字到map
mp[name] += (NUML * NUMR);
name.clear();
}
name.push_back(ch); //加入
i ++;
} else if(Num(ch)) { //遇到数字,说明要去读numR,原子个数
status = 2;
} else if(Small(ch)) { //小写也是上一个name的一部分
name.push_back(ch);
i ++;
} else if(ch == '=') { //等号要切换map并回到初始状态
mp[name] += (NUML * NUMR); //当然要先更新上一个name
ptr = &mp2; //切换到右边的map
to0;
i ++;
} else if(ch == '+') { //遇到+要读下一个"2NaCO3"
mp[name] += (NUML * NUMR);
to0;
i ++;
}
} else if(status == 2) { //状态2要读原子个数numR
if(Big(ch)) { //遇到大写,说明当前原子的个数numR读完了,跳回1继续读name
mp[name] += (NUML * NUMR); //更新0
name.clear();
numR = 0;
status = 1;
} else if(Num(ch)) {
numR = numR * 10 + (ch - '0');
i ++;
} else if(Small(ch)) {
} else if(ch == '=') { //等号同1里的等号
mp[name] += (NUML * NUMR);
ptr = &mp2;
to0;
i ++;
} else if(ch == '+') { //加号同1里的加号
mp[name] += (NUML * NUMR);
to0;
i ++;
}
} else if(status == 3) { //状态3是读总物质个数numL
if(Big(ch)) { //遇到大写说明当前numL读完了,跳去读name
mp[name] += (NUML * NUMR);
numR = 0;
name.clear();
status = 1; //改成status = 0也可
} else if(Num(ch)) {
numL = numL * 10 + (ch - '0');
i ++;
} else if(Small(ch)) {
} else if(ch == '=') {
} else if(ch == '+') {
}
}
}
#if 0
mp1.erase(""), mp2.erase("");
for(auto it : mp1)
cout << "[" << it.first << "," << it.second << "], ";
cout << endl;
for(auto it : mp2)
cout << "[" << it.first << "," << it.second << "], ";
cout << endl;
#else
mp1.erase(""), mp2.erase(""); //删掉两个map的空串
if(mp1.size() != mp2.size()) //两边原子种类数量不同,就no
printf("Hard!\n");
else { //比较每个原子个数是否相同
bool ok = true;
for(auto it=mp1.begin(), it2=mp2.begin(); it!=mp1.end(); it++, it2++) {
if(it->first!=it2->first || it->second!=it2->second)
ok = false;
}
printf("%s\n", !ok ? "Hard!" : "Easy!");
}
#endif
}
int main() {
#ifdef debug
freopen("test", "r", stdin);
clock_t stime = clock();
#endif
scanf("%d ", &Q);
while(Q--) {
mp1.clear(), mp2.clear();
scanf("%s ", buf);
n = strlen(buf);
buf[n] = '+'; //字符串屁股后加入一个+,就不用单独处理字符串末尾了
buf[n+1] = 0;
slove();
}
#ifdef debug
clock_t etime = clock();
printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
return 0;
}
查看22道真题和解析
