24h購物| | PChome| 登入
2011-08-26 22:42:54| 人氣7,574| 回應3 | 上一篇 | 下一篇

a229. 括號匹配問題

推薦 0 收藏 0 轉貼0 訂閱站台

a229. 括號匹配問題
最近更新 : 2011-08-25 21:05

內容 :

最近要開學了!  ( ~~~ 跟題目沒有什麼關係 ) ><

 

請寫一個程式把所有合法括號匹配方式列出來!   

 

Ex. (())  ,  ((()())) , ()((()))  是合法的匹配方式 

 

      )( , (()))(  , ()(()(  是不合法的匹配方式

 

     合法匹配的括號 , 從答案列的開頭到答案列某一點,左括弧次數永遠大於等於右括弧!  

 

    Ex. 合法匹配   ((()()))     

    字串 (        左括弧 : 1  >=   右括弧 : 0     

    字串 ((        左括弧 : 2  >=   右括弧 : 0   

    字串 (((        左括弧 : 3  >=   右括弧 : 0    

    字串 ((()        左括弧 : 3  >=   右括弧 : 1

    字串 ((()(        左括弧 : 4  >=   右括弧 : 1

    字串 ((()()        左括弧 : 4  >=   右括弧 : 2

    字串 ((()())        左括弧 : 4  >=   右括弧 : 3

    字串 ((()()))        左括弧 : 4  >=   右括弧 : 4        

 

    Ex. 不合法匹配    (()))(

   字串 (        左括弧 : 1  >=   右括弧 : 0 

   字串 ((        左括弧 : 2  >=   右括弧 : 0   

   字串 (()        左括弧 : 2  >=   右括弧 : 1

   字串 (())        左括弧 : 2  >=   右括弧 : 2

   字串 (()))        左括弧 : 2  <=   右括弧 : 3    

!!! 右括弧次數大於左括弧了!  (()))( 為不合法匹配  

 

輸入說明 :

 

輸入一個正整數 N , 1 =< N <= 13 。

N 代表有幾組括號要匹配

Ex.

      N = 1 代表 一組括號 ()

      N = 2 代表有兩組括號  ()() 

 

輸出說明 :

 

輸出 N 組括號的所有合法匹配組合   

輸出方式請見範例

 

範例輸入 :

1
2
3
4

範例輸出 :

()
 
(())
()()
 
((()))
(()())
(())()
()(())
()()()

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

提示 :

背景知識: DFS


出處 :

C++ 名題百則 (管理:stanley17112000)



作法 : DFS
程式碼很短, 就不多說了

/**********************************************************************************/
/*  Problem: a229 "括號匹配問題" from C++ 名題百則                      */
/*  Language: C                                                                   */
/*  Result: AC (128ms, 176KB) on ZeroJudge                                        */
/*  Author: morris1028 at 2011-08-26 19:50:58                                     */
/**********************************************************************************/


#include<stdio.h>
int n;
void DFS(int index, int r, int l, char *s) {
    if(l == n) {
        puts(s-2*n);
        return;
    }
    if(r < n)
    *s = '(', DFS(index+1, r+1, l, s+1);
    if(r > l)
    *s = ')', DFS(index+1, r, l+1, s+1);
}
main() {
    char s[100];
    while(scanf("%d", &n) == 1)
        s[2*n] = '\0', DFS(0, 0, 0, s), puts("");
    return 0;
}

台長: Morris
人氣(7,574) | 回應(3)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:d739. 最少路径覆盖
此分類上一篇:a219. 限制排列

eewe
卧槽!!!
2014-09-03 16:22:27
chongwanying
hihihihihihihihi 你好厉害哦 可是我看不懂
2018-08-01 15:27:41
12123
12326544259364681321
2018-08-01 15:28:17
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文