допустимый список скобок в прологе

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

Ему нужен только один атрибут, и он проверяет квадратное время. Не так быстро, как код Виллемса или Изабель, но работает.
Идея состоит в том, что в каждом действительном созвездии скобок есть по крайней мере один шаблон из одной открывающей и одной закрывающей скобки рядом друг с другом. Найдите их, удалите их, повторите.

ваш 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).

Для полноты картины здесь решение без дополнительных аргументов.

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

Это просто следует за определением правильно заключенного в скобки выражения. Либо оно пусто, либо начинается с (, за которым следует правильно заключенное в скобки подвыражение (Sub1), за которым следует ), за которым следует еще одно правильно заключенное в скобки подвыражение (Sub2).

Однако это довольно неэффективно по сравнению с прямым решением с одним дополнительным аргументом, представленным Виллемом Ван Онсемом. Основная проблема заключается в том, что вызов append/3 должен недетерминистически угадывать положение соответствующей закрывающей скобки, а это приводит к большому количеству возвратов.

Можно ли написать такой тест без дополнительных аргументов вроде счетчиков?

Я совершенно уверен, что невозможно написать такой тест (edit:, который выполняет один проход по списку) без отслеживания дополнительной информации, такой как счетчик или стек. . Это связано с тем, что анализируемый вами язык является надлежащим контекстно-свободным языком, а не обычный. Синтаксический анализ контекстно-свободных языков требует некоторого вида представления неограниченного состояния, в то время как обычные языки обходятся конечными состояниями.

Обычно вы обрабатываете это дополнительное состояние с помощью аргументов. Возможно, скрытые с использованием грамматик с определенными предложениями (DCG). Но здесь — и я очень настоятельно рекомендую вам не использовать это ни для чего — есть способ сохранить это состояние не в дополнительном аргументе, а в начале самого списка.

Во-первых, убедитесь, что мы используем полезный синтаксис для синтаксического анализа:

:- 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 — лучший способ сделать это на Прологе.

Обратите внимание, что приведенная выше реализация принимает список, который не является просто списком скобок:

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

Исправить это можно, но не стоит, так как вообще не стоит использовать этот подход.