Bewerten Sie einen Ausdruck von ternären Operatoren

29

Betrachten wir eine Grammatik über dem Alphabet { 0, 1, ?, :} durch die definierte Produktionsregel

s → 010 ?s :s ┃ 1 ?s :s

Analysieren Sie einen aus s generierten String als Ausdruck, bei dem es sich um einen rechtsassoziativen Ausdruck ?:handelt (z. B. a?B?X:Y:c?d:e?f:gMittelwert a?(B?X:Y):(c?d:(e?f:g))), und werten Sie ihn mit der folgenden Semantik aus:

eval(0) = 0
eval(1) = 1
eval(0?a:b) = eval(b)
eval(1?a:b) = eval(a)

Wenn das Ergebnis 0 ist , geben Sie einen festen Wert aus. Wenn der Ausgang 1 ist , wird ein anderer fester Wert ausgegeben. Geben Sie in Ihrer Antwort die von Ihnen gewählten Ausgabewerte (z. B. 0/ 1oder False/ True) an.

Testfälle

0 -> 0
1 -> 1
0?0:1 -> 1
0?1:0 -> 0
1?0:1 -> 0
1?1:0 -> 1
0?1?0:1:1 -> 1
1?0?1:1:1 -> 1
1?0:1?0:1?1:1 -> 0
1?1?1:0?1?0:0:0:0 -> 1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1 -> 0
1?1?1:0?0?1:1:0?1:0:1?1?0?0:0:1?1:0:0?1?0:1:1?0:1 -> 1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1 -> 0

