CCF191203化学方程式满分
程序员文章站
2022-05-12 15:01:50
...
基本思路是：
1.根据‘=’号提取左右两侧。
2.根据‘+’提取各个部分
3.将各个部分为系数和化学式
4.然后再使用如下状态图解析化学式，如果有括号包裹的部分，将其整体递归一次。
这个题目就化学式的分析部分有点麻烦，这部分的解析画了一个简单的状态图，如下：
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
typedef struct Formula
{
string name;
int number;
}Formula;
typedef struct Item
{
int coefficient;
vector<Formula> formula;
}Item;
class Equeal
{
public:
vector<Item> left;
vector<Item> right;
void prase(string str);
void split(string& src, char ch,string& des_s, string& des_e);
void add_item(vector<Item>& vec, string str);
void prase_fomula(Item& item, string fomula, int multiple);
void add_element(Item& item, string str, int multiple);
void calculate(vector<Item>& items, vector<Formula>& result);
int compare(vector<Formula>& left_formuals, vector<Formula>& right_formuals);
};
void Equeal::prase(string str)
{
string left_str , right_str;
string item,leave;
split(str, '=', left_str, right_str);
do
{
split(left_str, '+', item, leave);
add_item(left, item);
left_str = leave;
}while(!left_str.empty());
do
{
split(right_str, '+', item, leave);
add_item(right, item);
right_str = leave;
}while(!right_str.empty());
}
void Equeal::split(string& src, char ch,string& des_s, string& des_e)
{
int pos;
if((pos = src.find(ch)) != src.npos)
{
des_s = src.substr(0, pos);
des_e = src.substr(pos + 1);
}
else
{
des_s = src;
des_e.erase();
}
}
void Equeal::add_item(vector<Item>& vec, string str)
{
string temp_str, formula_str;
std::stringstream ss;
int i, coefficient;
Item item;
for(i=0; i<str.size(); i++)
{
if(str[i] < '0' || str[i] > '9')
{
break;
}
}
temp_str = str.substr(0, i);
formula_str = str.substr(i);
if(temp_str.empty())
{
coefficient = 1;
}
else
{
ss<<temp_str;
ss>>coefficient;
}
item.coefficient = coefficient;
prase_fomula(item, formula_str, 1);
vec.push_back(item);
}
void Equeal::prase_fomula(Item& item, string fomula, int multiple)
{
int i;
int state = 0, bracket_count = 0;
string element_str;
for(i = 0; i<fomula.size(); i++)
{
switch(state)
{
case 0:
if(fomula[i] >= 'A' && fomula[i] <= 'Z')
{
state = 2;
element_str+=fomula[i];
}
else if(fomula[i] == '(')
{
element_str+=fomula[i];
state = 1;
}
else
{
state = 0;
element_str.erase();
}
break;
case 1:
if(fomula[i] == ')')
{
element_str+=fomula[i];
if(bracket_count >0)
{
bracket_count--;
}
else
{
state = 4;
}
}
else if(fomula[i] == '(')
{
element_str+=fomula[i];
bracket_count++;
}
else
{
state = 1;
element_str+=fomula[i];
}
break;
case 2:
if(fomula[i] >= 'a' && fomula[i] <= 'z')
{
state = 2;
element_str+=fomula[i];
}
else if((fomula[i] >= 'A' && fomula[i] <= 'Z') || fomula[i] == '(')
{
add_element(item, element_str, multiple);
element_str.erase();
i--;
state = 0;
}
else if(fomula[i] >= '0' && fomula[i] <= '9')
{
state = 3;
element_str+=' ';
element_str+=fomula[i];
}
else
{
state = 0;
element_str.erase();
}
break;
case 3:
if(fomula[i] >= '0' && fomula[i] <= '9')
{
state = 3;
element_str+=fomula[i];
}
else
{
add_element(item, element_str, multiple);
element_str.erase();
i--;
state = 0;
}
break;
case 4:
if(fomula[i] >= '0' && fomula[i] <= '9')
{
state = 3;
element_str+=' ';
element_str+=fomula[i];
}
else
{
add_element(item, element_str, multiple);
element_str.erase();
i--;
state = 0;
}
break;
case 5:
break;
case 6:
break;
case 7:
break;
default:
break;
}
}
if(state != 0)
{
add_element(item, element_str, multiple);
}
}
void Equeal::add_element(Item& item, string str, int multiple)
{
string name,num_str;
int num;
Formula formula;
if(str[0] == '(')
{
split(str, ' ', name, num_str);
if(num_str.empty())
{
num = 1;
}
else
{
stringstream ss;
ss<<num_str;
ss>>num;
}
num*=multiple;
name.erase(name.end() - 1);
name.erase(0, 1);
prase_fomula(item, name, num);
}
else
{
split(str, ' ', name, num_str);
if(num_str.empty())
{
num = 1;
}
else
{
stringstream ss;
ss<<num_str;
ss>>num;
}
num*=multiple;
int i;
for(i=0; i< item.formula.size(); i++)
{
if(item.formula[i].name == name)
{
break;
}
}
if(i >= item.formula.size())
{
formula.name = name;
formula.number = num;
item.formula.push_back(formula);
}
else
{
item.formula[i].number += num;
}
}
}
void Equeal::calculate(vector<Item>& items, vector<Formula>& result)
{
Formula formula;
for(int i=0; i<items.size();i++)
{
for(int j=0;j<items[i].formula.size();j++)
{
int k;
for(k=0; k<result.size(); k++)
{
if(result[k].name == items[i].formula[j].name)
{
break;
}
}
if(k>=result.size())
{
formula.name = items[i].formula[j].name;
formula.number = items[i].formula[j].number * items[i].coefficient;
result.push_back(formula);
}
else
{
result[k].number += items[i].formula[j].number * items[i].coefficient;
}
}
}
}
int Equeal::compare(vector<Formula>& left_formuals, vector<Formula>& right_formuals)
{
for(int i=0; i<left_formuals.size();i++)
{
int j;
for(j=0; j<right_formuals.size();j++)
{
if(left_formuals[i].name == right_formuals[j].name)
{
if(left_formuals[i].number != right_formuals[j].number)
{
return 0;
}
break;
}
}
if(j >= right_formuals.size())
{
return 0;
}
}
return 1;
}
vector<Formula> left_formuals;
vector<Formula> right_formuals;
Equeal equeal;
int main(void)
{
int total;
string str;
cin>>total;
for(unsigned int i=0; i<total; i++)
{
cin>>str;
equeal.prase(str);
equeal.calculate(equeal.left, left_formuals);
equeal.calculate(equeal.right, right_formuals);
if(equeal.compare(left_formuals, right_formuals) && equeal.compare(right_formuals, left_formuals) && equeal.right.size()>0)
{
cout<<'Y'<<endl;
}
else
{
cout<<'N'<<endl;
}
left_formuals.clear();
right_formuals.clear();
equeal.left.clear();
equeal.right.clear();
}
return 0;
}