请问我的代码哪里错了？
原题链接：63.等价表达式
2025-08-01 20:54:17
发布于：浙江
65阅读
0回复
0点赞
代码：
#include<bits/stdc++.h>
using namespace std;
string s;
int p;
struct V { map<int, long long> m; };
V A(const V& a, const V& b, bool sub = false) {
V r = a;
for (auto& kv : b.m) {
int e = kv.first; long long c = kv.second;
if (sub) c = -c;
r.m[e] += c;
if (r.m[e] == 0) r.m.erase(e);
}
return r;
}
V M(const V& a, const V& b) {
V r;
for (auto& ka : a.m) for (auto& kb : b.m) {
r.m[ka.first + kb.first] += ka.second * kb.second;
}
vector<int> d;
for (auto& kv : r.m) if (kv.second == 0) d.push_back(kv.first);
for (int e : d) r.m.erase(e);
return r;
}
V W(V a, int e) {
V r; r.m[0] = 1;
while (e) { if (e & 1) r = M(r, a); a = M(a, a); e >>= 1; }
return r;
}
V F();
V T() {
V v = F();
while (p < s.size() && s[p] == '*') { p++; V v2 = F(); v = M(v, v2); }
return v;
}
V E() {
V v = T();
while (p < s.size() && (s[p] == '+' || s[p] == '-')) {
char c = s[p++];
V v2 = T();
v = (c == '+' ? A(v, v2) : A(v, v2, true));
}
return v;
}
V F() {
V v;
if (s[p] == '(') { p++; v = E(); p++; }
else if (isdigit(s[p])) {
long long n = 0;
while (p < s.size() && isdigit(s[p])) { n = n * 10 + (s[p++] - '0'); }
v.m[0] = n;
} else { v.m[1] = 1; p++; }
if (p < s.size() && s[p] == '^') {
p++; int e = 0;
while (p < s.size() && isdigit(s[p])) e = e * 10 + (s[p++] - '0');
v = W(v, e);
}
return v;
}
V G(string t) {
s = ""; for (char c : t) if (c != ' ') s.push_back(c);
p = 0; return E();
}
int main() {
string b; getline(cin, b);
V bp = G(b);
int n; cin >> n; string tmp;
getline(cin, tmp);
vector<char> ans;
for (int i = 0; i < n; i++) {
string o; getline(cin, o);
V op = G(o);
if (op.m == bp.m) ans.push_back('A' + i);
}
sort(ans.begin(), ans.end());
for (char c : ans) cout << c;
}
我的思路：
先将表达式中的空格去掉，然后使用递归下降的方法解析表达式，生成单变量多项式的系数映射。对于加减乘幂运算，分别实现多项式的加法、减法、乘法和幂运算（将一个多项式自乘多次）。将题干表达式与每个选项表达式都解析成多项式后，比较它们的系数映射是否相同。若相同则视为等价。最后按字母顺序输出等价选项的标号。
全部评论 3
#include<bits/stdc++.h> using namespace std; string s; int p; struct V { map<int, long long> m; }; V A(const V& a, const V& b, bool sub = false) { V r = a; for (auto& kv : b.m) { int e = kv.first; long long c = kv.second; if (sub) c = -c; r.m[e] += c; if (r.m[e] == 0) r.m.erase(e); } return r; } V M(const V& a, const V& b) { V r; for (auto& ka : a.m) for (auto& kb : b.m) { r.m[ka.first + kb.first] += ka.second * kb.second; } vector<int> d; for (auto& kv : r.m) if (kv.second == 0) d.push_back(kv.first); for (int e : d) r.m.erase(e); return r; } V W(V a, int e) { V r; r.m[0] = 1; while (e) { if (e & 1) r = M(r, a); a = M(a, a); e >>= 1; } return r; } V F(); V T() { V v = F(); while (p < s.size() && s[p] == '*') { p++; V v2 = F(); v = M(v, v2); } return v; } V E() { V v = T(); while (p < s.size() && (s[p] == '+' || s[p] == '-')) { char c = s[p++]; V v2 = T(); v = (c == '+' ? A(v, v2) : A(v, v2, true)); } return v; } V F() { V v; if (s[p] == '(') { p++; v = E(); p++; } else if (isdigit(s[p])) { long long n = 0; while (p < s.size() && isdigit(s[p])) { n = n * 10 + (s[p++] - '0'); } v.m[0] = n; } else { v.m[1] = 1; p++; } if (p < s.size() && s[p] == '^') { p++; int e = 0; while (p < s.size() && isdigit(s[p])) e = e * 10 + (s[p++] - '0'); v = W(v, e); } return v; } V G(string t) { s = ""; for (char c : t) if (c != ' ') s.push_back(c); p = 0; return E(); } int main() { string b; getline(cin, b); V bp = G(b); int n; cin >> n; string tmp; getline(cin, tmp); vector<char> ans; for (int i = 0; i < n; i++) { string o; getline(cin, o); V op = G(o); if (op.m == bp.m) ans.push_back('A' + i); } sort(ans.begin(), ans.end()); for (char c : ans) cout << c; }1周前 来自 广东
0
有帮助，赞一个