一道贪心题。
贪心策略是除了最后一个 # 其他的都变成 \(1\) 个 )，这样前面的 ) 就尽可能的少，最后的 # 变成的 ) 数量加上前面的 ) 数量等于 ( 的数量，这样在最后所有的括号都会匹配。最后检查一下合不合法。
Code
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
string s, tmp;
int sum1, sum2, sum3, sum4, cnt, last; // sum1 和 sum2 用来判断最后一个 # 要变成多少个 )
signed main() {
ios :: sync_with_stdio(0);
cin >> s;
if (s.size() == 1) {
cout << -1;
return 0;
} // 如果只有 1 个字符必然无解
for (int i = s.size() - 1; i >= 0; i--) {
if (s[i] == '#') {
cnt++;
last = i;
break;
}
}
for (int i = 0; i < s.size(); i++) {
if (i == last) continue; // 最后一个 # 先不处理
if (s[i] == '(') sum1++;
else if (s[i] == ')') sum2++;
else {
cnt++;
s[i] = ')';
sum2++;
}
}
if (sum1 == sum2) {
cout << -1;
return 0;
} // 必然无解，因为 # 必须变成 1 个以上的 )
for (int i = 1; i <= sum1 - sum2; i++) tmp += ')';
s.replace(last, 1, tmp);
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') sum3++;
if (s[i] == ')') sum4++;
if (sum4 > sum3) {
cout << "-1";
return 0;
}
} // 判断是否合法
for (int i = 1; i <= cnt; i++) {
if (i == cnt) cout << sum1 - sum2;
else cout << 1 << "\n";
} // 贪心策略
return 0;
}