Schreiben Sie ein Programm, das die geschweiften Klammern durch Leerzeichen ersetzt, wenn geschweifte Klammern an bestimmten Stellen zu Stauungen führen

17

Sie sind Projektmanager. Eines Tages wurde einer Ihrer Programmierer wahnsinnig ( nicht Ihre Schuld ), nahm alle Ausdrücke in die Codebasis und fügte ihnen zufällige Klammern hinzu, bevor er sofort aufhörte und über Ihre Inkompetenz schwärmte ( auch nicht Ihre Schuld ). Dies ist jedoch eine einfache Lösung, da Sie aus irgendeinem Grund die Versionskontrolle nicht verwenden ( ganz und gar nicht Ihre Schuld ). Und aus irgendeinem Grund möchte keiner der anderen Programmierer alle Ausdrücke durchgehen, um die nicht übereinstimmenden Klammern zu korrigieren ( das ist übrigens nicht Ihre Schuld ). Programmierer heutzutage, denken Sie. Sie müssen es selbst tun. Der Horror! Solche Aufgaben sollten unter Ihnen sein ...

Die Eingabe wird eine einzelne Zeile sein, die eine Reihe von linken Klammern ( ( [ {) und rechten Klammern ( ) ] }) enthält. Es kann auch, aber nicht immer, Kommentare ( /* */) und Zeichenkettenliterale ( " "oder ' ') sowie verschiedene Zahlen, Buchstaben oder Symbole enthalten.

