九度题目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;
}