鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

poj 3991(括号匹配)

来源:互联网 作者:佚名 时间:2015-09-25 05:40
#includecstdio#includecmath#includestack#includecstring#includestring#includeiostream#includealgorithmusing namespace std;int main(){int n,l,i,j,k,cs=1;char a1[3000];int a[3000];while(gets(a1)){if(a1[0]=='-')break;l=strlen(a1);for(i=0;il;i
#include<cstdio>
#include<cmath>
#include<stack>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n,l,i,j,k,cs=1;
	char a1[3000];
	int a[3000];
	while(gets(a1)){
		if(a1[0]=='-')
			break;
		l=strlen(a1);
		for(i=0;i<l;i++){
			if(a1[i]=='{')
				a[i]=1;
			else if(a1[i]=='}')
				a[i]=-1;
		}
		int sum=0;k=0;
		for(i=0;i<l;i++){
			sum+=a[i];
			if(sum<0){
				sum=1;
				k++;
			}
		}
		if(sum>0)
			k+=sum/2;
		printf("%d. %d\n",cs++,k);
	}
	return 0;
}


题目链接:http://poj.org/problem?id=3991

题目解析:这是匹配问题,其实不难,关键是要找到思路。就是计数左括号,当遇到一个右括号的时候做相应的匹配

                  而比较简单的做法就是把左括号标记为1,右括号标记为-1,然后进行计算,要是一一匹配下来sum=0的话,恰好能匹配完全。要是sum<0说明右括号多出来,此时用k记录下右括号的个数,然后把sum变成1,;

代码:

网友评论
<