655
九度题目1342：寻找最长合法括号序列II
题目1342：寻找最长合法括号序列II（25分）
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：732
解决：294
题目描述：
假如给你一个由’(‘和’)’组成的一个随机的括号序列，当然，这个括号序列肯定不能保证是左右括号匹配的，所以给你的任务便是去掉其中的一些括号，使得剩下的括号序列能够左右括号匹配且长度最长，即最长的合法括号序列。
输入：
测试数据包括多个，每个测试数据只有一行，即一个随机的括号序列，该括号序列的长度保证不超过106。
输出：
对于每个测试案例，输出一个整数，表示最后剩下的最长合法括号序列长度。
样例输入：
(())()
(()
样例输出：
6
2
思路：以前做过的水题...用栈模拟即可，相同的出栈，不相同继续进栈....
AC代码：
#include<stdio.h>
#include<string.h>
char s[1000010];
char stack[1000010];
int main()
{
int i,j,n,m,sum;
while(gets(s))
{
n=strlen(s);m=0;
sum=0;
for(i=0;i<n;i++)
{
stack[m++]=s[i];
if(m-2>=0)
{
if(stack[m-2]=='('&&stack[m-1]==')')
{
sum+=2;
m-=2;
}
}
}
printf("%d\n",sum);
}
return 0;
}
最后更新：2017-04-03 12:56:29