Buat pengurai Boolean (lanjutan)

8

Kelanjutan dari tantangan ini karena penulis telah pergi dan pertanyaannya sudah ditutup.


Yang perlu Anda lakukan adalah membuat parser Boolean.


Ekspresi Boolean, jika Anda belum pernah mendengarnya, memiliki dua input dan satu output.

Ada empat "gerbang" dalam aritmatika boolean, yaitu:

  • ATAU (diwakili oleh | ) (operator biner, di antara argumen)
  • DAN (diwakili oleh & ) (operator biner, di antara argumen)
  • XOR (diwakili oleh ^ ) (operator biner, di antara argumen)
  • TIDAK (diwakili oleh !) (operator unary, argumen di sebelah kanan)

Gerbang ini beroperasi pada input mereka yang benar (diwakili oleh 1) atau salah (diwakili oleh 0). Kami dapat mendaftar input yang mungkin ( Adan Bdalam hal ini) dan output ( O) menggunakan tabel kebenaran sebagai berikut:

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

Contoh input akan 1^((1|0&0)^!(1&!0&1)), yang akan mengevaluasi ke:

 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

Outputnya adalah 1.

Detail

  • Seperti terlihat dalam contoh, tidak ada urutan prevalensi. Semua dievaluasi dari kiri ke kanan, kecuali ketika di dalam tanda kurung, yang harus dievaluasi terlebih dahulu.
  • Input hanya akan berisi ()!^&|01.
  • Anda dapat memilih karakter 8-byte untuk mengganti 8 karakter di atas, tetapi karakter tersebut harus memiliki pemetaan 1-ke-1 dan harus dinyatakan.
  • Secara khusus, fungsi evalini tidak diperbolehkan untuk digunakan pada string apa pun yang berasal dari input . Secara khusus, fungsi input(atau yang setara dalam bahasa) dan fungsi apa pun yang memanggilnya tidak dapat digunakan oleh eval. Anda juga tidak dapat menyatukan inputke dalam string Anda di dalam eval.

Mencetak gol

Ini adalah . Solusi terpendek dalam byte menang.

Biarawati Bocor
sumber
Cheddar memiliki built-in untuk menghasilkan panggilan stack dari sebuah string apakah itu dianulir juga?
Downgoat
2
Bisakah Anda menambahkan beberapa test case lagi?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Test case apa yang ingin Anda lihat?
Leaky Nun
@ KennyLau Beberapa yang rumit, idk
Conor O'Brien
Apakah ada kondisi yang tidak ditangani oleh test case? Saya pikir sudah cukup banyak menangani semuanya.
Leaky Nun

Jawaban:

6

JavaScript (ES6) 116 byte

edit thx @ user81655 selama 3 byte disimpan dan bug ditemukan

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

Mungkin bukan pendekatan terbaik, tapi tidak ada operator eval dan tidak ada boolean, hanya tabel kebenaran.

Karakter yang digunakan:

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

Uji

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
sumber
1
Apakah Anda benar-benar jahat x>7?
Neil
r=f(x.replace(/./g,c=>"01!&|^()".indexOf(c)))
Neil
@Neil saya akan periksa, terima kasih. Tentu saja jika> 6
edc65
@Neil Saya menambahkan kasus uji. Saya cukup yakin bahwa mengingat asosiatifitas dan komutatifitas operator, TIDAK harus selalu bekerja
edc65
Butuh beberapa waktu untuk mencari tahu mengapa (katakanlah) 0|!0bekerja, tetapi sekarang saya lakukan, dapatkan upvote saya.
Neil
5

Retina, 49 byte

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

Saya tidak tahu bagaimana hasilnya begitu singkat.

Pemetaan karakter:

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

1,, 0dan !dibiarkan tidak berubah.

Ini bekerja dengan mengganti semua ekspresi truthy (tunggal 1dalam kurung, !0, 1&1, 1^0, 0|1, dll) dengan 1, dan semua lainnya (tunggal 0dalam kurung, !1, 1&0, 1^1, 0|0, dll) dengan 0.

Cobalah online!
Cobalah online dengan pemetaan karakter otomatis!

daavko
sumber
3

grep + shell utils, 131 byte

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)|))$'

Karakter berikut diubah namanya:

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

