九度题目1342:寻找最长合法括号序列II-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: