Erstellen Sie einen Booleschen Parser (Fortsetzung)

8

Fortsetzung dieser Herausforderung, weil der Autor weg ist und die Frage geschlossen ist.


Sie müssen lediglich einen booleschen Parser erstellen.


Boolesche Ausdrücke haben, falls Sie noch nichts davon gehört haben, zwei Eingänge und einen Ausgang.

In der Booleschen Arithmetik gibt es vier "Tore", nämlich:

  • ODER (dargestellt durch |) (binärer Operator zwischen Argumenten)
  • UND (dargestellt durch &) (binärer Operator zwischen Argumenten)
  • XOR (dargestellt durch ^) (binärer Operator zwischen Argumenten)
  • NICHT (dargestellt durch !) (unärer Operator, Argument rechts)

Diese Gatter arbeiten mit ihren Eingängen, die entweder wahr (dargestellt durch 1) oder falsch (dargestellt durch 0) sind. Wir können die möglichen Eingaben ( Aund Bin diesem Fall) und die Ausgaben ( O) unter Verwendung einer Wahrheitstabelle wie folgt auflisten:

XOR
A|B|O
-----
0|0|0
0|1|1
1|0|1
1|1|0

OR
A|B|O
-----
0|0|0
0|1|1
1|0|1
1|1|1

AND
A|B|O
-----
0|0|0
0|1|0
1|0|0
1|1|1

NOT
A|O
---
0|1
1|0

Eine Beispieleingabe wäre 1^((1|0&0)^!(1&!0&1)), die Folgendes auswerten würde:

 1^((1|0&0)^!(1&!0&1))
=1^(( 1 &0)^!(1&!0&1))
=1^(   0   ^!(1&!0&1))
=1^(   0   ^!(1& 1&1))
=1^(   0   ^!(  1 &1))
=1^(   0   ^!    1   )
=1^(   0   ^    0    )
=1^0
=1

Die Ausgabe wäre 1.

Einzelheiten

  • Wie im Beispiel zu sehen ist, gibt es keine Reihenfolge der Prävalenz. Alle werden von links nach rechts ausgewertet, außer in Klammern, die zuerst ausgewertet werden sollten.
  • Die Eingabe enthält nur ()!^&|01.
  • Sie können ein beliebiges 8-Byte-Zeichen auswählen, um die oben genannten 8 Zeichen zu ersetzen. Sie müssen jedoch eine 1-zu-1-Zuordnung aufweisen und angegeben werden.
  • Insbesondere evaldarf die Funktion nicht für Zeichenfolgen verwendet werden, die von der Eingabe abgeleitet wurden . Insbesondere können die Funktion input(oder das Äquivalent in der Sprache) und jede Funktion, die sie aufruft, nicht von verwendet werden eval. Sie können das auch nicht inputin Ihre Zeichenfolge innerhalb der verketten eval.

Wertung

Das ist . Die kürzeste Lösung in Bytes gewinnt.

Undichte Nonne
quelle
Cheddar hat eine integrierte Funktion zum Generieren eines Aufrufstapels aus einer Zeichenfolge. Ist das auch nicht zulässig?
Downgoat
2
Könnten Sie weitere Testfälle hinzufügen?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Welchen Testfall möchten Sie sehen?
Undichte Nonne
@ KennyLau Ein paar komplizierte, idk
Conor O'Brien
Gibt es eine Bedingung, die der Testfall nicht behandelt hat? Ich denke, es hat schon so ziemlich alles erledigt.
Undichte Nonne

Antworten:

6

JavaScript (ES6) 116 Bytes

edit thx @ user81655 für 3 Bytes gespeichert und ein Fehler gefunden

s=>[...s].map(x=>x<2?v=m[x]:x<6?m=[,,m[1]+m[0],0+v,v+1,v+(1^v)][x]:x>6?v=o.pop()[v]:m=o.push(m)&&a,o=[v=a=m='01'])|v

Wahrscheinlich nicht der beste Ansatz, aber keine Eval- und Booleschen Operatoren, nur Wahrheitstabellen.

Verwendeter Charakter:

  • ! -> 2
  • & -> 3
  • | -> 4
  • ^ -> 5
  • (-> 6
  • ) -> 7

Prüfung

f=s=>[...s].map(x=>x<2?v=m[x]:x<6?m=[,,m[1]+m[0],0+v,v+1,v+(1^v)][x]:x>6?v=o.pop()[v]:m=o.push(m)&&a,o=[v=a=m='01'])|v

console.log=(...x)=>O.textContent+=x+'\n'

