8
1
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 functioninput
(or the equivalent in the language) and any function that calls it cannot be used byeval
. You also cannot concatenate theinput
into your string inside theeval
.
Scoring
This is code-golf. Shortest solution in bytes wins.
Cheddar has a built in to generate a call stack from a string is that disallowed too? – Downgoat – 2016-04-24T01:28:59.233
2Could you add some more test cases? – Conor O'Brien – 2016-04-24T02:24:11.023
@CᴏɴᴏʀO'Bʀɪᴇɴ What test case would you like to see? – Leaky Nun – 2016-04-24T02:24:59.967
@KennyLau A few complicated ones, idk – Conor O'Brien – 2016-04-24T02:28:34.060
Is there any condition that the test case did not handle? I think it pretty much handled everything already. – Leaky Nun – 2016-04-24T02:29:36.763
@KennyLau Considering that there are only 2 outputs, a program could still fail some cases even if it passes one test case. – Conor O'Brien – 2016-04-24T02:30:31.470
I deliberately designed
1|0&0
so that if they evaluate&
first, the output will fail. – Leaky Nun – 2016-04-24T02:32:31.093Is
eval
disallowed even when it's not used on input data at all, but instead to golf the parser? – orlp – 2016-04-24T07:19:11.420@orlp Is it clear enough now? People will just find loopholes if I make it too explicit (I forgot the name of the phenomenon). – Leaky Nun – 2016-04-24T07:23:12.680
@KennyLau I think you should explicitly say that the input is given as a string (and not any other epression, otherwise you could just use an identity function in many languages). – flawr – 2016-04-24T10:33:11.283
About testcases: with just 1 or 0 for output I can just put a random function and I will be right 50% of times – edc65 – 2016-04-24T10:35:30.983
@edc65 Please do provide me with more testcases (just the input, I will produce the output) in case of doubt. – Leaky Nun – 2016-04-24T10:44:31.237
are 2 or more consecutive
!
allowed? ie!!1
– Jack Ammo – 2016-04-24T21:23:48.470eval
won't help as there are different operator priorities. – Qwertiy – 2016-04-25T07:19:10.740@JackAmmo Yes, though I do not see how that would posit any problem. – Leaky Nun – 2016-04-25T10:08:35.967
@KennyLau it's not so much a problem as verifying a case that needs to be dealt with – Jack Ammo – 2016-04-25T10:51:07.853
Not enough test cases. Testing my script on your input is just one test case, no matter how complex your test case is. I might get the right output despite getting wrong output on other cases. – msh210 – 2016-04-25T16:14:08.700
One test case should make sure the script parses left-to-right instead of all false substrings first; another should make sure it parses left-to-right instead of all true substrings first; another should make sure it parses left-to-right instead of using the usual order of operations. (That last can probably be combined with one of the others.) Another should use
!!
. – msh210 – 2016-04-25T16:17:46.360