Bracket Sequence CodeForces - 223A

原题链接
考察:栈,模拟
  模拟栈匹配,不匹配的留入栈里.然后栈里都是不匹配的坐标,相邻之间都是匹配的.

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
char s[N],res[N];
int match[N],top,stk[N],sum[N];
int main()
{
	scanf("%s",s+1);
	int len = strlen(s+1);
	//这样栈存储的都是不配对的下标,这之间都是配对的. 
	for(int i=1;i<=len;i++)
	{
		if(s[i]=='[') sum[i]++;
		sum[i] += sum[i-1];
	}
	for(int i=1;i<=len;i++)
	{
		if(!top) stk[++top]  = i;
		else if(s[stk[top]]=='('&&s[i]==')') top--;
		else if(s[stk[top]]=='['&&s[i]==']') top--;
		else stk[++top] = i;
	}
	stk[++top] = len+1;
	int ans = -1,ansl,ansr;
	for(int i=1;i<=top;i++)
	{
		int l = stk[i-1],r = stk[i]-1;
		if(sum[r]-sum[l]>ans)
		{
			ans = sum[r]-sum[l];
			ansl = l+1,ansr = r;
		}
	}
	printf("%d\n",ans);
	for(int i=ansl;i<=ansr;i++)
		res[i-ansl] = s[i];
	res[ansr+1] = '/0';
	printf("%s\n",res);
	return 0;
}
上一篇:数据结构 (实验三 括号匹配)


下一篇:leetcode--括号有效性检查