我做的题解总是90分,我实在找不出来错在哪儿了,求大佬们救救,感激不尽。 CCF官网的题目贴不出来不好意思,是CCF计算机职业资格认证考试的201912-3。
这是我的题解:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <memory>
#include <vector>
#include <stack>
#include <unordered_map>
#include <utility>
#define MAX_LEN 1024
// H2+O2=H2O
// 2H2+O2=2H2O
// H2+Cl2=2NaCl
// H2+Cl2=2HCl
// CH4+2O2=CO2+2H2O
// CaCl2+2AgNO3=Ca(NO3)2+2AgCl
// 3Ba(OH)2+2H3PO4=6H2O+Ba3(PO4)2
// 3Ba(OH)2+2H3PO4=Ba3(PO4)2+6H2O
// 4Zn+10HNO3=4Zn(NO3)2+NH4NO3+3H2O
// 4Au+8NaCN+2H2O+O2=4Na(Au(CN)2)+4NaOH
// Cu+As=Cs+Au
using std::vector;
using std::stack;
using std::unordered_map;
using std::pair;
using std::hash;
enum TokenKind {
Element,
Number,
Plus,
EQ,
OpenParen,
CloseParen,
End
};
struct Token {
char str[50] = {0};
int tokenLen = 1;
TokenKind kind;
int cnt = 0;
bool operator==(const Token & token) const {
bool result = kind == token.kind && tokenLen == token.tokenLen && strncmp(str, token.str, tokenLen) == 0;
return result;
}
};
struct HashToken{
size_t operator()(const Token & token) const{
size_t h = 0;
const int mod = (1e9 + 7);
for (int idx = 0; idx < token.tokenLen; idx++) {
h = (hash<char>()(token.str[idx]) + h * 233) % mod;
}
return h;
}
};
struct Analyzer {
char source[MAX_LEN] = { 0 };
int sourceLen = 0;
int scanOffset = -1;
int parseOffset = -1;
int curEquationIndex = 0;
vector<Token> tokenStream;
vector<Token*> elements;
vector<int> numbers;
unordered_map<Token, int, HashToken> equations[2];
void scan() {
scanf("%s", source);
sourceLen = strlen(source);
tokensize();
}
void reset() {
memset(source, 0, MAX_LEN);
equations[0].clear();
equations[1].clear();
sourceLen = 0;
scanOffset = -1;
parseOffset = -1;
curEquationIndex = 0;
elements.resize(0);
numbers.resize(0);
tokenStream.resize(0);
}
void parse() {
parseExpr();
parseEQ();
parseExpr();
calcPrefixCoef();
}
inline void parseEQ() {
calcPrefixCoef();
curEquationIndex = 1;
}
void parseExpr() {
parseCoef();
parseFormula();
parseExprSub();
}
void parseExprSub() {
parseAdvance();
if (curToken().kind == Plus) {
parsePlus();
parseCoef();
parseFormula();
parseExprSub();
}
}
inline void parsePlus() {
calcPrefixCoef();
}
void parseCoef() {
parseAdvance();
Token& cur = curToken();
if (cur.kind == Number) {
int number = atoi(cur.str);
numbers.emplace_back(number);
} else {
numbers.emplace_back(1);
parseBack();
}
}
void parseFormula() {
parseTerm();
parseCoef();
calcSufixCoef();
parseFormulaSub();
}
void parseTerm() {
parseAdvance();
Token& cur = curToken();
if (curToken().kind == Element) {
elements.emplace_back(&cur);
} else {
parseOpen();
parseFormula();
parseClose();
}
}
void parseFormulaSub() {
parseAdvance();
if (curToken().kind == Element || curToken().kind == OpenParen) {
parseBack();
parseTerm();
parseCoef();
calcSufixCoef();
parseFormulaSub();
} else {
parseBack();
}
}
void tokensize() {
while(!atEnd()) {
char next = scanAdvance();
while(!isTerminal(next)) {
next = judge(next);
}
}
Token token;
token.kind = End;
tokenStream.emplace_back(token);
}
inline void parseOpen() {
elements.emplace_back(&curToken());
}
inline void parseClose() {
parseAdvance();
elements.emplace_back(&curToken());
}
void calcSufixCoef() {
Token* element = elements.back();
int number = numbers.back();
numbers.pop_back();
if (element->kind == CloseParen) {
elements.pop_back();
stack<Token*> store;
while (elements.back()->kind != OpenParen) {
element = elements.back();
elements.pop_back();
element->cnt *= number;
store.push(element);
}
elements.pop_back();
while(!store.empty()) {
elements.emplace_back(store.top());
store.pop();
}
} else {
element->cnt = number;
}
}
void calcPrefixCoef() {
int number = numbers.back();
numbers.pop_back();
while (!elements.empty()) {
Token* element = elements.back();
int cnt = element->cnt;
elements.pop_back();
equations[curEquationIndex][*element] += number * cnt;
}
}
char judge(char next) {
if (next >= '0' && next <= '9') {
return tokenizeNumber(next);
}
if (next >= 'A' && next <= 'Z') {
return tokenizeElement(next);
}
if (next == '+') {
return tokenizePlus(next);
}
if (next == '=') {
return tokenizeEQ(next);
}
if (next == '(') {
return tokenizeOpenParen(next);
}
if (next == ')') {
return tokenizeCloseParen(next);
}
return next;
}
char tokenizeOpenParen(char next) {
Token token;
token.str[0] = '(';
token.kind = OpenParen;
tokenStream.emplace_back(token);
next = scanAdvance();
return next;
}
char tokenizeCloseParen(char next) {
Token token;
token.str[0] = ')';
token.kind = CloseParen;
tokenStream.emplace_back(token);
next = scanAdvance();
return next;
}
char tokenizePlus(char next) {
Token token;
token.str[0] = '+';
token.kind = Plus;
tokenStream.emplace_back(token);
next = scanAdvance();
return next;
}
char tokenizeEQ(char next) {
Token token;
token.str[0] = '=';
token.kind = EQ;
tokenStream.emplace_back(token);
next = scanAdvance();
return next;
}
char tokenizeElement(char next) {
int start = scanOffset;
next = scanAdvance();
if ('a' <= next && next <= 'z') {
next = scanAdvance();
}
Token token;
token.tokenLen = scanOffset - start;
strncpy(token.str, source + start, scanOffset - start);
token.kind = Element;
tokenStream.emplace_back(token);
return next;
}
char tokenizeNumber(char next) {
int start = scanOffset;
while(true) {
next = scanAdvance();
if (next >= '0' && next <= '9') {
continue;
} else {
Token token;
token.tokenLen = scanOffset - start;
strncpy(token.str, source + start, token.tokenLen);
token.kind = Number;
tokenStream.emplace_back(token);
return next;
}
}
}
inline bool isTerminal(const char& chr) {
return chr == 0;
}
inline char scanAdvance() {
return source[++scanOffset];
}
inline void parseAdvance() {
++parseOffset;
}
inline void parseBack() {
--parseOffset;
}
inline Token& curToken() {
return tokenStream[parseOffset];
}
inline bool atEnd() {
return scanOffset >= sourceLen - 1;
}
};
int main() {
int n;
scanf("%d", &n);
Analyzer analyzer;
for (int idx = 0; idx < n; idx++) {
analyzer.scan();
analyzer.parse();
for(const pair<Token, int>& kv: analyzer.equations[0]){
if (analyzer.equations[1].find(kv.first) == analyzer.equations[1].end() ||
analyzer.equations[1][kv.first] != kv.second
) {
printf("N\n");
goto out;
}
}
printf("Y\n");
out:
analyzer.reset();
}
}