高中生程式解題系統：括號匹配問題 Balanced Parentheses

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://zerojudge.tw/ShowProblem?problemid=a229。

這題用 Depth-first search (DFS) 的觀念來解。

程式碼一：

#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;
}

程式碼二：

#include <cstdio>
#include <iostream>

using namespace std;

void prtPattern(int index, int right, int left, char *pattern) {
 if(index == right && left == index)
 {
  puts(pattern - 2 * index);
 }
 
 if( right < index )
 {
  *pattern = '(';
  prtPattern(index, right + 1, left, pattern + 1);
 }
 
 if( left < right)
 {
  *pattern = ')';
  prtPattern(index, right, left + 1, pattern + 1);
 }
}

int main() {
 int n;
    while(scanf("%d", &n) != EOF)
 {
  char str[32] = {'\0'};
  prtPattern(n,  0, 0, str);
 }
    return 0;
}