我们可以扫一遍,扫描的过程中遇到左括号则保留,遇到右括号能匹配的尽量匹配,如果没有左括号了,我们先把右括号变成左括号。
最后剩余的左括号有一般要变成右括号。
#include <bits/stdc++.h>
using namespace std;
int ans, sum, i;
string s;
int main() {
cin >> s;
int lens = s.size(); //这样快
for (; i < lens; ++i) {
if (s[i] == '(')
sum++; //模拟栈
else {
if (sum)
--sum; //抵消一个左括号
else
++ans, ++sum; //变成了左括号
}
}
ans += sum >> 1; //剩下的都是左括号的情况 ,要有一半变成右括号
cout << ans;
return 0;
}