Entklammern einer Zeichenfolge

25

Bei einer korrekt in Klammern gesetzten Zeichenfolge als Eingabe wird eine Liste aller nicht leeren Teilzeichenfolgen in übereinstimmenden Klammern (oder außerhalb aller Klammern) ausgegeben, wobei geschachtelte Klammern entfernt werden. Jede Teilzeichenfolge sollte die Folge von Zeichen in genau den gleichen Klammern sein. Teilzeichenfolgen sollten in der Reihenfolge der Tiefe aufgelistet werden, und Teilzeichenfolgen derselben Tiefe sollten in der Reihenfolge aufgelistet werden, in der sie in der Zeichenfolge vorkommen. Angenommen, die Eingabe ist immer korrekt in Klammern gesetzt.

Sie können davon ausgehen, dass die Eingabe nur ASCII-Kleinbuchstaben und Klammern enthält.

Ihre Antwort sollte eine Funktion sein, die bei Angabe einer Zeichenfolge eine Liste von Zeichenfolgen zurückgibt.

Beispiele:

                   'a(b)c(d)e' -> ['ace', 'b', 'd']
                   'a(b(c)d)e' -> ['ae', 'bd', 'c']
                  'a((((b))))' -> ['a', 'b']
                        'a()b' -> ['ab']
                            '' -> []
                           'a' -> ['a']
          '(((a(b)c(d)e)f)g)h' -> ['h', 'g', 'f', 'ace', 'b', 'd']
'ab(c(((d)ef()g)h()(i)j)kl)()' -> ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

Wenigste Bytes gewinnt.

redstonerodent
quelle
Sind 'i'und 'd'in der richtigen Reihenfolge im letzten Testfall?
PurkkaKoodari
@ Pietu1998 iist weniger tief verschachtelt als d.
Feersum
@feersum Oh, richtig.
PurkkaKoodari
1
Würde es Ihnen etwas ausmachen, auch die anderen Standardeinreichungsarten zuzulassen, insbesondere vollständige Programme? Nicht alle Sprachen haben ein Funktionskonzept. Informationen zum Standardkonsens finden Sie unter meta.codegolf.stackexchange.com/a/2422/8478 und meta.codegolf.stackexchange.com/questions/2447/… .
Martin Ender
2
@redstonerodent Die Formulierung, die ich normalerweise verwende, lautet: "Sie können ein Programm oder eine Funktion schreiben, Eingaben über STDIN (oder die nächstgelegene Alternative), Befehlszeilenargumente oder Funktionsargumente und Ausgaben des Ergebnisses über STDOUT (oder die nächstgelegene Alternative), Funktionsrückgabewert oder Funktionsparameter (out). " und in Ihrem Fall "Die Ausgabe kann in jedem geeigneten, eindeutigen, flachen Listenformat erfolgen."
Martin Ender

Antworten:

11

JavaScript ES6, 91 93 104 133 148

Edit2 2 Bytes gespeichert dank user81655

Bearbeiten Sie mit mehr Zeichenfolgen und weniger Arrays

Testen Sie das folgende Snippet in einem EcmaScript 6-kompatiblen Browser

f=s=>[...s].map(c=>l+=c<')'||-(o[l]=(o[l]||'')+c,c<'a'),o=[],l=0)&&(o+'').match(/\w+/g)||[]

// Less golfed

u=s=>{
  o=[]; l=0;
  [...s].map(c=>{
    if (c>'(') // letters or close bracket
      o[l]=(o[l]||'')+c, // add letter or close bracket to current level string
      l-=c<'a' // if close bracket, decrement level
    else
      ++l // open bracket, increment level
  })
  o = o+'' // collapse array to comma separated string
  return o.match(/\w+/g)||[] // fetch non empty strings into an array
}

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[ 'a(b)c(d)e'                    // ['ace', 'b', 'd']
 , 'a(b(c)d)e'                    // ['ae', 'bd', 'c']
 , 'a((((b))))'                   // ['a', 'b']
 , 'a()b'                         // ['ab']
 , ''                             // []
 , 'a'                            // ['a']
 , '(((a(b)c(d)e)f)g)h'           // ['h', 'g', 'f', 'ace', 'b', 'd']
 , 'ab(c(((d)ef()g)h()(i)j)kl)()' // ['ab', 'ckl', 'hj', 'efg', 'i', 'd']
].forEach(t=>console.log(t +" -> " + f(t)))
<pre id=O></pre>

edc65
quelle
Sparen Sie 2 Bytes mit c=>l+=c<')'||-(o[l]=(o[l]||'')+c,c<'a'),.
user81655
@ user81655 nett, danke
edc65
8

Julia, 117 86 83 Bytes

v->(while v!=(v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))end;split(v))

Es ist eine Regex-Lösung.

Ungolfed:

function f(v)
  w=""
  while v!=w
    w=v
    v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))
  end
  split(v)
