前言中的有效括号列表 [英] valid bracket list in prolog

问题描述

我正在尝试测试方括号列表是否有效.我的代码:

I'm trying to test if a list of brackets is valid. My code:

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

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

My code works for ['(', '(', ')', '(', '(', ')', ')', ')']
but it fails for ['(', '(', ')', ')', '(', ')'].
What am I doing wrong? Is it possible to write such a test without additional arguments like counters?

推荐答案

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

它确实只需要一个属性，并以平方时间为单位进行检查.不如Willems或Isabelles代码快，但可以工作.
这个想法是，在每个有效的括号星座中，至少有一个开口括号和一个闭合括号的图案彼此相邻.找到它们，删除它们，然后重复.

It does need only one attribute and checks in square time. Not as fast as Willems or Isabelles code but works.
The idea is that in each valid bracket constellation there is at least once the pattern of one opening and one closing bracket next to each other. Find them, delete them, repeat.

这篇关于前言中的有效括号列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！