test=[ ["1^((1|0&0)^!(1&!0&1))",1] 
// be more careful, step by step
,["0&0",0],["0&1",0],["1&0",0],["1&1",1]
,["0|0",0],["0|1",1],["1|0",1],["1|1",1]
,["0^0",0],["0^1",1],["1^0",1],["1^1",0]
,["0&!0",0],["0&!1",0],["1&!0",1],["1&!1",0]
,["0|!0",1],["0|!1",0],["1|!0",1],["1|!1",1]
,["0^!0",1],["0^!1",0],["1^!0",0],["1^!1",1]
,["!0&0",0],["!0&1",1],["!1&0",0],["!1&1",0]
,["!0|0",1],["!0|1",1],["!1|0",0],["!1|1",1]
,["!0^0",1],["!0^1",0],["!1^0",0],["!1^1",1]
// nand, nor
,["!(0&0)",1],["!(0&1)",1],["!(1&0)",1],["!(1&1)",0]
,["!(0|0)",1],["!(0|1)",0],["!(1|0)",0],["!(1|1)",0]
     ]

test.forEach(([x,check]) => {
  // remap operators (each one on its line, just to be clear)
  var t = x.replace(/!/g,"2")
  t = t.replace(/&/g,"3")
  t = t.replace(/\|/g,"4")
  t = t.replace(/\^/g,"5")
  t = t.replace(/\(/g,"6")
  t = t.replace(/\)/g,"7")
  r = f(t)
  console.log((r==check?'OK':'KO')+' '+x +' '+r)
})
<pre id=O></pre>

edc65
quelle
1
Meinten Sie wirklich x>7?
Neil
r=f(x.replace(/./g,c=>"01!&|^()".indexOf(c)))
Neil
@Neil Ich werde überprüfen, danke. Natürlich wenn> 6
edc65
@Neil Ich füge Testfälle hinzu. Ich bin mir ziemlich sicher, dass angesichts der Assoziativität und Kommutativität der Operatoren das NOT immer funktionieren sollte
edc65
Ich habe einige Zeit 0|!0gebraucht , um herauszufinden, warum (sagen wir) funktioniert, aber jetzt habe ich meine Gegenstimme.
Neil
5

Netzhaut, 49 Bytes

