<分区>
这是我在一次采访中被问到的。当时我不知道它的正确复发。问题是,如果给定表达式的长度,那么该长度可以组成多少个合适的括号表达式,它们是什么?
例如,正确的括号表达式是
[[]][[[]][]]
[[[][]]][][[]]
以下不是正确的括号表达式,
[[[][]]][]][[]]
也就是说,每个左括号都有一个右括号。 我不是在寻找实现,而是在寻找算法或者我应该如何处理它?
谢谢!
标签 algorithm
<分区>
这是我在一次采访中被问到的。当时我不知道它的正确复发。问题是,如果给定表达式的长度,那么该长度可以组成多少个合适的括号表达式,它们是什么?
例如,正确的括号表达式是
[[]][[[]][]]
[[[][]]][][[]]
以下不是正确的括号表达式,
[[[][]]][]][[]]
也就是说,每个左括号都有一个右括号。 我不是在寻找实现,而是在寻找算法或者我应该如何处理它?
谢谢!
最佳答案
这是 Python 中的一个算法:
def properbracket(l, s):
if l == 0:
if s == 0:
return 1
else:
return 0
ret = 0
if s > 0:
ret += properbracket(l-1, s-1)
ret += properbracket(l-1, s+1)
return ret
print properbracket(2, 0)
print properbracket(4, 0)
print properbracket(6, 0)
...这里是不同长度的有效表达式: 长度 == 2:
[]
len == 4:
[[]]
[][]
len == 6:
[[[]]]
[][][]
[][[]]
[[][]]
[[]][]
这假设“][”不是一个有效的表达式。
关于algorithm - 给定括号总数,如何找到数量和实际正确的括号表达式?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29212363/