Problem 2030 括号问题
Accept: 413 Submit: 804
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
给出一个字符串，其中包括3种字符: ‘(‘, ‘)’, ‘?’.其中?表示这个字符可以是’(‘也可以是’)’. 现在给出字符串S,你可以在’?’处填写’(‘ 或者 ‘)’，当然随意填写得到的序列可能是括号不匹配的。例如”(?”，如果你填写’(‘那么”((“是括号不匹配的！ 现在你的任务是确定你有多少种填写方案，使得最终的字符串是括号匹配的！2种方案是不同的，当2种方案中至少存在1个填写字符是不同的。 例如，对于”((??))”,我们可以得到2种方案: “((()))”, “(()())”。
Input
数据包含多组测试数据第一行输入一个字符串S(S的长度不超过16)。
Output
输出一个整数,表示合法的填写方案数。
Sample Input
((??))
Sample Output
2
思路：
代码：
#include
#include
using namespace std; char s[20]; int len; int ans; void DFS(int i,int cnt)//cnt代表没配对的（的个数 { if(i==len&&cnt==0) { ans++; } if(cnt<0||i>=len) return; if(s[i]=='(') DFS(i+1,cnt+1); else if(s[i]==')') DFS(i+1,cnt-1); else { DFS(i+1,cnt+1); DFS(i+1,cnt-1); } } int main() { while(scanf("%s",s)==1) { len=strlen(s); ans=0; DFS(0,0); printf("%d\n",ans); } return 0; }