序言中的有效括号列表

Question

我正在尝试测试括号列表是否有效。我的代码：

checkbrackets([]).
checkbrackets(['('|T]):-
    T = [')'|List],
    checkbrackets(List).    
checkbrackets(['('|T]):-
    T = ['('|List],
    append(Rest,[')'],T),
    checkbrackets(Rest).

我的代码适用['(', '(', ')', '(', '(', ')', ')', ')']
于['(', '(', ')', ')', '(', ')'].
我究竟做错了什么？是否可以在没有计数器等额外参数的情况下编写这样的测试？

Answer 1

您append(Rest, [')'], T)将解析到列表末尾，但并不是说左括号最终会与最后一个右括号匹配，例如()()不会。

话虽如此，我认为你让事情变得过于复杂。您可以在此处使用单次扫描，而不是获取各种子列表：您使用以 初始化0的累加器，并且累加器最终应以 结束0并且永远不会小于零，因此：

checkbrackets(B) :-
    checkbrackets(B, 0).

checkbrackets([], 0).  %% ← at the end, zero
checkbrackets([')'|T], N) :-
    N > 0,   %% ← always greater than or equal to zero.
    N1 is N-1,
    checkbrackets(T, N1).
checkbrackets(['('|T], N) :-
    N1 is N+1,
    checkbrackets(T, N1).

Answer 2

是否可以在没有计数器等额外参数的情况下编写这样的测试？

我相当确定不可能在不跟踪计数器或堆栈等附加信息的情况下编写这样的测试（编辑：单次遍历列表）。这是因为您正在解析的语言是一种适当的上下文无关语言，而不是常规语言。解析上下文无关语言需要某种无界状态表示，而常规语言则摆脱有限状态。

您通常会使用参数处理该额外状态。可能是隐藏的使用定语从句文法 (DCGs) 的。但在这里-我非常强烈建议你不使用任何东西-是存储不是一个额外的参数，但在列表本身的头状态的方式。

首先，确保我们使用有用的语法进行解析：

:- set_prolog_flag(double_quotes, chars).

这意味着双引号之间的任何内容都将被解释为字符列表，因此您可以"(()"等效地编写非常不可读的['(', '(', ')'].

这是代码本身：

checkbrackets([]).
checkbrackets(['(' | Xs]) :-
    checkbrackets([count(1) | Xs]).
checkbrackets([count(0)]).
checkbrackets([count(N), '(' | Xs]) :-
    N1 is N + 1,
    checkbrackets([count(N1) | Xs]).
checkbrackets([count(N), ')' | Xs]) :-
    N > 0,
    N1 is N - 1,
    checkbrackets([count(N1) | Xs]).

这将用初始化为 1 的计数器“替换”第一个左括号。它在消耗其他左括号或右括号时递增和递减该计数器。每次更新计数器时，新值都会被推送到传递给递归调用的列表的前面。当列表中的所有括号都被消耗掉并且计数器正好为 0 时，谓词成功。（您不会说是否要接受()()。此实现以特定方式解决了这种歧义，这可能不是您想要的.)

例子：

?- checkbrackets("").
true.

?- checkbrackets("(()(()))").
true ;
false.

?- checkbrackets("()(()))").
false.

?- checkbrackets("(()(())").
false.

您可以使用相同的技巧来解析需要比单个计数器更复杂状态的更复杂的语言。但你不应该。DCG 是在 Prolog 中执行此操作的最佳方式。

请注意，上面的实现确实接受了一个不纯粹是括号列表的列表：

?- checkbrackets([count(0)]).
true ;
false.

有可能解决这个问题，但你不应该，因为你根本不应该使用这种方法。

Answer 3

为了完整起见，这里是一个没有额外参数的解决方案。

checkbrackets([]).
checkbrackets(['('|Rest]):-
    append(Sub1,[')'|Sub2],Rest),
    checkbrackets(Sub1),
    checkbrackets(Sub2).

它只是遵循“适当括号”表达式的定义。它要么是空的，要么以 a 开头(，后跟一个正确括起来的子表达式 ( Sub1)，然后是)，然后是另一个正确括起来的子表达式 ( Sub2)。

然而，与 Willem Van Onsem 提出的一个额外参数的直接解决方案相比，它的效率相当低。主要问题是append/3调用需要非确定性地“猜测”匹配右括号的位置，这会产生大量回溯。

Answer 4

checkbrackets([]).
checkbrackets(L):-
    append(Sub1,['(',')'|Sub2],L),
    !,
    append(Sub1,Sub2,New),
    checkbrackets(New).

它确实只需要一个属性并以平方时间进行检查。虽然不如 Willems 或 Isabelles 的代码快，但也能工作。
这个想法是，在每个有效的括号星座中，至少有一次一个左括号和一个右括号彼此相邻的模式。找到它们，删除它们，然后重复。