给定一个数字n,输出包含n对括号的所有合法字符串

技术宅 rainforest 1年前 (2019-02-23) 604次浏览 0个评论

所谓n对括号的所有合法字符串即是指:括号能够被合法关闭,比如“()”是一个合法的括号字符串,而“)(”是一个非法的括号字符串。

首先我们看怎么样的括号字符串是合法的呢?很容易观察到规律,就是从前到后扫描,右括号的数永远不大于左括号的数,到最后左括号的数和右括号的数是相等的。

要考虑输出n对所有的合法的括号字符串,那我们可以用分裂的思路,一个字符串往后加:

  1. 如果左括号的数<n,则可以再加入左括号
  2. 如果右括号的数<左括号的数,则可以加入右括号

简单来说可以采用递归的思路来解决,也可以用一个栈,然后用循环的策略来解决,这里为了简单,给定一个循环的实现:

#include <iostream>
#include <string>

void print_legal_brackets(int n, std::string stack = "", int left = 0, int right = 0) {
    if (left == n && right == n) {
        std::cout << stack << std::endl;
        return;
    }   

    if (left < n) {
        print_legal_brackets(n, stack + "(",  left + 1, right);
    }   

    if (right < left) { 
        print_legal_brackets(n, stack + ")", left, right + 1); 
    } 
} 

int main(int argc, char *argv[]) { 
    int n = 0; 
    while (std::cin >> n) {
        print_legal_brackets(n);
    }   
    return 0;
}


最后我们考虑具体输出多少个字符串呢?应该是个卡特兰数,即:
$$C_{2n}^{n}/(n+1)$$


乐趣公园 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:给定一个数字n,输出包含n对括号的所有合法字符串
喜欢 (1)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址