+`(<1>|!0|1[ox]0|0[ox]1|1[ao]1)|<0>|!1|\d\w\d
$#1

Ich habe keine Ahnung, wie es so kurz gekommen ist.

Zeichenzuordnung:

^ -> x
& -> a
| -> o
( -> <
) -> >

1, 0Und !bleiben unverändert.

Dies funktioniert , indem alle truthy Ausdrücke ersetzt (single 1in Klammern !0, 1&1, 1^0, 0|1, etc.) mit 1, und alle anderen (Single 0in Klammern !1, 1&0, 1^1, 0|0, etc.) mit 0.

Probieren Sie es online aus!
Probieren Sie es online mit automatischer Zeichenzuordnung!

daavko
quelle
3

grep + shell utils, 131 bytes

rev|grep -cP '^(((0|R((?9)(x(?1)|a(?4))|(?2)([oxa](?4)|a(?1)|))L|(1|R(?1)L)!)(!!)*)[xo](?1)|(1|R(?1)L|(?2)!)([ao](?1)|[xo](?4)|))$'

Die folgenden Zeichen werden umbenannt:

( -> L
) -> R
| -> o
& -> a
^ -> x

Ich habe versucht, eine grep-Lösung zu schreiben, habe jedoch festgestellt, dass sie mit den linksassoziativen Infix-Operatoren nicht gut funktioniert. Ich brauchte ein Muster wie (Kette von Operatoren) = (Kette von Operatoren) (binäre Operation) (einzelner Operand), aber dieses enthält eine mögliche unendliche Rekursion, daher weigert sich grep, es auszuführen. Aber ich bemerkte, dass ich rechtsassoziative Operatoren analysieren konnte . Dies machte dem !Bediener Schmerzen, aber es war immer noch möglich. Also habe ich einen regulären Ausdruck für die Berechnung rückwärts gerichteter boolescher Ausdrücke erstellt und die Eingabe durchgeschickt rev. Der reguläre Ausdruck selbst, der den wahren Ausdrücken entspricht, beträgt 116 Byte.

TODO: Wählen Sie verschiedene Zeichen für die Eingabe aus, damit ich alle verwendeten Gruppen von Operatoren mit integrierten Zeichenklassen unterscheiden kann.

Feersum
quelle
Was heißt (?9)das
Undichte Nonne
Dies bedeutet, dass Sie die 9. Erfassungsgruppe nehmen und erneut ausführen (im Unterschied dazu \9würde dies bedeuten, dass sie mit der 9. Erfassungsgruppe übereinstimmt). So (\d)\1stimmt beispielsweise dieselbe Ziffer zweimal (\d)(\?1)überein , während zwei Ziffern übereinstimmen.
Neil
2

Python, 210 Bytes

from operator import*;
def t(o):c=o.pop(0);return ord(c)-48if c in"01"else[p(o),o.pop(0)][0]if"("==c else 1-t(o)
def p(o):
 v=t(o)
 while o and")"!=o[0]:v=[xor,or_,and_]["^|&".index(o.pop(0))](v,t(o))
 return v

Wirklich schlechter rekursiver Abstieg, ich erwarte, dass dies sofort geschlagen wird.

orlp
quelle
2

Mathematica, 139 129 Bytes

a=StringPartition;StringReplace[#,{"(0)0&00&11&00|00^01^1"~a~3|"!1"->"0","(1)1&10|11|01|10^11^0"~a~3|"!0"->"1"},1]&~FixedPoint~#&

Eine einfache Lösung zum Ersetzen von Saiten schneidet weitaus besser ab, als ich es mir erhofft hatte.

LegionMammal978
quelle
2

JavaScript ES6, 223 Bytes

x=>(Q=[],S=[],[...x].map(t=>{q=+t&&Q.push(t);if(t==")")while((a=S.pop())!="(")Q.push(a);else if(!q)S.push(t)}),k=[],p=_=>k.pop(),Q.concat(S.reverse()).map(e=>k.push(+e||e<"#"?1-p():e<"'"?p()&p():e<","?p()|p():p()^p())),p())

Verwendet einen Rangierplatzalgorithmus.

x=>(Q=[],S=[],[...x].map(t=>{q=+t&&Q.push(t);if(t==")")while((a=S.pop())!="(")Q.push(a);else 
if(!q)S.push(t)}),k=[],p=_=>k.pop(),Q.concat(S.reverse()).map(e=>k.push(+e||e<"#"?1-p():e<"'"
?p()&p():e<","?p()|p():p()^p())),p())

Verwendet +für OR, !für Negation, ^für XOR und &für und. 0und 1werden für ihre jeweiligen Werte verwendet. Sicher, ich könnte ein bisschen Golf spielen, indem ich die Betreibernummern mache, aber ich gewinne den JavaScript-Preis nicht, selbst wenn ich das tue, also dachte ich, ich würde es zumindest etwas lesbar und korrekt machen.

Conor O'Brien
quelle
1

C 247

Golf:

b(char*s){int i,j,k,l;if(*s==40){for(j=i=1;i+=s[++j]==41?-1:s[j]==40?1:0,i;);s[j++]=0;b(s+1);sprintf(s,"%s%s",s+1,s+j);}!s[1]?:(b(s+1),i=*s,j=1,k=s[1],i>47&i<50?:(s[1]=i==33?(j=0,k^1):(l=s[-1],i==38?k&l:i==94?k^l|'0':k|l),sprintf(s-j,"%s",s+1)));}

Ungolfed, mit main()(nimmt Ausdruck als 1. Argument). Die Golfversion hat keine Debugging-Drucke und verwendet zweistellige ASCII-Codes anstelle von Zeichenliteralen ( 40 == '('). Ich hätte einige Zeichen durch Zuordnung ()|^&!zu speichern können 234567- dies hätte viele Manipulationen und Tests nach dem Subtrahieren 48von jedem einfacher gemacht .

char*z;                 // tracks recursion depth; not used in golfed version
b(char*s){
    int i,j,k,l;
    printf("%u> '%s'\n", s-z, s);
    if(*s=='('){        // handles parenthesis
        for(j=i=1;i+=s[++j]==')'?-1:s[j]=='('?1:0,i;);
        s[j++]=0;
        b(s+1);         // s+1 to s+j gets substituted for its evaluation
        sprintf(s,"%s%s",s+1,s+j);
    }
    !s[1]?:(            // if 1 char left, return
        b(s+1),         // evaluate rest of expression
        i=*s,
        j=1,
        k=s[1],
        printf("%u: '%c'\n", s-z, i),
        i>47&i<50?:(    // if 0 or 1, skip substitution
                        // otherwise, perform boolean operation
            s[1]=i=='!'?(j=0,k^1):(l=s[-1],i=='&'?k&l:i=='|'?k|l:k^l|'0'),
                        // and replace operation with result
            sprintf(s-j,"%s",s+1),printf("%u= '%s'\n", s-z, s-j)));
    printf("%u< '%s'\n", s-z, s);
}
int main(int argc, char **argv){
    char *s;    
    sscanf(argv[1],"%ms",&s);
    z=s;
    b(s);
    printf("%s => %s\n", argv[1], s);
}
Tucuxi
quelle
+1 für for(j=i=1;i+=s[++j]==')'?-1:s[j]=='('?1:0,i;);.
Undichte Nonne
1

Java, 459 Bytes

String p(String s){int x,y;while((y=s.indexOf("b"))>=0){x=s.lastIndexOf("a",y);s=s.replaceAll(s.subString(x,y+1),p(s.subString(x+1,y)));}String t,a="1",b="0";while(s.indexOf("!")>=0){s=s.replaceAll("!0",a);s=s.replaceAll("!1",b);}while(s.length()>1){t=s.subString(0,3);if(t.charAt(1)=='l')s=s.replaceFirst(t,t.equals("0l0")?b:a);else if(t.charAt(1)=='&')s=s.replaceFirst(t,t.equals("1&1")?a:b);else s=s.replaceFirst(t,t.charAt(0)==t.charAt(2)?b:a);}return s;}

AND ist &

ORist l(Kleinbuchstabe L)

XORist x(oder eine andere Figur , die schön zu spielen geschieht String‚s Methoden wie String.replaceAll(...))

NOT ist !

( ist a

) ist b

Hier ist eine besser lesbare Version:

String parseBoolean( String str ) {
    int start,end;
    //look for matching brackets ab
    while( (end = str.indexOf( "b" )) >= 0 ) {
        start = str.lastIndexOf( "a", end );
        str = str.replaceAll( str.subString( start, end + 1 ), parseBoolean( str.subString( start + 1, end ) ) );
    }
    String temp, one = "1", zero = "0";
    //handle all the !'s
    while( str.indexOf( "!" ) >= 0 ) {
        str = str.replaceAll( "!0", one );
        str = str.replaceAll( "!1", zero );
    }
    //handle the remaining operators from left to right
    while( str.length() > 1 ){
        temp = str.subString( 0, 3 );
        //check for OR
        if( temp.charAt( 1 ) == 'l' )
            str = str.replaceFirst( temp, temp.equals( "0l0" ) ? zero : one );
        //check for AND
        else if(t.charAt(1)=='&')
            str = str.replaceFirst( temp, temp.equals( "1&1" ) ? one : zero );
        //handle XOR
        else 
            str = str.replaceFirst( temp, temp.charAt( 0 ) == temp.charAt( 2 ) ? zero : one );
    }
    return str;
}

Probieren Sie es online aus

Jack Ammo
quelle
1
Wie immer beim Java-Golfen ist es meine Lieblingsbeschäftigung, Zeichenliterale durch ihre ganzzahligen Gegenstücke zu ersetzen, wo immer ich kann. In diesem Fall wäre dies sowohl in den regulären indexOfs- als auch in den charAt-Vergleichen der Fall. Wenn Sie das Zeichen für AND in "n" anstelle von "&" ändern, können Sie <oder> -Anweisungen mit einzelnen ifs verwenden, wenn Sie prüfen, für welche Operation Sie arbeiten müssen.
Blau
1
Oh, noch eine Sache. Sie können den Aufruf von replaceAll in der zweiten while-Schleife verdoppeln und diese Klammern speichern.
Blau
@Blue Ich vergesse immer, Literale in Ints zu schreiben, danke. Ich bin mir nicht ganz sicher, was du damit meinst, wenn du den Ersetzungsaufruf für die! Verdoppelst.
Jack Ammo
s = s.replaceAll ("! 0", a) .replaceAll ("! 1", b);
Blau
1

Java, 218

Verwendet Pattern Matching, vermeidet jedoch das Ersetzen meines vorherigen fehlgeschlagenen Java-Versuchs (scharfe Augen, @Kenny Lau !).

Golf:

String e(String s){Matcher m=Pattern.compile("(<1>|1o[01]|0o1|1a1|1x0|0x1|n0)|(<0>|0o0|0a[01]|1a0|1x1|0x0|n1)").matcher(s);return m.find()?e(s.substring(0,m.start())+(m.group(1)==null?"0":"1")+s.substring(m.end())):s;}

Ungolfed, liest Eingaben von Argumenten und wendet das Mapping oaxnfür |&^!und <>für an ():

import java.util.regex.*;

public class B{
    String e(String s){
        System.out.println(s);
        Matcher m=Pattern
            .compile(
                "(<1>|1o[01]|0o1|1a1|1x0|0x1|n0)|"+
                "(<0>|0o0|0a[01]|1a0|1x1|0x0|n1)")
            .matcher(s);
        return m.find()?e(s.substring(0,m.start())+(m.group(1)==null?"0":"1")+s.substring(m.end())):s;
    }

    public static String map(String s, String ... replacements) {
        for (String r: replacements) {
            s = s.replace(r.substring(0,1), r.substring(1));
        }
        return s;
    }

    public static void main(String ... args){
        for (String s: args) System.out.println(new B().e(
            map(s,"(<",")>","|o","&a","!n","^x")
        ));
    }
}

Java m.group(i)sagt Ihnen, welche Gruppe übereinstimmt; Die erste Gruppe ist für wahre Substitutionen und die zweite für falsche. Dies wird in strikter Reihenfolge von links nach rechts wiederholt, bis keine Substitutionen mehr durchgeführt werden.

Tucuxi
quelle