Es wird mindestens eine eckige Klammer (außerhalb eines Kommentars oder eines String-Literal) geben, die kein entsprechendes Gegenteil hat (außerhalb eines Kommentars oder eines String-Literal). Zum Beispiel ein Irrtum }ohne {Prior. Ein anderes Beispiel: a, (das )hinterher kein hat . Ihr Programm ersetzt durch ein Leerzeichen die Mindestanzahl von Klammern, die erforderlich sind, damit die Klammern übereinstimmen.

Beispiele:

(4 + (2 + 3))]==> (4 + (2 + 3)) (die eckige Klammer am Ende)
][][[]]==> [][[]](die eckige Klammer am Anfang)
("Hel(o!"))==> ("Hel(o!") (die Klammer am Ende)
( /* )]*/==> /* )]*/ (die Klammer am Anfang)
{()]==> () (die geschweifte Klammer und die eckige Klammer)

  • Die Eingabe kann von einem beliebigen Ort aus erfolgen (STDIN, Befehlszeilenargument, Lesen aus einer Datei usw.).
  • Wenn es mehr als eine Möglichkeit gibt, die Nichtübereinstimmung mit der gleichen Anzahl von Entfernungen zu beheben, ist beides akzeptabel.
  • In Klammern werden nur Abweichungen angezeigt. Zeichenkettenliterale und Kommentare werden immer korrekt gebildet.
  • Der Titel stammt aus diesem SO-Thread
  • Es wird niemals Anführungszeichen in Kommentaren, Anführungszeichen in Anführungszeichen, Kommentare in Kommentaren oder Kommentare in Anführungszeichen geben.

Dies ist Codegolf, daher gewinnt die Mindestanzahl an Bytes. Stellen Sie Fragen in Kommentaren, wenn die Spezifikation nicht klar ist.

Absinth
quelle
Hoppla, unsere Bearbeitungen sind dort irgendwie kollidiert. : P Alles sollte jetzt behoben sein.
Türklinke
@Doorknob Danke übrigens dafür. Wusste nicht, wie SE daran zu hindern , die Räume reinigen.
Absinth
Müssen wir mit entkommenen Sachen in String-Literalen umgehen (zB ("foo (\") bar"))?
Türklinke
1
Ich würde argumentieren, dass die richtige Ausgabe für {{(})sollte { } oder gleichwertig sein, da das Eröffnungsszenario impliziert, dass der Code zu Beginn arbeitete, und {(})als nicht übereinstimmende Klammern in jeder mir bekannten Programmiersprache zählt (dh "verursacht Stasis" ??). Aber dann habe ich bereits eine Antwort geschrieben, also bin ich voreingenommen.
DLosc
3
Aha. Ich glaube, ich bin einfach nicht inkompetent genug. ;)
DLosc

Antworten:

6

Ruby, 223 Zeichen

Dieser erwies sich als etwas lang.

u,b,i=[],[[],[],[]],-1
s=gets.gsub(/(\/\*|"|').*?(\*\/|"|')|~/){|m|u+=[m];?~}
s.chars{|c|i+=1
(t='{[('.index(c))?b[t].push(i):((t='}])'.index(c))&&(b[t].pop||s[i]=' '))}
b.flatten.map{|l|s[l]=' '}
puts s.gsub(/~/){u.shift}

Es werden zuerst die Zeichenfolgen und Kommentare entfernt, damit sie nicht gezählt werden (und später wieder eingefügt werden).

Dann wird die Zeichenfolge zeichenweise durchlaufen. Wenn es eine öffnende Klammer findet, speichert es seine Position. Wenn eine schließende geschweifte Klammer gefunden wird, wird sie aus dem entsprechenden Speicherarray für offene geschweifte Klammern entfernt.

Bei popRückgabe nil(dh es gab nicht genügend öffnende Klammern) wird die schließende Klammer entfernt. Nachdem dies alles erledigt ist, werden die verbleibenden zusätzlichen öffnenden Klammern entfernt (dh es gab nicht genügend schließende Klammern).

Am Ende des Programms werden alle Zeichenfolgen und Kommentare zurückgesetzt und ausgegeben.

Ungolfed:

in_str = gets

# grab strings and comments before doing the replacements
i, unparsed = 0, []
in_str.gsub!(/(\/\*|"|').*?(\*\/|"|')|\d/){|match| unparsed.push match; i += 1 }

# replaces with spaces the braces in cases where braces in places cause stasis
brace_locations = [[], [], []]
in_str.each_char.with_index do |chr, idx|
    if brace_type = '{[('.index(chr)
        brace_locations[brace_type].push idx
    elsif brace_type = '}])'.index(chr)
        if brace_locations[brace_type].length == 0
            in_str[idx] = ' '
        else
            brace_locations[brace_type].pop
        end
    end
end
brace_locations.flatten.each{|brace_location| in_str[brace_location] = ' ' }

# put the strings and comments back and print
in_str.gsub!(/\d+/){|num| unparsed[num.to_i - 1] }
puts in_str
Türknauf
quelle
Das ist sehr beeindruckend. Eine Frage jedoch: Funktioniert das noch für eine Eingabe wie (("string"/*comment*/)"string"? Wenn ich die ungolfed-Version richtig lese, ersetzen Sie Zeichenfolgen und Kommentare durch ihren Index im unparsedArray, was zu einer Substitution führen würde ((12)3und dann nach einem nicht vorhandenen Index 12(oder 11) suchen würde . Ich sehe, die Golf-Version verwendet nur shift, aber könnte es nicht immer noch ein ähnliches Problem haben?
DLosc
4

Python 3, 410 322 317

import re;a='([{';z=')]}';q=[re.findall('".*?"|/\*.*?\*/|.',input())]
while q:
 t=q.pop(0);s=[];i=0
 for x in t:
  if x in a:s+=[x]
  try:x in z and 1/(a[z.find(x)]==s.pop())
  except:s=0;break
 if[]==s:print(''.join(t));break
 while 1:
  try:
   while t[i]not in a+z:i+=1
  except:break
  u=t[:];u[i]=' ';q+=[u];i+=1

Versucht jeden möglichen Satz von Löschungen, beginnend mit kleineren, bis er einen findet, bei dem die Klammern ausgeglichen sind. (Womit ich voll richtig ausbalanciert meine: {{(})produziert ( ), nicht {(}).)

Die erste Version verwendete eine rekursive Generatorfunktion, die sehr cool, aber auch sehr lang war. Diese Version führt eine einfache Breitensuche mit einer Warteschlange durch. (Ja, es ist ein faktorieller Zeitalgorithmus. Was ist das Problem?: ^ D)

DLosc
quelle
Ich mag dieses, weil es tatsächlich die geringste Entfernung findet und korrekt verschachtelte Ausdrücke erzeugt, aber der letzte Kommentar von @vonilya legt nahe, dass die korrekte Verschachtelung nicht wichtig ist. Es ist jedoch sehr langsam, wenn viele Zahnspangen entfernt werden müssen.
rici
2

C - 406

Ein Versuch in C ohne reguläre Ausdrücke.

#define A if((d==125||d==93||d==41)
char*s;t[256];f(i,m,n,p){while(s[i]!=0){int c=s[i],k=s[i+1],v=1,d;if((c==42&&k==47)||(c==m&&i>n))return i;if(!p||p==2){if((c==39||c==34)||(c==47&&k==42)){i=f(i,c*(c!=47),i,p+1);
c=c==47?42:c;}d=c+1+1*(c>50);A){v=f(i+1,d,i,2);if(!p&&v)t[d]++;if(p==2&&v)i=v;}}d=c;A&&!p){v=!!t[c];t[c]-=v;}if(p<2)putchar(c*!!v+32*!v);i++;}return 0;}main(int c,char*v[]){s=v[1];f(0,0,0,0);}

Kompilieren und ausführen (auf einem Linux-Computer):
gcc -o Klammern brackets.c
./brackets "[(])"

In undefinierten Fällen wie [(]) wird das letzte gültige Klammerpaar zurückgegeben ()

Markuz
quelle
2

Python 3, 320

import re
O=dict(zip('([{',')]}'))
def o(s,r,m=0,t=[]):m+=re.match(r'([^][)({}/"]|/(?!\*)|/\*.*?\*/|".*?")*',s[m:]).end();return r and o(s[:m]+' '+s[m+1:],r-1,m+1,t)or(o(s,r,m+1,t+[O[s[m]]])if s[m]in O else[s[m]]==t[-1:]and o(s,r,m+1,t[:-1]))if s[m:]else not t and s
s=input();i=0;a=0
while not a:a=o(s,i);i+=1
print(a)

Wie bei der DLosc-Lösung wird hier jede mögliche Löschung untersucht, es wird jedoch eine viel schnellere rekursive Erkundungs- und Ausweichstrategie verwendet. Ich weiß, dass Geschwindigkeit im Code-Golf kein Kriterium ist und eine erschöpfende Suche auf jeden Fall exponentiell ist, aber diese kann Eingaben wie ({({({({({({({({(}}}}}}}}in ein paar Sekunden verarbeiten.

rici
quelle
Gut gespielt, gut gespielt. Ich habe es geschafft, auf 317 zu kommen, aber ich denke, Sie sollten das ziemlich leicht überstehen können. (In der Zwischenzeit arbeitet mein Programm immer noch an Ihrer Beispieleingabe ...)
DLosc
@ DLosc: Halten Sie nicht den Atem an :). Meine Maschine brauchte 58 Minuten, um die Version dieses Musters mit 6 offenen Parens zu erstellen. Um die Stase zu lösen, bevor das Universum den Hitzetod erreicht, müssen Sie die Warteschlange auswendig lernen. Andernfalls erhalten Sie eine O(n!!)Lösung, nicht O(n!). (Mein Golf ist O(n*2^n)stattdessen O(2^n), weil otatsächlich alle Muster mit bis zu rEntfernungen erzeugt werden, anstatt genau rEntfernungen. Einfach zu reparieren, aber es würde ein paar Zeichen kosten.)
rici