#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,;
代码: