产生匹配括号的字符串

文章目錄

请写一个程序，输入一个正整数的值，然后列出所有有n个做括号与n个右括号正确地组成的字符串；当然，正确的左、右括号一定个数一样多。

说明：
所谓由括号正确地组成的字符串，指的是如果有一个左括号，那么在它的右边就一定有一个与它相匹配的右括号。(())、()(),就是仅有的两个由两个左括号和两个右括号正确地组成的字符串；((()))、(()())、(())()、()(())、()()()是仅有的5个由3个左括号和3个右括号正确地组成的字符串。

如何产生这样的字符串呢？下面就是一个有用的想法：如果在产生的过程中已经产生了若干左、右括号，为了要把产生的行为完成，还欠R个左括号、L个右括号，那么有没有办法找出产生下一个括号时L与R的关系呢？记住，递归是一个不容忽视的利器。
解法：
假设还有left个左括号和right个右括号等待匹配，根据left与right的大小可以分三种情况
1.当 left == right 时，此时只能继续放左括号
2.当 left < right时，可以有两个选择， 继续放一个左括号或者继续放一个有括号。
放左括号时需要判断left是否大于0，只有left大于0时,才能继续放左括号。
放右括号时则不需要判断。
3.当left > right时，此时没有意义。

写成Java程序如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GenerateParenthesis {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        generateParenthesis(n, n , n, "", result);
        return result;
    }
    private static void generateParenthesis(int left, int right, int n, 
            String s, List<String> result) {

        if (s.length() == n * 2) {
            result.add(s);
        } else {
            if (left == right) {
                generateParenthesis(left - 1, right, n , s + "(", result);
            } else if (left < right) {
                if (left > 0) {
                    generateParenthesis(left - 1, right, n , s + "(", result);
                }
                generateParenthesis(left, right - 1, n, s + ")", result);
            } 
        }    
    }
    public static void main(String[] args) {
        List<String> result = generateParenthesis(3);
        for (String s: result) {
            System.out.println(s);
        }
    }
}

还可以对程序进行优化，因为递归过程会产生许多字符串，可以用数组来解决这个问题。修改程序如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GenerateParenthesis {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        char[] str = new char[n * 2];
        generateParenthesis(n, n , str, 0, result);
        return result;
    }
    private static void generateParenthesis(int left, int right, char[] str, 
            int length, List<String> result) {

        if (length == str.length) {
            result.add(String.valueOf(str));
        } else {
            if (left == right) {
                str[length] = '(';
                generateParenthesis(left - 1, right, str, length + 1, result);
            } else if (left < right) {
                if (left > 0) {
                    str[length] = '(';
                    generateParenthesis(left - 1, right, str, length + 1, result);
                }
                str[length] = ')';
                generateParenthesis(left, right - 1, str, length + 1, result);
            } 
        }    
    }
    public static void main(String[] args) {
        List<String> result = generateParenthesis(3);
        for (String s: result) {
            System.out.println(s);
        }
    }
}