8
\$\begingroup\$

Continuation of this challenge because the author is gone and the question is closed.


What you need to do is create a Boolean parser.


Boolean expressions, in case you haven't heard of them yet, have two inputs and one output.

There are four "gates" in boolean arithmetic, namely:

  • OR (represented by |) (binary operator, between arguments)
  • AND (represented by &) (binary operator, between arguments)
  • XOR (represented by ^) (binary operator, between arguments)
  • NOT (represented by !) (unary operator, argument on right)

These gates operate on their inputs which are either true (represented by 1) or false (represented by 0). We can list the possible inputs (A and B in this case) and the outputs (O) using a truth table as follows:

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

An example input would be 1^((1|0&0)^!(1&!0&1)), which would evaluate to:

 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

The output would be 1.

Details

  • As seen in the example, there is no order of prevalence. All are evaluated from left to right, except when inside parentheses, which should be evaluated first.
  • The input will only contain ()!^&|01.
  • You can choose any 8-byte character to replace the 8 characters above, but they must have a 1-to-1 mapping and must be stated.
  • Specifically, the function eval is not allowed to be used on any string derived from the input. Specifically, the function input (or the equivalent in the language) and any function that calls it cannot be used by eval. You also cannot concatenate the input into your string inside the eval.

Scoring

This is . Shortest solution in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Cheddar has a built in to generate a call stack from a string is that disallowed too? \$\endgroup\$ – Downgoat Apr 24 '16 at 1:28
  • 2
    \$\begingroup\$ Could you add some more test cases? \$\endgroup\$ – Conor O'Brien Apr 24 '16 at 2:24
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ What test case would you like to see? \$\endgroup\$ – Leaky Nun Apr 24 '16 at 2:24
  • \$\begingroup\$ @KennyLau A few complicated ones, idk \$\endgroup\$ – Conor O'Brien Apr 24 '16 at 2:28
  • \$\begingroup\$ Is there any condition that the test case did not handle? I think it pretty much handled everything already. \$\endgroup\$ – Leaky Nun Apr 24 '16 at 2:29
6
\$\begingroup\$

JavaScript (ES6) 116 bytes

edit thx @user81655 for 3 bytes saved and a bug found

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

Probably not the best approach, but no eval and no boolean operators, just truth tables.

Character used:

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

Test

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>

\$\endgroup\$
  • 1
    \$\begingroup\$ Did you really mean x>7? \$\endgroup\$ – Neil Apr 24 '16 at 12:08
  • \$\begingroup\$ r=f(x.replace(/./g,c=>"01!&|^()".indexOf(c))) \$\endgroup\$ – Neil Apr 24 '16 at 12:11
  • \$\begingroup\$ @Neil I'll check, thanks. Of course if >6 \$\endgroup\$ – edc65 Apr 24 '16 at 12:20
  • \$\begingroup\$ @Neil I'm adding test cases. I'm quite sure that given associativity and commutativity of the operators, the NOT should always work \$\endgroup\$ – edc65 Apr 24 '16 at 12:28
  • \$\begingroup\$ It took me some time to work out why (say) 0|!0 works, but now I do, have my upvote. \$\endgroup\$ – Neil Apr 24 '16 at 14:19
5
\$\begingroup\$

Retina, 49 bytes

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

I have no idea how did it come out so short.

Character mapping:

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

1, 0, and ! are left unchanged.

This works by replacing all truthy expressions (single 1 in parentheses, !0, 1&1, 1^0, 0|1, etc.) with 1, and all other (single 0 in parentheses, !1, 1&0, 1^1, 0|0, etc.) with 0.

Try it online!
Try it online with automatic character mapping!

\$\endgroup\$
3
\$\begingroup\$

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

The following chars are renamed:

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

I started trying to write a grep solution, but discovered that it did not work well with the left-associative infix operators. I needed to have a pattern like (chain of operators) = (chain of operators) (binary op) (single operand), but this contains a possible infinite recursion, so grep refuses to execute it. But I noticed that I could parse right-associative operators. This made the ! operator a pain, but it was still possible. So I made a regex for calculating backwards boolean expressions, and sent the input through rev. The regex itself, which matches true expressions, is 116 bytes.

TODO: choose different characters for the input so that I can distinguish all the used groups of operators with built-in character classes.

\$\endgroup\$
  • \$\begingroup\$ What does (?9) mean? \$\endgroup\$ – Leaky Nun Apr 24 '16 at 7:25
  • \$\begingroup\$ It means take the 9th capturing group and re-execute it (as distinct from \9 which would mean to match what the 9th capturing group matched). So for instance (\d)\1 matches the same digit twice, while (\d)(\?1) matches any two digits. \$\endgroup\$ – Neil Apr 24 '16 at 7:52
2
\$\begingroup\$

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

Really bad recursive descent, I expect this to be beaten in a heartbeat.

\$\endgroup\$
2
\$\begingroup\$

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

A simple string-replacement solution scores far better than I hoped for.

\$\endgroup\$
2
\$\begingroup\$

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

Uses a shunting yard algorithm.

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

Uses + for OR, ! for negation, ^ for XOR, and & for and. 0 and 1 are used for their respective values. Sure, I could golf some by making the operators numbers, but I'm not winning the JavaScript prize even if I do, so I thought I'd make it at least somewhat readable and correct.

\$\endgroup\$
1
\$\begingroup\$

C, 247

Golfed:

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() (takes expression as 1st arg). The golfed version has no debugging printfs and uses 2-digit ascii codes instead of char literals (40 == '('). I could have saved some characters by mapping ()|^&! to 234567 - this would have made many manipulations and tests easier after subtracting 48 from each.

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);
}
\$\endgroup\$
  • \$\begingroup\$ +1 for for(j=i=1;i+=s[++j]==')'?-1:s[j]=='('?1:0,i;);. \$\endgroup\$ – Leaky Nun Apr 25 '16 at 14:55
1
\$\begingroup\$

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

OR is l(lowercase L)

XOR is x (or any other character that happens to play nice with String's methods such as String.replaceAll(...))

NOT is !

( is a

) is b

here's a more readable 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;
}

try it online

\$\endgroup\$
  • 1
    \$\begingroup\$ As always with Java golfing, my favorite thing to do is replace char literals with their integer counterparts wherever I can. In this case, that would be in both the regular indexOfs, and the charAt comparisons. Also, if you change the character for AND to "n" instead of "&", you can use < or > statements with single ifs when checking for which operation you need to do. \$\endgroup\$ – Blue Apr 25 '16 at 10:22
  • 1
    \$\begingroup\$ Oh, one more thing. You can double up on the call to replaceAll in the second while loop, also saving you those brackets. \$\endgroup\$ – Blue Apr 25 '16 at 10:24
  • \$\begingroup\$ @Blue i always forget to char literals to ints, thanks. I'm not quite sure what you mean on doubling up on the replaceAll call for the !'s. \$\endgroup\$ – Jack Ammo Apr 25 '16 at 11:21
  • \$\begingroup\$ s=s.replaceAll("!0",a).replaceAll("!1",b); \$\endgroup\$ – Blue Apr 25 '16 at 11:23
1
\$\begingroup\$

Java, 218

Uses pattern-matching, but avoids the out-of-order replacements of my previous failed Java attempt (sharp eyes there, @Kenny Lau!).

Golfed:

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, reads input from arguments and applies the mapping oaxn for |&^! and <> for ():

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's m.group(i) tells you which group matched; the 1st group is for true substitutions and the 2nd one for false ones. This is iterated in strict left-to-right order until no substitutions are performed.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.