序言中的有效括号列表

Question

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

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

我的代码适用于 ['(', '(', ')', '(', '(', ')', ')', ')']
但是 ['(', '(', ')', ')', '(', ')'].
失败了我究竟做错了什么？是否可以在不使用计数器等附加参数的情况下编写这样的测试？

Answer 1

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

话虽这么说，我认为你把事情搞得太复杂了。您可以在这里使用一次扫描，而不是获取各种子列表：您使用一个用 0 初始化的累加器，累加器最终应该以 0 结束并且永远不会小于零，所以:

checkbrackets(B) :-
    checkbrackets(B, <b>0</b>).

checkbrackets([], <b>0</b>).  %% ← 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

Is it possible to write such a test without additional arguments like counters?

我相当确定如果不跟踪额外的信息编辑： 就不可能编写这样的测试（只通过列表一次） 例如计数器或堆栈。这是因为您正在解析的语言是正确的context-free language as opposed to a regular one。解析上下文无关语言需要某种无界状态表示，而常规语言则需要有限状态。

您通常会使用参数处理该额外状态。可能使用 definite clause grammars (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).

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

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

Answer 4

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

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

序言中的有效括号列表

valid bracket list in prolog

parsing

brackets

list

prolog