Saya mulai mencoba untuk menulis solusi grep, tetapi menemukan bahwa itu tidak bekerja dengan baik dengan operator infiks asosiatif kiri. Saya perlu memiliki pola seperti (rantai operator) = (rantai operator) (ops biner) (operan tunggal), tetapi ini berisi kemungkinan rekursi tak terbatas, jadi grep menolak untuk menjalankannya. Tetapi saya perhatikan bahwa saya dapat mengurai operator asosiasi kanan. Ini membuat !operator sakit, tetapi itu masih mungkin. Jadi saya membuat regex untuk menghitung ekspresi boolean mundur, dan mengirim inputrev . Regex itu sendiri, yang cocok dengan ekspresi sebenarnya, adalah 116 byte.

TODO: pilih karakter yang berbeda untuk input sehingga saya bisa membedakan semua grup operator yang digunakan dengan kelas karakter bawaan.

feersum
sumber
Apa (?9)artinya
Leaky Nun
Ini berarti mengambil grup penangkap ke-9 dan menjalankannya kembali (berbeda dari \9yang berarti mencocokkan dengan apa kelompok penangkap ke-9 cocok). Jadi misalnya (\d)\1cocok dengan digit yang sama dua kali, sedangkan (\d)(\?1)cocok dengan dua digit.
Neil
2

Python, 210 byte

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

Keturunan rekursif yang sangat buruk, saya berharap ini akan dikalahkan dalam sekejap.

orlp
sumber
2

Mathematica, 139 129 byte

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

Solusi penggantian string sederhana jauh lebih baik daripada yang saya harapkan.

LegionMammal978
sumber
2

JavaScript ES6, 223 byte

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

Menggunakan algoritma halaman shunting.

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

Penggunaan +untuk OR, !untuk negasi, ^untuk XOR, dan &untuk dan. 0dan 1digunakan untuk nilai masing-masing. Tentu, saya bisa bermain golf beberapa dengan membuat angka operator, tapi saya tidak memenangkan hadiah JavaScript bahkan jika saya melakukannya, jadi saya pikir saya akan membuatnya setidaknya terbaca dan benar.

Conor O'Brien
sumber
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)));}

Tidak digabung, dengan main()(mengambil ekspresi sebagai argumen 1). Versi golf tidak memiliki debugging printfs dan menggunakan kode ascii 2-digit sebagai ganti char literals ( 40 == '('). Aku bisa menyelamatkan beberapa karakter dengan pemetaan ()|^&!untuk 234567- ini akan membuat banyak manipulasi dan tes lebih mudah setelah dikurangi 48dari masing-masing.

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

Java, 459 byte

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 adalah &

ORis l(huruf kecil L)

XORadalah x(atau karakter lain yang kebetulan bermain bagus dengan Stringmetode seperti String.replaceAll(...))

NOT adalah !

( adalah a

) adalah b

inilah versi yang lebih mudah dibaca:

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

coba online

Jack Ammo
sumber
1
Seperti biasa dengan Java golf, hal favorit saya adalah mengganti char literal dengan rekan integer mereka di mana pun saya bisa. Dalam hal ini, itu akan menjadi di kedua indexOfs biasa, dan perbandingan karakter. Juga, jika Anda mengubah karakter untuk AND menjadi "n" alih-alih "&", Anda dapat menggunakan pernyataan <atau> dengan if tunggal ketika memeriksa operasi mana yang perlu Anda lakukan.
Biru
1
Oh, satu hal lagi. Anda dapat menggandakan panggilan untuk menggantiAll di loop sementara kedua, juga menghemat kurung Anda.
Biru
@ Biru aku selalu lupa untuk char literals ke ints, terima kasih. Saya tidak yakin apa yang Anda maksud dengan menggandakan pada replaceAll call for! 'S.
Jack Ammo
s = s.replaceAll ("! 0", a) .replaceAll ("! 1", b);
Biru
1

Jawa, 218

Menggunakan pencocokan pola, tetapi menghindari penggantian out-of-order dari upaya Java saya yang gagal sebelumnya (mata tajam di sana, @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;}

Tidak digabungkan, membaca masukan dari argumen dan menerapkan pemetaan oaxnuntuk |&^!dan <>untuk ():

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)memberi tahu Anda grup mana yang cocok; kelompok 1 adalah untuk penggantian yang benar dan yang kedua untuk yang salah. Ini diulang dalam urutan kiri-ke-kanan yang ketat sampai tidak ada pergantian yang dilakukan.

tucuxi
sumber