end

r"(\(((?>\w|(?1))*)\))(.*)"ist eine rekursive ( (?1)rekursive Gruppe 1) Regex, die den ersten ausgeglichenen Klammern (die keine unsymmetrischen / umgekehrten Klammern enthalten) entspricht, wobei die zweite Gruppe alles in den Klammern enthält (ohne die Klammern selbst) und die dritte Gruppe enthält alles nach den Klammern (bis zum Ende der Zeichenkette).

replace(v,r"...",s"\g<3> \g<2>")Verschiebt dann die zweite Gruppe an das Ende der Zeichenfolge (nach einem Leerzeichen, um als Begrenzer zu fungieren), wobei die entsprechenden Klammern entfernt werden. Durch Iterieren bis v == w wird sichergestellt, dass das Ersetzen wiederholt wird, bis keine Klammern mehr vorhanden sind. Da Übereinstimmungen an das Ende verschoben werden und die nächste Übereinstimmung für die erste Klammer gilt, ist das Ergebnis die Zeichenfolge, die in der Reihenfolge der Tiefe aufgeschlüsselt ist.

Dann splitkehrt alle der Nicht-Leerzeichen Komponenten der String in der Form einer Anordnung von Zeichenketten (die keine Leerzeichen haben).

Beachten Sie, dass dies w=""im ungolfed-Code verwendet wird, um sicherzustellen, dass die while-Schleife mindestens einmal ausgeführt wird (außer natürlich, wenn die Eingabezeichenfolge leer ist) und in der golfed-Form nicht benötigt wird.

Vielen Dank an Martin Büttner für die Unterstützung beim Sparen von 3 Bytes.

Glen O
quelle
Ordentlich, ich bin unabhängig in Retina zu der gleichen Lösung gekommen. Es sind dort 44 Bytes, aber aus heutiger Sicht sind Vollprogrammlösungen nicht erlaubt. : /
Martin Ender
Sie können drei Bytes einsparen, indem Sie \wanstelle von verwenden [^()].
Martin Ender
@ MartinBüttner - danke. Eigentlich hatte ich darüber nachgedacht, aber ich war besorgt, dass ich etwas übersehen hatte und dass es an einem Randfall scheitern würde. Wenn Sie sagen, es ist in Ordnung, dann ist es in Ordnung.
Glen O
6

Python, 147 Bytes

def f(s):
 d=0;r=[['']for c in s]
 for c in s:
  if c=='(':d+=1;r[d]+=['']
  elif c==')':d-=1
  else:r[d][-1]+=c
 return[i for i in sum(r,[])if i]

Unit-Tests:

assert f('a(b)c(d)e') == ['ace', 'b', 'd']
assert f('a(b(c)d)e') == ['ae', 'bd', 'c']
assert f('a((((b))))') == ['a', 'b']
assert f('a()b') == ['ab']
assert f('') == []
assert f('a') == ['a']
assert f('(((a(b)c(d)e)f)g)h') == ['h', 'g', 'f', 'ace', 'b', 'd']
assert f('ab(c(((d)ef()g)h()(i)j)kl)()') == ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

Ich mag dieses Rätsel. das ist sehr süß!

Quuxplusone
quelle
4

Pyth, 32 Bytes

