Wie finde ich einen Teilstring zwischen zwei Zeichen mit Prolog?

Question

Ich habe eine Variable, die an ein Prädikat übergeben wird, das eine Liste von Zeichenfolgen ist.

Von jeder Zeichenfolge in der Liste möchte ich die Teilzeichenfolge zwischen den tiefsten Satz von Klammern extrahieren und eine Liste aller dieser Teilzeichenfolgen erstellen.

Zum Beispiel:

• Eingang:

  ["Canidae(Canis(C. lupus(C. l. familiaris)))", "Felidae(Felinae(Felis(F. catus)))", "Equidae(Equus(E. ferus(E. f. caballus)))"] 
  

• Ouput:

  ["C. l. familiaris", "F. catus", "E. f. caballus"] 
  

(I biologischen Klassifikation verwendet zählt als Beispiel, da sie ähnlich sind in Struktur zu meinen tatsächlichen Daten a)

Schließlich ist die Tiefe jedes Klammersatzes unbekannt und der tiefste Teilstring ist immer der einzige Teilstring zwischen einer offenen Klammer und einer geschlossenen Klammer.

Vielen Dank für Ihre Hilfe, ich bin neu in Prolog, so ist die Art des Denkens ein wenig anders. Ich habe versucht, mich für eine Weile mit diesem Problem herumzuschlagen, aber ich kann es nicht hinbekommen.

Answer 1

Anstatt das Problem für eine Liste zu lösen, lösen wir zuerst das Problem für eine einzelne Zeichenfolge. Um die tiefste Teilkette zu berechnen, können wir - wenn ich die Spezifikationen richtig verstanden habe - die Position der letzten öffnenden Klammer berechnen. Wir gehen davon aus, dass Sie die Zeichenfolge in eine Liste von ASCII-Codes umgewandelt haben, zum Beispiel mit string_codes/2.Hier wird die öffnende Klammer hat Code 40:

last_opening(L,X) :- 
    last_opening(L,0,0,X). 

last_opening([],J,_,J). 
last_opening([40|T],_,I,X) :- 
    !, 
    I1 is I+1, 
    last_opening(T,I1,I1,X). 
last_opening([_|T],J,I,X) :- 
    I1 is I+1, 
    last_opening(T,J,I1,X). 

Zum Beispiel für Ihr erstes Beispiel:

?- string_codes("Canidae(Canis(C. lupus(C. l. familiaris)))",L),last_opening(L,X). 
L = [67, 97, 110, 105, 100, 97, 101, 40, 67|...], 
X = 23. 

Es sagt, dass wir von Entnahmeposition anfangen 23:

Canidae(Canis(C. lupus(C. l. familiaris))) 
        ^here 

---

Sobald wir wissen, wo der tiefste Teilstring beginnt, können wir den String extrahieren: wir einfach haben 41 am Ende der Liste oder auf Code zu stoppen, was auch immer zuerst kommt:

extract_substring(L,0,S) :- 
    !, 
    extract_substring2(L,S). 
extract_substring([_|T],N,S) :- 
    N1 is N-1, 
    extract_substring(T,N1,S). 

extract_substring2([],[]). 
extract_substring2([41|_],[]) :- 
    !. 
extract_substring2([L|T],[L|U]) :- 
    extract_substring2(T,U). 

Zum Beispiel:

?- string_codes("Canidae(Canis(C. lupus(C. l. familiaris)))",L),last_opening(L,X),extract_substring(L,X,T),string_codes(St,T). 
L = [67, 97, 110, 105, 100, 97, 101, 40, 67|...], 
X = 23, 
T = [67, 46, 32, 108, 46, 32, 102, 97, 109|...], 
St = "C. l. familiaris". 

---

Jetzt können wir ein Prädikat schreiben, das die string_codes Berufung tut automatisch:

deepest_string(S,T) :- 
    string_codes(S,CS), 
    last_opening(CS,X), 
    extract_substring(CS,X,CT), 
    string_codes(T,CT). 

Zum Beispiel:

?- deepest_string("Canidae(Canis(C. lupus(C. l. familiaris)))",L). 
L = "C. l. familiaris". 

---

Zum Schluss müssen wir nur noch die Funktion über eine Liste implementieren:

deepest_string_list([],[]). 
deepest_string_list([S|ST],[T|TT]) :- 
    deepest_string(S,T), 
    deepest_string_list(ST,TT). 

ergibt:

?- deepest_string_list(["Canidae(Canis(C. lupus(C. l. familiaris)))", "Felidae(Felinae(Felis(F. catus)))", "Equidae(Equus(E. ferus(E. f. caballus)))"],T). 
T = ["C. l. familiaris", "F. catus", "E. f. caballus"]. 

Wenn Sie die Zeichen ändern möchten, können Sie einfach Suchen Sie ihr ASCII-Äquivalent und setzen Sie diese anstelle von 40 und 41.

Answer 2

Ich würde eine DCG vorschlagen, und findAll/3:

par(L, Content, R) --> 
    left(L), inner(L, Content, R). 

left(P) --> P. 
left(P) --> [_], left(P). 

inner(_, [], R) --> R. 
inner(L, [C|Cs], R) --> 
    \+ L, \+ R, [C], inner(L, Cs, R). 

?- findall(A,(phrase(par("[",C,"]"),`[a[b][cd]]e`,_),atom_codes(A,C)),L). 
L = [b, cd]. 

Notiere den _ als letzte Parameter Phrase/3. Es ermöglicht das Erstellen von Listen mit findall/3.

Sie können eine beliebige Zeichenfolge als linke/rechte Klammer verwenden.