prolog - Prolog，生成n个平衡括号的所有组合

Question

你能告诉我如何在 PROLOG 中实现一个算法来生成 N 个平衡括号的所有组合吗？（正确关闭的括号）

标签： prologdcg

Answer 1

这是dcg最适合的。我们为平衡圆括号定义一个语法，然后相应地枚举它们。

:- set_prolog_flag(double_quotes, chars).

balanced --> "".
balanced --> "(", balanced, ")", balanced.

现在，当要求具体句子时，最好使用library(double_quotes)see this了解更多信息。

我们可以要求固定长度的句子：

| ?- length(T, 6), phrase(balanced, T).
   T = "()()()"
;  T = "()(())"
;  T = "(())()"
;  T = "(()())"
;  T = "((()))"
;  false.

或者只是比比皆是任何句子：

| ?- length(T, N), phrase(balanced, T).
   T = [], N = 0
;  T = "()", N = 2
;  T = "()()", N = 4
;  T = "(())", N = 4
;  T = "()()()", N = 6
;  T = "()(())", N = 6
;  T = "(())()", N = 6
;  T = "(()())", N = 6
;  T = "((()))", N = 6
;  T = "()()()()", N = 8
;  T = "()()(())", N = 8
;  T = "()(())()", N = 8
;  T = "()(()())", N = 8
;  T = "()((()))", N = 8
;  ...