fTscR)uX0.<GJ-FqLH`()@[Hdk)Jzmkz

Testsuite

Locker basierend auf @ Quuxplusones Ansatz. Erstellt durch Leerzeichen getrennte Listen der Zeichen in jeder Tiefe, teilt sie dann auf und filtert die leeren Gruppen heraus. Die Arbeitsliste wird gedreht, um die aktuelle Tiefenliste immer im Vordergrund zu haben.

isaacg
quelle
4

Retina , 44 41 Bytes

+`\(((\w|(\()|(?<-3>.))*).(.*)
$4 $1
S_` 

Laufen Sie mit der -sFlagge. Beachten Sie das Leerzeichen am Ende der letzten Zeile.

Ich habe diese Lösung unabhängig von Glen O entwickelt, aber sie ist identisch. Die Idee ist, das erste Klammernpaar abzugleichen, es zu entfernen und seinen Inhalt am Ende der Ausgabe einzufügen (wiederholt). Aufgrund der fehlenden Rekursion von .NET in regulären Ausdrücken musste ich Bilanzgruppen verwenden, die vier Bytes länger sind.

Wenn Sie den ersten regulären Ausdruck nicht verstehen, verweisen wir Sie auf meine SO-Antwort zum Thema Bilanzkreise . Da die Eingabe garantiert in Klammern steht, können wir zwei Bytes einsparen, indem wir statt )mit mit übereinstimmen . Dann passen wir einfach den Rest der Zeichenfolge an . Schreibt zuerst den Rest der Zeichenfolge zurück (wobei sowohl die Klammern als auch deren Inhalt weggelassen werden) und dann den Inhalt der Klammern nach einem Leerzeichen. Das weist Retina an, diesen Schritt zu wiederholen, bis sich die Zeichenfolge nicht mehr ändert (was erst geschieht, wenn alle Klammern entfernt wurden)..\)(.*)$4 $1+`

Leere Klammern führen zu zwei aufeinanderfolgenden Leerzeichen. Schließlich teilen wir die gesamte Zeichenfolge in Leerzeichen auf ( S`aktiviert den Teilungsmodus und die Regex ist ein einzelnes Leerzeichen). Die _Option weist Retina an, leere Teile der Teilung wegzulassen, sodass die leeren Ergebnisse nicht in die Ausgabe einbezogen werden.

Martin Ender
quelle
3

Common Lisp, 160

(lambda(x)(labels((g(l)(cons(#1=format()"~(~{~A~}~)"(#2=remove-if'listp l))(mapcan #'g(#2#'atom l)))))(remove""(g(read-from-string(#1#()"(~A)"x))):test'equal))))

Dies könnten vier Bytes weniger sein, wenn die Konvertierung der Groß- / Kleinschreibung nicht erforderlich wäre. Die Idee ist, jeder Seite der Eingabezeichenfolge eine linke und eine rechte Klammer hinzuzufügen, sie als Liste zu behandeln, die Elemente der obersten Ebene der Liste in eine Zeichenfolge zu schreiben und die Unterlisten dann auf die gleiche Weise zu verarbeiten.

Joshua Taylor
quelle
2

Haskell, 114 112 111 Bytes

')'%(h:i:t)=("":i):t++[h]
'('%l=last l:init l
c%((h:i):t)=((c:h):i):t
g x=[a|a<-id=<<foldr(%)(x>>[[""]])x,a>""]

Anwendungsbeispiel: g "ab(c(((d)ef()g)h()(i)j)kl)()"-> ["ab","ckl","hj","efg","i","d"].

Ich gehe die Eingabezeichenfolge rückwärts durch. Die Zwischendatenstruktur ist eine Liste von Zeichenfolgen. Die äußere Liste ist pro Ebene und die innere Liste ist pro Gruppe innerhalb einer Ebene, z. B. [["ab"],["ckl"],["hj"],["efg","i"],["d"]](Hinweis: Die reale Liste enthält viele leere Zeichenfolgen dazwischen). Alles beginnt mit einer Anzahl von leeren Strings, die der Länge der Eingabe entsprechen - mehr als genug, aber leere Listen werden trotzdem herausgefiltert. Die äußeren Listen drehen sich entweder um (/ )oder fügen dem vorderen Element das Zeichen hinzu. )startet auch eine neue Gruppe.

Bearbeiten: @Zgarb hat ein Byte zum Speichern gefunden.

nimi
quelle
1

Sed, 90 Bytes

:
s/^(\w*)\((.*)\n?(.*)/\1\n\3_\2/M
s/(\n\w*_)(\w*)\)(.*)/\3\1\2/M
t
s/[_\n]+/,/g
s/,$//

Verwendet erweiterte reguläre Ausdrücke ( -rFlag) mit einem Anteil von +1 Byte. Dies verwendet auch eine GNU-Erweiterung (das MFlag im sBefehl).

Beispielnutzung:

$ echo 'ab(c(((d)ef()g)h()(i)j)kl)()' | sed -r -f deparenthesize.sed
ab,ckl,hj,efg,i,d

Erläuterung: Da sed keine rekursiven regulären Ausdrücke unterstützt, ist manuelle Arbeit erforderlich. Der Ausdruck ist in mehrere Zeilen aufgeteilt, die jeweils eine Verschachtelungstiefe darstellen. Die einzelnen Ausdrücke in derselben Tiefe (und damit in derselben Zeile) werden durch ein getrennt _. Das Skript arbeitet die Eingabezeichenfolge nacheinander in Klammern ab. Die verbleibende Eingabe bleibt immer am Ende der Zeile, die der aktuellen Verschachtelungsebene entspricht.

matz
quelle
0

Python, 161 Bytes

Folgendes habe ich mir ausgedacht: Eine einzeilige funktionale Python-Lösung:

p=lambda s:filter(None,sum([''.join([s[i]for i in range(len(s))if s[:i+1].count('(')-s[:i+1].count(')')==d and s[i]!=')']).split('(')for d in range(len(s))],[]))

Diese Herausforderung wurde von https://github.com/samcoppini/Definition-book inspiriert , das eine lange Zeichenfolge mit in Klammern definierten Wörtern ausgibt. Ich wollte Code schreiben, der mir jeden Satz mit entfernten Klammern gibt. Die funktionale Lösung ist zu langsam, um auf langen Saiten wirksam zu sein, aber Imperativlösungen (wie die Lösung von @ Quuxplusone) sind viel schneller.

redstonerodent
quelle