您好,匿名用户
随意问技术百科期待您的加入

一道经典的括号匹配笔面问题

0 投票

来自新浪weibo @陈利人

问题:

左“{”,右”}"括号各N个,请打印出所有正确的组合,比如当N=3,{}{}{},{}{{}},等为正确的组合。如果写的代码是recursive,能否用iterative再写一个;反之亦然。

求好的算法描述. (不用使用循环和递归都做.一种即可.这个用递归更简单些)

py实现:

def foo(output, open, close, pairs):
	if open == pairs and close == pairs:
		print output
	else:
		if open<pairs:
			foo(output+'(', open+1, close, pairs)
		if close<open:
			foo(output+')', open, close+1, pairs)

foo('', 0, 0, 3)
用户头像 提问 2012年 12月1日 @ Gangplank 上等兵 (314 威望)
分享到:

1个回答

0 投票
 
最佳答案

这个很容易就可以想到用回溯法来做。假设从左往右填括号。

状态包括:
(1) 填到第几个:int i
(2) 在右边最多还能填多少个 "}":int left
(3) 还剩多少个"{"可以填:int a
(4) 还剩多少个"{"可以填:int b

具体策略:
(1) 如果已经填完了,输出,返回(回溯)
(2) 如果还有"{"可以填:填进去,递归填下一个。
(3) 如果还可以填"}"并且还有"}"可以填:填进去,递归填下一个。

实现的代码附在后面。

至于转化成迭代的方式,任何递归都可以通过引入栈的方式来转化,只是写起来比较痛苦,看起来也比较痛苦就是了。

#include <stdio.h>

const int maxn = 50;
char x[maxn * 2 + 1];

void perm(int i, int left, int a, int b) {
    if (a == 0 && b == 0) {
        puts(x); 
        return; 
    }
    if (a > 0) {
        x[i] = '{';
        perm(i + 1, left + 1, a - 1, b);
    }
    if (b > 0 && left > 0) {
        x[i] = '}';
        perm(i + 1, left - 1, a, b - 1);
    }
}

int main() {
    int n = 4;
    x [n * 2] = 0;
    perm(0, 0, n, n);
    return 0;
}
用户头像 回复 2012年 12月1日 @ Malzahar 上等兵 (335 威望)
选中 2012年 12月1日 @Gangplank
提一个问题:

相关问题

0 投票
0 回复 20 阅读
0 投票
0 回复 21 阅读
用户头像 提问 2012年 12月1日 @ Morgana 上等兵 (251 威望)
0 投票
1 回复 26 阅读
0 投票
1 回复 27 阅读
用户头像 提问 2012年 12月1日 @ Gemini 上等兵 (319 威望)
0 投票
1 回复 78 阅读

欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。
温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。

欢迎访问随意问技术百科,为了给您提供更好的服务,请及时反馈您的意见。
...