用到编译原理的递归下降法,类似写语法分析器,
不过不需要生成AST,只需要统计元素个数即可。

代码长度 3.673KB
编程语言 C0X
评测结果 正确
得分 100
时间使用 156ms
空间使用 632.0KB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <bits/stdc++.h>
using namespace std;
using element = string;

map<element, int> &operator+=(map<element, int> &a, const map<element, int> &b) {
for (const auto &p : b) {
a[p.first] += p.second;
}
return a;
}
map<element, int> operator*(int coef, const map<element, int> &b) {
map<element, int> r;
for (const auto &p : b) {
r[p.first] = p.second * coef;
}
return r;
}

map<element, int> parseTerm(const string &str);
map<element, int> parseFormula(const string &str);
size_t parseCOEF(const string &str, size_t pos, int &coef);

map<element, int> parseTerm(const string &str) {
map<element, int> r;
if (str.front() == '(') {
return parseFormula(str.substr(1, str.size() - 2));
}
++r[str];
return r;
}

map<element, int> parseFormula(const string &str) {
map<element, int> r;
size_t i = 0;
int level = 0;
string term;
while (i < str.size()) {
if (level > 0) {
if (str[i] == '(') {
++level;
} else if (str[i] == ')') {
--level;
}
term += str[i];
++i;
} else {

// 在level=0,只有小写才代表上一项没有结束。
if (islower(str[i])) {
term += str[i];
++i;
} else {
// level=0,非小写一律代表上一个符号已经结束。
// 此处处理
if (!term.empty()) {
int co = 0;
i += parseCOEF(str, i, co);
r += co * parseTerm(term);
term.clear();
}
if (str[i] == '(') {
++level;
term = str[i];
++i;
} else if (isupper(str[i])) {
term = str[i];
++i;
}
}

}

}
// 不要忘了最后可能还有一项,循环中可能没有处理。
if (!term.empty()) {
int co = 0;
parseCOEF(str, i, co);
r += co * parseTerm(term);
term.clear();
}
return r;
}

// 返回coef长度
size_t parseCOEF(const string &str, size_t pos, int &coef) {
if (pos >= str.size()) {
coef = 1;
return 0;
}
coef = 0;
size_t i = pos;
if (isdigit(str[i])) {
coef = str[i] - '0';
++i;
while (i < str.size() && isdigit(str[i])) {
coef = coef * 10 + (str[i] - '0');
++i;
}
} else {
coef = 1;
}
return i - pos;
}

map<element, int> parseExpr(const string &str) {
map<element, int> r;
size_t i = 0, ni = str.find('+');
if (ni == string::npos) {
int coef, coeflen;
coeflen = parseCOEF(str, 0, coef);
r += coef * parseFormula(str.substr(coeflen));
} else
while (i != string::npos) {
int coef, coeflen;
coeflen = parseCOEF(str, i, coef);
if (ni != string::npos) {
r += coef * parseFormula(str.substr(i + coeflen, ni - (i + coeflen)));
} else {
r += coef * parseFormula(str.substr(i + coeflen));
}
if (ni != string::npos) {
i = ni + 1;
ni = str.find('+', i);
} else {
i = ni;
}
}
return r;
}

bool legalEquation(const string &str) {
size_t i = str.find('=');
if (i == string::npos) return false;
return parseExpr(str.substr(0, i)) == parseExpr(str.substr(i + 1, str.size()));
}

int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
cin.get();
while (n--) {
string e;
getline(cin, e);
cout << (legalEquation(e) ? "Y" : "N") << endl;
}
}