Problem Description

給出一個(gè)字符串，其中包括3種字符: ‘(‘, ‘)’, ‘?’.其中?表示這個(gè)字符可以是’(‘也可以是’)’. 現(xiàn)在給出字符串S,你可以在’?’處填寫’(‘ 或者 ‘)’，當(dāng)然隨意填寫得到的序列可能是括號不匹配的。例如”(?”，如果你填寫’(‘那么”((“是括號不匹配的！ 現(xiàn)在你的任務(wù)是確定你有多少種填寫方案，使得最終的字符串是括號匹配的！2種方案是不同的，當(dāng)2種方案中至少存在1個(gè)填寫字符是不同的。 例如，對于”((??))”,我們可以得到2種方案: “((()))”, “(()())”。

Input

數(shù)據(jù)包含多組測試數(shù)據(jù)第一行輸入一個(gè)字符串S(S的長度不超過16)。

Output

輸出一個(gè)整數(shù),表示合法的填寫方案數(shù)。

Sample Input

((??))

Sample Output

2 講解：剛開始看這個(gè)題，你會想到括號配對，但是呢這兩個(gè)題卻又不太一樣，所以我們依然也可以采用那種方式來做的，只不過要變換一次遞歸一次，最后遞歸出來結(jié)果，下面就以例題為例子講解一下： 注意：遇見0了則不能再進(jìn)性下去； 如圖所示： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 char str[1010]; 6 int len; 7 int ans; 8 void fun(int end,int k) 9 { 10 if(end==len && k==0) 11 { 12 ans++; 13 } 14 if(k<0) 15 { 16 17 } 18 else if(str[end]=='?') 19 { 20 fun(end+1,k-1); 21 fun(end+1,k+1); 22 } 23 else if(str[end]=='(') 24 { 25 fun(end+1,k+1); 26 } 27 else if(str[end]==')') 28 { 29 fun(end+1,k-1); 30 } 31 } 32 int main() 33 { 34 while(gets(str)) 35 { 36 ans=0; 37 len=strlen(str); 38 fun(0,0); 39 printf("%d\n",ans); 40 } 41 return 0; 42 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lovychen/p/3413255.html

總結(jié)

以上是生活随笔為你收集整理的FZU Problem 2030 括号问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。