首先进行一次括号匹配,把正确匹配的全部删去。
删去之后剩下的状态肯定是 L个连续右括号+R个连续左括号。
如果L是偶数,答案是L/2+R/2;
否则答案是 (L-1)/2+(R-1)/2+2;
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<algorithm>
using namespace std; char s[ + ];
char st[ + ];
int top; int main()
{
int T = ;
while (~scanf("%s", s))
{
int ans = ;
memset(st, , sizeof st);
top = -;
if (s[] == '-') break;
for (int i = ; s[i]; i++)
{
if (top == -) st[++top] = s[i];
else
{
if (st[top] == '{'&&s[i] == '}')
{
st[top] = ;
top--;
}
else st[++top] = s[i];
}
} int L = , R = ;
for (int i = ; st[i]; i++)
{
if (st[i] == '}') L++;
else R++;
}
if (L % == ) ans = L / + R / ;
else ans = (L - ) / + (R - ) / + ;
printf("%d. %d\n", T++, ans);
}
return ;
}