Crear un analizador booleano (continuación)

8

Continuación de este desafío porque el autor se ha ido y la pregunta está cerrada.


Lo que debe hacer es crear un analizador booleano.


Las expresiones booleanas, en caso de que aún no haya oído hablar de ellas, tienen dos entradas y una salida.

Hay cuatro "puertas" en la aritmética booleana, a saber:

  • O (representado por |) (operador binario, entre argumentos)
  • AND (representado por &) (operador binario, entre argumentos)
  • XOR (representado por ^) (operador binario, entre argumentos)
  • NOT (representado por !) (operador unario, argumento a la derecha)

Estas puertas operan en sus entradas que son verdaderas (representadas por 1) o falsas (representadas por 0). Podemos enumerar las posibles entradas ( Ay Ben este caso) y las salidas ( O) usando una tabla de verdad de la siguiente manera:

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

Un ejemplo de entrada sería 1^((1|0&0)^!(1&!0&1)), que se evaluaría para:

 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

La salida sería 1.

Detalles

  • Como se ve en el ejemplo, no hay un orden de prevalencia. Todos se evalúan de izquierda a derecha, excepto cuando están entre paréntesis, que deben evaluarse primero.
  • La entrada solo contendrá ()!^&|01.
  • Puede elegir cualquier carácter de 8 bytes para reemplazar los 8 caracteres anteriores, pero deben tener una asignación de 1 a 1 y deben indicarse.
  • Específicamente, evalno se permite usar la función en ninguna cadena derivada de la entrada . Específicamente, la función input(o el equivalente en el lenguaje) y cualquier función que lo llame no puede ser utilizada por eval. Tampoco puede concatenar inputen su cadena dentro de eval.

Puntuación

Este es el . La solución más corta en bytes gana.

Monja permeable
fuente
¿Cheddar tiene una función incorporada para generar una pila de llamadas desde una cadena?
Downgoat
2
¿Podría agregar más casos de prueba?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ ¿Qué caso de prueba le gustaría ver?
Monja Leaky
@KennyLau Algunos complicados, idk
Conor O'Brien
¿Hay alguna condición que el caso de prueba no haya manejado? Creo que ya manejó todo.
Leaky Nun

Respuestas:

6

JavaScript (ES6) 116 bytes

edite thx @ user81655 por 3 bytes guardados y se encontró un error

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

Probablemente no sea el mejor enfoque, pero no hay operadores eval y no booleanos, solo tablas de verdad.

Carácter usado:

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

Prueba

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
fuente
1
¿Realmente quisiste decir x>7?
Neil
r=f(x.replace(/./g,c=>"01!&|^()".indexOf(c)))
Neil
@Neil lo comprobaré, gracias. Por supuesto si> 6
edc65
@Neil Estoy agregando casos de prueba. Estoy bastante seguro de que dada la asociatividad y la conmutatividad de los operadores, el NOT siempre debería funcionar
edc65
Me tomó algo de tiempo entender por qué (por ejemplo) 0|!0funciona, pero ahora sí, tengo mi voto a favor.
Neil
5

Retina, 49 bytes

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

No tengo idea de cómo salió tan corto.

Mapeo de personajes:

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

1, 0y no !se modifican.

Esto funciona mediante la sustitución de todas las expresiones Truthy (solo 1entre paréntesis, !0, 1&1, 1^0, 0|1, etc.) con 1, y todos los demás (single 0paréntesis, !1, 1&0, 1^1, 0|0, etc.) con 0.

Pruébalo en línea!
¡Pruébelo en línea con el mapeo automático de caracteres!

daavko
fuente
3

grep + utilidades de shell, 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)|))$'

Los siguientes caracteres cambian de nombre:

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

Comencé a tratar de escribir una solución grep, pero descubrí que no funcionaba bien con los operadores de infijo asociativo a la izquierda. Necesitaba tener un patrón como (cadena de operadores) = (cadena de operadores) (binario op) (operando único), pero esto contiene una posible recursión infinita, por lo que grep se niega a ejecutarlo. Pero noté que podía analizar operadores asociativos correctos. Esto hizo que el !operador fuera un dolor, pero aún era posible. Así que hice una expresión regular para calcular expresiones booleanas hacia atrás y envié la entrada rev. La expresión regular en sí, que coincide con expresiones verdaderas, es de 116 bytes.

TODO: elija diferentes caracteres para la entrada para que pueda distinguir todos los grupos de operadores utilizados con clases de caracteres incorporadas.

Feersum
fuente
Que (?9)significa
Leaky Nun
Significa tomar el noveno grupo de captura y volver a ejecutarlo (a diferencia de \9lo que significaría hacer coincidir lo que coincidió con el noveno grupo de captura). Entonces, por ejemplo, (\d)\1coincide con el mismo dígito dos veces, mientras que (\d)(\?1)coincide con cualquiera de los dos dígitos.
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

Descenso recursivo realmente malo, espero que esto sea superado en un instante.

orlp
fuente
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~#&

Una solución simple de reemplazo de cadenas tiene un puntaje mucho mejor de lo que esperaba.

LegionMammal978
fuente
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())

Utiliza un algoritmo de patio de maniobras.

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())

Usos +para OR, !para negación, ^para XOR y &para y. 0y 1se usan para sus respectivos valores. Claro, podría jugar golf haciendo los números de los operadores, pero no estoy ganando el premio JavaScript, incluso si lo hago, así que pensé que sería al menos algo legible y correcto.

Conor O'Brien
fuente
1

C, 247

Golfizado:

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)));}

Sin golf, con main()(toma la expresión como 1er argumento). La versión de golf no tiene printfs de depuración y utiliza códigos ascii de 2 dígitos en lugar de literales char ( 40 == '('). Podría haber guardado algunos caracteres asignándolos ()|^&!a 234567- esto habría facilitado muchas manipulaciones y pruebas después de restar 48de cada una.

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
fuente
+1 para for(j=i=1;i+=s[++j]==')'?-1:s[j]=='('?1:0,i;);.
Leaky Nun
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 es &

ORes l(L minúscula)

XORes x(o cualquier otro personaje que juegue bien con Stringmétodos como String.replaceAll(...))

NOT es !

( es a

) es b

Aquí hay una versión más legible:

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;
}

pruébalo en línea

Jack munición
fuente
1
Como siempre con el golf Java, lo que más me gusta hacer es reemplazar los literales char con sus homólogos enteros siempre que pueda. En este caso, eso estaría en las comparaciones indexOfs regulares y charAt. Además, si cambia el carácter de AND a "n" en lugar de "&", puede usar sentencias <o> con ifs individuales al verificar qué operación necesita hacer.
Azul
1
Oh, una cosa mas. Puede duplicar la llamada para reemplazar All en el segundo ciclo while, lo que también le ahorrará esos corchetes.
Azul
@Blue Siempre me olvido de los literales char a ints, gracias. No estoy muy seguro de lo que quieres decir al doblar en la llamada de reemplazo. ¡Todos!
Jack Ammo
s = s.replaceAll ("! 0", a) .replaceAll ("! 1", b);
Azul
1

Java, 218

Utiliza la coincidencia de patrones, pero evita los reemplazos fuera de orden de mi intento fallido de Java anterior (¡ojos agudos allí, @Kenny Lau !).

Golfizado:

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, lee la entrada de argumentos y aplica el mapeo oaxnpara |&^!y <>para ():

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)te dice qué grupo coincidió; el primer grupo es para sustituciones verdaderas y el segundo para falsas. Esto se repite en estricto orden de izquierda a derecha hasta que no se realicen sustituciones.

tucuxi
fuente