Regeln

  • In einigen Programmiersprachen (z. B. JavaScript / Perl / Ruby / Python's eval) dürfen keine integrierten Sprachen verwendet werden, die Zeichenfolgen als Code interpretieren und ausführen .
  • Dies vorausgeschickt , ist der Code nicht tatsächlich zu parsen und dann bewertet die Eingabezeichenfolge. Sie können jeden Ansatz wählen, um gleichwertige Ergebnisse zu erzielen, und verstoßen nicht gegen die vorherige Regel.
  • Ihr Programm wird gegen geprüft perl -le 'print eval<>'.
  • Der kürzeste Code (in Bytes) gewinnt.
Lynn
quelle
Wie wäre es mit Sprach-Built-Ins wie eval, die Strings nach einer radikalen Änderung des Strings als $ my_language-Code interpretieren?
Adám
Was ist mit Builtins, die Strings als $ some_other_language- Code interpretieren ?
Mego
@Adam Das wäre leider nicht erlaubt.
Lynn
@Mego Hmm, da gibt es eine triviale Betrugsmöglichkeit, also habe ich die Regel auf alle diese eingebauten Funktionen ausgedehnt.
Lynn
1
Im Lichte von Martins Testfällen, vielleicht wäre es einfacher, die Grammatik zu definieren S → T | T ? S : S, T → 0 | 1die Notwendigkeit zu entfernen über Assoziativität zu sprechen?
Peter Taylor

Antworten:

17

Netzhaut , 23 Bytes

r-1=+`0\?.:|1\?(.):.
$1

Probieren Sie es online! (Die erste Zeile aktiviert eine durch Zeilenvorschub getrennte Testsuite.)

Erläuterung

Es ist eigentlich ziemlich einfach. Die Eingabe wird durch wiederholtes ( +) Auswerten von Ternären, die nur Literale enthalten, auf das Ergebnis reduziert . Um sicherzustellen, dass dies rechtsassoziativ erfolgt, suchen wir nach Übereinstimmungen von rechts nach links ( r) und ersetzen nur die zuletzt gefundene Übereinstimmung ( -1=).

Die Regex selbst passt zu 0\?.:und entfernt sie (lässt nur das Zeug danach :) oder 1\?.:.ersetzt sie durch den Wert nach dem ?.

Martin Ender
quelle
Wenn der reguläre Ausdruck von rechts beginnt, sollten Sie dann nicht das 1st-Match anstelle des -1st verarbeiten?
Undichte Nonne
@LeakyNun Leider denke ich, dass ich die Übereinstimmungen storniere, bevor ich das Limit anwende.
Martin Ender
10

Haskell, 106 101 100 90 83 Bytes

Dies hängt stark von den Pattern-Matching-Fähigkeiten von Haskell ab. Zuallererst kehren wir die Zeichenfolge um, sodass wir nur nach dem ersten Vorkommen von b:a?x(das normalerweise so lautet x?a:b) suchen und es durch seinen Wert ersetzen können. Dies sorgt automatisch für die richtige Assoziativität . Hier verwenden wir x:xsMuster. Dies ist, was die Funktion ftut. Dann wenden wir uns grundsätzlich immer wieder fauf die Ausgabe an, bis wir eine einzelne Zahl (0 oder 1) übrig haben.

Danke @Lynn für 12 Bytes!

f(b:':':a:'?':x:l)|x>'0'=a:l|1>0=b:l
f(x:l)=x:f l
f x=x
until((<2).length)f.reverse
fehlerhaft
quelle
8

Brainfuck, 82 64 63 Bytes

+
[
  ,>>,>
  +++++++[<---<<-[------>>]<-]
  <<
  [
    ->[<++>[+]]
  ]
  +>[>>]
  <<<-
]
<.

Die Ausgabe ist \xfffür 0und \x00für 1. Die Brainfuck-Implementierung muss es ermöglichen, nach links von der Startzelle zu gehen.

Dies verwendet im Wesentlichen den gleichen Ansatz wie die Python- Antwort von xsot , aber die Verzweigung ist im Vergleich zu meiner ursprünglichen 82-Byte- Übermittlung wahrscheinlich schwerer nachzuvollziehen:

-
[
  +
  [
    ->,,>+++++++[<--------->-]
    <[<++>[+]]
    <
  ]
  ,->,>+++++++[<[-------<]>>-->-]
  <[<]
  <
]
>>.

(Bei dieser Lösung ist die Ausgabe \xfefür 0und \xfffür 1und eine größere Kompatibilität wird erreicht, wenn die Eingabe mit einem Zeilenumbruch endet.)

Wenn Sie sich nicht die Mühe machen müssen, die xsot-Lösung zu analysieren, lautet die Idee: Gehen Sie von links nach rechts vor. Wenn Sie sehen, 1?dann verwerfen Sie es gierig. Wenn Sie 0?dann sehen, verwerfen Sie alles zwischen diesem und dem entsprechenden :. Wenn ?das zweite Zeichen nicht angezeigt wird, beenden Sie die Schleife und drucken Sie das erste Zeichen der verbleibenden Zeichenfolge.

Die 82-Byte-Lösung spiegelt dieses Schema also ziemlich genau wider. Die innere Schleife 0?wird wie die innere Schleife von xsot behandelt. Es wird mit größter Sorgfalt vorgegangen, um in die Hauptschleife einzutreten, ohne die eingegebenen Zeichen zu überprüfen. dh wir wollen überprüfen, ob das zweite Zeichen ?nur einmal am Ende der Hauptschleife und nicht auch am Anfang ist, bevor wir in die Hauptschleife eintreten.

Die 63-Byte-Lösung kombiniert im Wesentlichen die inneren und äußeren Schleifen zu einer, was ich aufgrund der Ähnlichkeit zwischen diesen Schleifen für möglich hielt. Das Speicherlayout in der Hauptschleife könnte wie folgt beschrieben werden:

[s] d c

Dabei [x]bedeutet "Aktuelle Zelle": Der sWert beginnt als Dummy-Wert ungleich Null, der lediglich angibt, dass wir noch eine Schleife ausführen, und wird sofort mit einem Eingabezeichen (entweder 0oder 1) überschrieben . Die dZelle enthält die (negative) Tiefe, falls wir uns in der Mitte von a befinden 0?, ansonsten 0. Das cwird entweder ?oder :oder Newline oder EOF sein.

Nach der Aktualisierung von sund behandeln cwir den 0?Fall, indem wir ihn dentsprechend aktualisieren und den Zeiger anpassen. Andernfalls verwenden wir den aktuellen Wert von cals den Wert von din der nächsten Iteration oder stoppen, wenn wir fertig sind.

Mitch Schwartz
quelle
7

Python 2, 76 74 73 72 Bytes

a=`id`
for c in input()[::-1]:a=(c+a,a[ord(c)*7%9]+a[4:])[a>'?']
print a

Bei Eingabe als String-Literal zu vermeiden raw_.

Die Ausgabe erfolgt 0oder 1gefolgt von <built-in function id>.

Mitch Schwartz
quelle
1
Haha, ich habe gerade deine Antwort für b lang gelesen und wollte eine fast identische Antwort posten! Hier ist eine zusätzliche Optimierung:3>>int(c)
xsot
Möchtest du erklären, wie das funktioniert? Sieht wirklich gut aus
WorldSEnder
@WorldSEnder Ich denke, es ist die Art von Lösung, die schwierig zu finden sein kann, aber einfach zu verstehen ist, wenn man sie erst einmal sieht. Es läuft rückwärts durch die Zeichenkette und verarbeitet wiederholt die am weitesten rechts stehende Bedingung, wie es auch andere Löser getan haben.
Mitch Schwartz
Dieser `id`Trick ...! Gut gemacht :)
Lynn
5

Python 2, 89 Bytes

s=input()
while'?'<=s[1:]:
 n=s<'1'
 while n:s=s[2:];n+=-(s[1]<'?')|1
 s=s[2:]
print s[0]

Die Eingabe wird als Zeichenfolgenliteral interpretiert.

xsot
quelle
5

Schmutz , 34 31 Bytes

E=d|d\?E.E
e`\1|\1\?_.E|\0\?E._

Drucke 1für truthy Eingänge und 0für falsy diejenigen. Probieren Sie es online! Der letzte Testfall hat leider nicht genügend Speicher auf TIO.

Erläuterung

Die richtige Assoziativität bedeutet im Wesentlichen, dass in a?b:c, aimmer entweder 0oder ist1 nie ein längerer Ausdruck ist. Ich werde einfach rekursiv ein Muster definieren, das einem solchen wahrheitsgemäßen Ausdruck entspricht, und die Eingabe mit diesem vergleichen. Es ist auch unnötig zu überprüfen, ob alle :wirklich a sind :, wenn ?alle s markiert sind: Es gibt eine gleiche Anzahl von ?s und :s in der Eingabe, und wenn einige ?fälschlicherweise als a klassifiziert sind , stimmen :die entsprechenden :Werte nicht überein und die Übereinstimmung mit Grime Motor fährt zurück.

E=d|d\?E.E
E=                      Define nonterminal E (for "expression") as
  d|                     a digit, OR
    d                    a digit,
     \?                  a literal ?,
       E                 a match of E,
        .                any character (will match a :), and
         E               another match of E.
e`\1|\1\?_.E|\0\?E._
e`                      Match entire input against this pattern (truthy expression):
  \1|                    a literal 1, OR
     \1\?                a literal 1?,
         _               a recursive match of truthy expression,
          .              any character (will match a :), and
           E|            any expression, OR
             \0\?E._     the same, but with 0 in front, and _ and E swapped.
Zgarb
quelle
5

Haskell, 79 71 70 62 60 56 Bytes

Edit: Danke an @Zgarb für 3 Bytes und an @nimi für 4 Bytes!

e(x:'?':r)|a:_:s<-e r=last$e s:[a:tail(e s)|x>'0']
e x=x

Dies ist ein rekursiver Ansatz , der die Ausgaberegel "einige feste Werte" wenig missbraucht . Edit: Das Entfernen der Tupel spart nicht nur 8 Bytes, sondern liefert auch eine schönere Ausgabe: "0"oder "1".

Ungolfed-Version:

eval (x:'?':r1) = if x=='1' then (a, r3) else (b, r3)
    where (a,':':r2) = eval r1
          (b, r3)    = eval r2
eval (x:r) = (x,r)

Wie funktioniert es?
Die evalFunktion durchläuft den impliziten Baum der Ausdrücke

eval 1?0?0:1:0?1:0 -> eval 1?          :
                             eval 0?0:1 eval 0?1:0

und gibt ein Tupel des Formulars zurück (result, rest).
Das erste Muster (x:'?':r1)passt xzu '1'und r1zu "0?0:1:0?1:0". Rekursives Anwenden evalauf r1wertet den Unterausdruck aus 0?0:1und gibt ihn zurück (0,":0?1:0"). Das Anpassen an das Muster (a,':':r2)ergibt a=0und r2=0?1:0. Diese Unterformel wird auch rekursiv ausgewertet, so dass b='0'und r3="". Überprüfen Sie, ob xist '1'oder '0'und Rückkehr entweder (a, r3)oder (b, r3).

Laikoni
quelle
1
Netter Ansatz! Würde x>'0'anstelle von arbeiten x=='1'?
Zgarb
Danke, daran habe ich beim Umgang mit Zeichen nicht gedacht.
Laikoni
1
Ich denke , Sie können auch ersetzen ':'durch _.
Zgarb
Ja, dann funktioniert der Code auch für beliebige Trennzeichen statt nur :. Danke noch einmal!
Laikoni
1
Nett! Sie können das if .. then .. elsemit ersetzen last$e s:[a:tail(e s)|x>'0'].
Nimi
3

JavaScript (ES6), 53 Byte

f=s=>s[1]?f(s.replace(/0\?.:|1\?(.):.(?!\?)/,"$1")):s

Gibt 0oder 1für eine gültige Eingabe zurück; hängt bei ungültiger Eingabe Erläuterung: Da das Umkehren eines Strings in JavaScript umständlich ist, wurde bei meinem ersten 71-Byte-Versuch ein negativer Lookahead für a verwendet, ?der ansonsten die Assoziativität stören würde:

f=s=>s[1]?f(s.replace(/(.)\?(.):(.)(?!\?)/,(_,a,b,c)=>+a?b:c)):s

Da dies etwas lang war, fragte ich mich, ob ich die Dinge verbessern könnte, indem ich die Entscheidungsfindung in den regulären Ausdruck einbeziehe. Wie sich herausstellte, war es kein sofortiger Erfolg, da es auch 71 Bytes dauerte:

f=s=>s[1]?f(s.replace(/0\?.:(.)(?!\?)|1\?(.):.(?!\?)/,"$1$2")):s

Dann fiel mir ein, dass 0?0:und 0?1:sind immer no-ops, ohne Sorge um die Assoziativität. Das hat mir fast 25% gespart.

Neil
quelle
Ihr Codeblock oben fehlt f=. Ich habe nicht geprüft, ob Ihre Byteanzahl dies berücksichtigt oder nicht.
Patrick Roberts
@PatrickRoberts Ich mache das für immer, weil ich aus dem Protokoll kopiere, das nur das Ergebnis der Zuweisung anzeigt (was für nicht rekursive Funktionen natürlich ausreicht).
Neil
@Neil Sie können von der Protokolleingabe anstelle der Ausgabe kopieren
ASCII
@MarsUltor Die Log-Eingabe beinhaltet die Eingabeaufforderung, die ich dann unbedingt ausschließen muss. Dies ist ein umständlicher zusätzlicher Schritt für nicht rekursive Funktionen, weshalb ich standardmäßig aus der Ausgabe kopiere.
Neil
3

Perl, 32 + 1 ( -pFlag) = 33 Bytes

Voller Dank an @Mitch Swartch , da seine Lösung 14 Byte kürzer war als meine!
Danke auch an @Neil, der eine Lösung vorgeschlagen hat, die 1 Byte länger ist als Mitch.

s/.*\K(0\?..|1\?(.)..)/\2/&&redo

Benötigt -pFlagge, sowie -M5.010oder -Ezu laufen. Zum Beispiel :

perl -pE 's/.*\K(0\?..|1\?(.)..)/\2/&&redo' <<< "0
0?0:1
0?1?0:1:1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1"

Erklärungen : Es reduziert im Grunde genommen die Blöcke von a?b:c(beginnend vom Ende, um sicher zu gehen, dass nichts ?folgt) in boder cabhängig von der Wahrheit von a, immer und immer wieder, bis der String nur noch 1oder enthält 0.

Dada
quelle
Zählt das -nicht zu deiner Punktzahl? Hrm. Interessant ... Gute Antwort!
BürgermeisterMonty
@MayorMonty Für einen 1-Liner können Sie ihn in der Befehlszeile aufrufen, indem Sie einen Wert perl -e '<code>'hinzufügen, der pnur 1 Byte kostet perl -pe '<code>'.
Neil
@ Neil Ahh, das macht Sinn
MayorMonty
Eigentlich muss man den String nicht umkehren, man kann nur negativ nachschauen ?, ich konnte das auf diese Weise auf 34 Bytes reduzieren.
Neil
Hier ist ein 32 + 1:s/.*\K(1\?(.)..|0\?..)/\2/&&redo
Mitch Schwartz
2

Python 3, 93 69 Bytes

def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r

Eingabe ist die Zeichenfolge als Liste von Zeichen, Ausgabe ist entweder "0"oder"1"

>>>f(list("0?0:1"))
<<<"1"

Ungolfed-Version:

def parse(s):
    predicate = s.pop(0)
    if s and s.pop(0) == '?':
        left, right = parse(s), parse(s)
        if predicate == '0':
            return right
        return left
    return predicate

Noch ein Versuch, aber mit deutlich mehr Bytes:

i=input()[::-1]
a=[i[0]]
for o,z in zip(i[1::2],i[2::2]):a+=[z]if o<'?' else[[a.pop(),a.pop()][z>'0']]
print(a[0])
WorldSEnder
quelle
Ihre Antwort kann eine Funktion sein - Sie können die zweite Zeile entfernen.
Lynn
Dies ist eindeutig ungetestet, da es die Testfälle nicht besteht und die ungolfed Version einen Laufzeitfehler liefert. Ihre Grundidee ist jedoch gut. Mit einigen Anpassungen erhalte ich 68 in Python 2 und 69 in Python 3.
Mitch Schwartz
1
Nun, ich denke, es ist sinnvoller für mich, Ihnen die Antwort zu geben, als sie in meine eigene zu ändern (da ich nicht über diese Art von Ansatz nachgedacht habe, bevor ich Ihre Antwort gesehen habe) oder herumzusitzen und zu warten, während Ihre Antwort fehlerhaft ist. Hier ist der 68, den ich erwähnt habe def f(s):x=s.pop(0);return[]<s<s.pop(0)>'>'and(f(s),f(s))[x<'1']or x, und für Python 3 mit geringem Bearbeitungsabstand zu Ihrem gibt es ihn def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r.
Mitch Schwartz
Vielen Dank @MitchSchwartz, ziemlich genau von rechts, anstatt von links, gotcha
WorldSEnder
1
Ansonsten links statt rechts ~~~
WorldSEnder
1

SED, 75 74 68 (40 + 1 für -r) 41

:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t
Riley
quelle
Sie können dies wahrscheinlich mit @ MitchSchwartzs Trick in seinem Kommentar reduzieren , obwohl Sie möglicherweise verwenden müssen(.*) einen zusätzlichen Ersatzbegriff und hinzufügen müssen.
Neil
@Neil, du könntest Recht haben, aber ich kann nicht herausfinden, wie es funktioniert.
Riley
Ich habe es im Chat geschrieben, da die Formatierung in einem Kommentar verwirrend sein kann: chat.stackexchange.com/transcript/message/31709640#31709640
Mitch Schwartz
@MitchSchwartz Heh, funktionieren leere Etiketten? Aber ich denke du meintest \3statt \2. Sie können auch die Zeilen mit verbinden ;, um zu erhalten :;s/(.*)(1\?(.):.|0\?.:)/\1\3/;t.
Neil
@Neil hatte ich \3also das heißt ich habe versehentlich eine Vorgängerversion kopiert. Ich kenne mich mit Semikolons aus. Aber igitt, warum solltest du Semikolons verwenden?
Mitch Schwartz
0

Bash + GNU-Dienstprogramme, 42

rev|sed -r ':
s/(.):.\?0|.:(.)\?1/\1\2/
t'

Eine ähnliche Idee wie bei den meisten anderen Mustervergleichsantworten.

Ideone .

Digitales Trauma
quelle
In dem 0Fall, dass Sie 5 Bytes sparen, müssen Sie das erste Zeichen nicht erfassen .
Neil