Criar um analisador booleano (continuação)

8

Continuação deste desafio porque o autor se foi e a pergunta está encerrada.


O que você precisa fazer é criar um analisador booleano.


Expressões booleanas, caso você ainda não as tenha ouvido, têm duas entradas e uma saída.

Existem quatro "portas" na aritmética booleana, a saber:

  • OR (representado por |) (operador binário, entre argumentos)
  • AND (representado por &) (operador binário, entre argumentos)
  • XOR (representado por ^) (operador binário, entre argumentos)
  • NOT (representado por !) (operador unário, argumento à direita)

Esses portões operam em suas entradas que são verdadeiras (representadas por 1) ou falsas (representadas por 0). Podemos listar as entradas possíveis ( Ae B, neste caso) e as saídas ( O) usando uma tabela verdade da seguinte maneira:

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

Um exemplo de entrada seria 1^((1|0&0)^!(1&!0&1)), que seria avaliado 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

A saída seria 1.

Detalhes

  • Como visto no exemplo, não há ordem de prevalência. Todos são avaliados da esquerda para a direita, exceto quando entre parênteses, que devem ser avaliados primeiro.
  • A entrada conterá apenas ()!^&|01.
  • Você pode escolher qualquer caractere de 8 bytes para substituir os 8 caracteres acima, mas eles devem ter um mapeamento de 1 para 1 e devem ser indicados.
  • Especificamente, a função evalnão pode ser usada em nenhuma sequência derivada da entrada . Especificamente, a função input(ou o equivalente no idioma) e qualquer função que a chama não podem ser usadas eval. Você também não pode concatenar o inputem sua string dentro do eval.

Pontuação

Isso é . A solução mais curta em bytes vence.

Freira Furada
fonte
O Cheddar foi incorporado para gerar uma pilha de chamadas a partir de uma string. Isso também não é permitido?
Downgoat
2
Você poderia adicionar mais alguns casos de teste?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Que caso de teste você gostaria de ver?
Leaky Nun
@KennyLau Alguns complicados, idk
Conor O'Brien
Existe alguma condição que o caso de teste não tratou? Eu acho que já lidou com tudo.
Leaky Nun

Respostas:

6

JavaScript (ES6) 116 bytes

editar thx @ user81655 por 3 bytes salvos e um erro encontrado

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

Provavelmente não é a melhor abordagem, mas nenhum operador avaliador e booleano, apenas tabelas verdadeiras.

Personagem usado:

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

Teste

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
fonte
1
Você realmente quis dizer x>7?
Neil
r=f(x.replace(/./g,c=>"01!&|^()".indexOf(c)))
Neil
@ Neil Vou verificar, obrigado. É claro que se> 6
edc65
@ Neil Estou adicionando casos de teste. Tenho certeza de que, dada a associatividade e comutatividade dos operadores, a não deve sempre trabalho
edc65
Levei algum tempo para descobrir por que (digamos) 0|!0funciona, mas agora eu faço, tenho meu voto positivo.
Neil
5

Retina, 49 bytes

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

Não tenho idéia de como saiu tão curto.

Mapeamento de caracteres:

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

1, 0E !são deixadas inalteradas.

Isso funciona através da substituição de todas as expressões truthy (única 1entre parênteses, !0, 1&1, 1^0, 0|1, etc.) com 1, e todos os outros (single 0entre parênteses, !1, 1&0, 1^1, 0|0, etc.) com 0.

Experimente online!
Experimente online com o mapeamento automático de caracteres!

daavko
fonte
3

utilitários grep + 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)|))$'

Os seguintes caracteres são renomeados:

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

Comecei a tentar escrever uma solução grep, mas descobri que ela não funcionava bem com os operadores de infixo associativos à esquerda. Eu precisava ter um padrão como (cadeia de operadores) = (cadeia de operadores) (operação binária) (operando único), mas isso contém uma possível recursão infinita, portanto o grep se recusa a executá-lo. Mas notei que podia analisar operadores associativos certos. Isso fez do !operador uma dor, mas ainda era possível. Então, criei um regex para calcular expressões booleanas anteriores e enviei a entrada através derev . O próprio regex, que corresponde a expressões verdadeiras, é de 116 bytes.

TODO: escolha caracteres diferentes para a entrada, para que eu possa distinguir todos os grupos de operadores usados ​​com classes de caracteres internas.

feersum
fonte
O que (?9)significa isso ?
Leaky Nun
Significa pegar o 9º grupo de captura e executá-lo novamente (como distinto do \9que significaria corresponder ao que o 9º grupo de captura correspondia). Por exemplo, (\d)\1corresponde ao mesmo dígito duas vezes, enquanto (\d)(\?1)corresponde a dois 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

Descida recursiva muito ruim, espero que seja batida em um piscar de olhos.

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

Uma solução simples de substituição de string tem uma pontuação muito melhor do que eu esperava.

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

Usa um algoritmo de desvio de jarda.

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

Usa +para OR, !para negação, ^para XOR e &para e. 0e 1são usados ​​para seus respectivos valores. Claro, eu poderia jogar alguns números dos operadores, mas não estou ganhando o prêmio JavaScript, mesmo que o faça, então pensei em torná-lo pelo menos um pouco legível e correto.

Conor O'Brien
fonte
1

C, 247

Golfe:

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, with main()(assume a expressão como 1º argumento). A versão golfed não possui depuração printfs e usa códigos ascii de dois dígitos em vez de char literals ( 40 == '('). Eu poderia ter salvo alguns caracteres mapeando ()|^&!para 234567- isso teria facilitado muitas manipulações e testes depois de subtraídos 48de cada um.

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
fonte
+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 é &

ORé l(L minúsculo)

XORé x(ou qualquer outro personagem que tenha um bom desempenho com Stringos métodos, como String.replaceAll(...))

NOT é !

( é a

) é b

aqui está uma versão mais legível:

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

experimente online

Jack Munição
fonte
1
Como sempre no golfe em Java, minha coisa favorita a fazer é substituir os literais de caracteres por seus pares inteiros, sempre que possível. Nesse caso, isso seria nas comparações regulares indexOfs e charAt. Além disso, se você alterar o caractere para AND para "n" em vez de "&", poderá usar as instruções <ou> com ifs únicos ao verificar para qual operação você precisa executar.
Azul
1
Oh, mais uma coisa. Você pode dobrar a chamada para substituir Tudo no segundo loop while, economizando também esses colchetes.
Azul
@ Blue, eu sempre esqueço de char literals para ints, obrigado. Não tenho muita certeza do que você quer dizer com dobrar na chamada replaceAll para os números!
Jack Ammo
s = s.replaceAll ("! 0", a) .replaceAll ("! 1", b);
Azul
1

Java, 218

Usa a correspondência de padrões, mas evita substituições fora de ordem da minha tentativa anterior de Java com falha (olhos nítidos, @Kenny Lau !).

Golfe:

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

Sem jogar, lê a entrada dos argumentos e aplica o mapeamento oaxnpara |&^!e <>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")
        ));
    }
}

O Java's m.group(i)diz qual grupo corresponde; o 1º grupo é para substituições verdadeiras e o 2º para falsas. Isso é iterado em ordem estrita da esquerda para a direita até que nenhuma substituição seja executada.

tucuxi
fonte