Evaluate an expression of ternary operators

Question

Consider a grammar over the alphabet {0, 1, ?, :} defined by the production rule

s → 0 ┃ 1 ┃ 0 ? s : s ┃ 1 ? s : s

Given a string generated from s, parse it as an expression where ?: is right-associative (for example, a?B?X:Y:c?d:e?f:g means a?(B?X:Y):(c?d:(e?f:g))) and evaluate it with the following semantics:

eval(0) = 0
eval(1) = 1
eval(0?a:b) = eval(b)
eval(1?a:b) = eval(a)

If the result is 0, output some fixed value; if the output is 1, output a different fixed value. Specify your chosen output values (e.g. 0/1, or False/True) in your answer.

Test cases

0 -> 0
1 -> 1
0?0:1 -> 1
0?1:0 -> 0
1?0:1 -> 0
1?1:0 -> 1
0?1?0:1:1 -> 1
1?0?1:1:1 -> 1
1?0:1?0:1?1:1 -> 0
1?1?1:0?1?0:0:0:0 -> 1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1 -> 0
1?1?1:0?0?1:1:0?1:0:1?1?0?0:0:1?1:0:0?1?0:1:1?0:1 -> 1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1 -> 0

Rules

• You may not use language built-ins that interpret strings as code in some programming language and run it (such as JavaScript/Perl/Ruby/Python’s eval).
• That said, your code doesn’t actually have to parse and then evaluate the input string. You can take any approach the achieves equivalent results and doesn’t violate the previous rule.
• Your program will be checked against perl -le 'print eval<>'.
• The shortest code (in bytes) wins.

• Adám: How about using language built-ins like eval that interpret strings as $my_language code after changing the string radically?
• user45941: What about builtins that interpret strings as $some_other_language code?
• lynn: @Adám That would be disallowed, sorry.
• lynn: @Mego Hmm, there’s a trivial cheating opportunity there, so I extended the rule to cover all such built-ins.
• Peter Taylor: In the light of Martin's test cases, perhaps it would be simpler to define the grammar as S → T | T ? S : S, T → 0 | 1, removing the need to talk about associativity?

Answer 1

Retina, 23 bytes

r-1=+`0\?.:|1\?(.):.
1ドル

Try it online! (The first line enables a linefeed-separated test suite.)

Explanation

It's fairly simple actually. The input is reduced to the result by repeatedly (+) evaluating ternaries that contain only literals. To make sure this is done right-associatively, we look for matches from right to left (r) and replace only the last match we find (-1=).

The regex itself either matches 0\?.: and removes it (leaving only the stuff after :) or 1\?.:. and replaces it with the value after the ?.

• Leaky Nun: If the regex starts from the right then shouldn't you process the 1st match instead of the -1st?
• Martin Ender: @LeakyNun Unfortunately, I think I reverse the matches before applying the limit.

Answer 2

Haskell, (削除) 106 101 100 90 (削除ここまで) 83 bytes

This heavily relies on pattern Haskell's pattern matching capabilities. First of all, we reverse the string such that we can just seach for the first occurence of b:a?x (which would normally read as x?a:b) and replace it with it's value. This automatically provides the right associativity. Here we make use of x:xs pattern. This is what the function f is doing. Then we basically apply f to it's output over and over again, until we have a single number (0 or 1) left.

Thanks @Lynn for 12 bytes!

f(b:':':a:'?':x:l)|x>'0'=a:l|1>0=b:l
f(x:l)=x:f l
f x=x
until((<2).length)f.reverse

Answer 3

Brainfuck, (削除) 82 (削除ここまで) (削除) 64 (削除ここまで) 63 bytes

+
[
 ,>>,>
 +++++++[<---<<-[------>>]<-]
 <<
 [
 ->[<++>[+]]
 ]
 +>[>>]
 <<<-
]
<.

The output is \xff for 0 and \x00 for 1. The brainfuck implementation must allow going to the left of the starting cell.

This uses essentially the same approach as xsot's Python answer, but the branching is probably harder to follow compared with my initial 82-byte submission:

-
[
 +
 [
 ->,,>+++++++[<--------->-]
 <[<++>[+]]
 <
 ]
 ,->,>+++++++[<[-------<]>>-->-]
 <[<]
 <
]
>>.

(For this solution, the output is \xfe for 0 and \xff for 1, and wider compatibility is achieved when the input ends with a newline.)

If you can't be bothered to analyse xsot's solution, the idea is this: Proceed from left to right. If you see 1? then greedily discard it. If you see 0? then discard everything between that and the corresponding :. When ? does not appear as the second character, stop looping and print the first character of the remaining string.

So, the 82-byte solution actually mirrors that scheme pretty closely. The inner loop handles 0?, just like xsot's inner loop. Some care is taken in order to enter the main loop without checking any input characters; i.e., we want to check whether the second character is ? just once at the end of the main loop, and not also at the beginning before entering the main loop.

The 63-byte solution essentially combines the inner and outer loops into one, which I suspected was possible given the similarity between those loops. The memory layout in the main loop could be described as:

[s] d c

where [x] means current cell -- the s starts as a dummy nonzero value that just indicates we are still looping, and is immediately overwritten with an input character (either 0 or 1). The d cell holds the (negative) depth in case we are in the middle of a 0?, otherwise 0. The c is going to be either ? or : or newline or EOF.

After updating s and c, we handle the 0? case by updating d accordingly and adjusting the pointer, otherwise we use the current value of c as the value of d in the next iteration, or stop if we are done.

Answer 4

Python 2, (削除) 76 (削除ここまで) (削除) 74 (削除ここまで) (削除) 73 (削除ここまで) 72 bytes

a=`id`
for c in input()[::-1]:a=(c+a,a[ord(c)*7%9]+a[4:])[a>'?']
print a

With input as string literal to avoid raw_.

The output is 0 or 1 followed by <built-in function id>.

• xsot: Haha, I just read your answer for b lang and was about to post an almost identical answer! Here's an additional optimisation: 3>>int(c)
• WorldSEnder: Care to explain how this works? Looks really neat
• Mitch Schwartz: @WorldSEnder I think it's the type of solution that can be tricky to come up with, but easy to understand once you see it. It runs through the string backwards and repeatedly processes the rightmost conditional, as other solvers have done as well.
• lynn: That `id` trick...! Well done :)

Answer 5

GolfScript, 21 bytes

2/-1%{)2%{0`=@@if}*}/

This outputs 0 or 1. Input is assumed to have a single trailing newline. Using ~ (which evaluates strings) would save a byte:

2/-1%{)2%{~!@@if}*}/

This is based on http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails_1462638030&gs .

Answer 6

Python 2, 89 bytes

s=input()
while'?'<=s[1:]:
 n=s<'1'
 while n:s=s[2:];n+=-(s[1]<'?')|1
 s=s[2:]
print s[0]

Input is taken as a string literal.

Answer 7

Grime, (削除) 34 (削除ここまで) 31 bytes

E=d|d\?E.E
e`1円|1円\?_.E|0円\?E._

Prints 1 for truthy inputs and 0 for falsy ones. Try it online! The last test case unfortunately runs out of memory on TIO.

Explanation

The right-associativity essentially means that in a?b:c, a is always either 0 or 1, never a longer expression. I'll just recursively define a pattern that matches a truthy expression like that, and check the input against it. It's also unnecessary to check that every : is really a :, if the ?s are all checked: there is an equal number of ?s and :s in the input, and if some ? is incorrectly classified as a :, the corresponding : will fail to match, and Grime's matching engine will backtrack.

E=d|d\?E.E
E= Define nonterminal E (for "expression") as
 d| a digit, OR
 d a digit,
 \? a literal ?,
 E a match of E,
 . any character (will match a :), and
 E another match of E.
e`1円|1円\?_.E|0円\?E._
e` Match entire input against this pattern (truthy expression):
 1円| a literal 1, OR
 1円\? a literal 1?,
 _ a recursive match of truthy expression,
 . any character (will match a :), and
 E| any expression, OR
 0円\?E._ the same, but with 0 in front, and _ and E swapped.

Answer 8

Haskell, (削除) 79 71 70 62 60 (削除ここまで) 56 bytes

Edit: Thanks to @Zgarb for 3 bytes and to @nimi for 4 bytes!

e(x:'?':r)|a:_:s<-e r=last$e s:[a:tail(e s)|x>'0']
e x=x

This a recursive approach (削除) that somewhat abuses the "some fixed value"-output rule (削除ここまで). Edit: Getting rid of the tuples doesn't only save 8 bytes, it also yields a nicer output: "0" or "1".

Ungolfed version:

eval (x:'?':r1) = if x=='1' then (a, r3) else (b, r3)
 where (a,':':r2) = eval r1
 (b, r3) = eval r2
eval (x:r) = (x,r)

How does it work?
The eval function traverses the implicit tree of the expressions

eval 1?0?0:1:0?1:0 -> eval 1? :
 eval 0?0:1 eval 0?1:0

and returns a tuple of the form (result, rest).
The first pattern (x:'?':r1) matches x to '1' and r1 to "0?0:1:0?1:0". Recursively applying eval to r1 evaluates the sub-expression 0?0:1 and returns (0,":0?1:0"). Matching this to the pattern (a,':':r2) yields a=0 and r2=0?1:0. This sub-formula is also recursively evaluated so that b='0' and r3="". Check if x is '1' or '0' and return either (a, r3) or (b, r3).

• Zgarb: Nice approach! Would x>'0' work in place of x=='1'?
• Laikoni: Thanks, I didn't think of that while dealing with chars.
• Zgarb: I think you can also replace ':' by _.
• Laikoni: Yes, then the code even works for arbitrary delimiters instead of just :. Thanks again!
• nimi: Nice! You can replace the if .. then .. else with last$e s:[a:tail(e s)|x>'0'].

Answer 9

JavaScript (ES6), 53 bytes

f=s=>s[1]?f(s.replace(/0\?.:|1\?(.):.(?!\?)/,"1ドル")):s

Returns 0 or 1 for valid input; hangs for invalid input. Explanation: because reversing a string is awkward in JavaScript, my first 71-byte attempt worked by using a negative lookahead for a ? which would otherwise disturb the associativity:

f=s=>s[1]?f(s.replace(/(.)\?(.):(.)(?!\?)/,(_,a,b,c)=>+a?b:c)):s

Since this was somewhat long I wondered whether I could improve matters by incorporating the decision making into the regexp. As it turned out, it wasn't an immediate success, as it also took 71 bytes:

f=s=>s[1]?f(s.replace(/0\?.:(.)(?!\?)|1\?(.):.(?!\?)/,"1ドル2ドル")):s

Then it occurred to me that 0?0: and 0?1: are always no-ops, without concern for associativity. This saved me almost 25%.

• Patrick Roberts: Your code block at the top is missing f=. I haven't checked if your byte count is taking it into account or not.
• Neil: @PatrickRoberts I'm forever doing that, because I copy from the log, which only shows the result of the assignment (which is enough for nonrecursive functions of course).
• ASCII-only: @Neil you can copy from log input instead of output
• Neil: @MarsUltor The log input includes the prompt, which I have to then remember to exclude. This is an awkward extra step for non-recursive functions, which is why I copy from the output by default.

Answer 10

Perl, 32 + 1 (-p flag) = 33 bytes

Full credit to @Mitch Swartch, as his solution was 14 bytes shorter than mine!
Thanks also to @Neil who suggested a solution 1 byte longer than Mitch.

s/.*\K(0\?..|1\?(.)..)/2円/&&redo

Needs -p flag, as well as -M5.010 or -E to run. For instance :

perl -pE 's/.*\K(0\?..|1\?(.)..)/2円/&&redo' <<< "0
0?0:1
0?1?0:1:1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1"

Explanations : It basically reduces the blocks of a?b:c (starting from the end to be sure no ? follows) into b or c depending on the truthness of a, over and over until the string only contains 1 or 0.

• bren: Does the - not count towards your score? Hrm. Interesting... Good answer!
• Neil: @MayorMonty For a 1-liner you can invoke it on the command line using perl -e '<code>' thus adding a p only costs 1 byte perl -pe '<code>'.
• bren: @Neil Ahh, that makes sense
• Neil: Actually you don't have to reverse the string, you can just negative lookahead for a ?, I was able to cut this down to 34 bytes this way.
• Mitch Schwartz: Here is a 32 + 1: s/.*\K(1\?(.)..|0\?..)/2円/&&redo

Answer 11

Python 3, (削除) 93 (削除ここまで) 69 bytes

def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r

Input is the string as a list of characters, output is either "0" or "1"

>>>f(list("0?0:1"))
<<<"1"

---

Ungolfed version:

def parse(s):
 predicate = s.pop(0)
 if s and s.pop(0) == '?':
 left, right = parse(s), parse(s)
 if predicate == '0':
 return right
 return left
 return predicate

---

Another try, but with considerably more bytes:

i=input()[::-1]
a=[i[0]]
for o,z in zip(i[1::2],i[2::2]):a+=[z]if o<'?' else[[a.pop(),a.pop()][z>'0']]
print(a[0])

• lynn: Your answer may be a function — you can remove the second line.
• Mitch Schwartz: This is clearly untested, as it doesn't pass the test cases, and the ungolfed version gives a runtime error. Your basic idea is good though. With some adjustments I get 68 in Python 2 and 69 in Python 3.
• Mitch Schwartz: Well I think it makes more sense for me to give you the answer than to edit it into my own (since I wasn't thinking about this kind of approach before I saw your answer) or sit around waiting while your answer is buggy. Here is the 68 I mentioned def f(s):x=s.pop(0);return[]<s<s.pop(0)>'>'and(f(s),f(s))[x<'1']or x, and for Python 3 with small edit distance to yours, there is def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r .
• WorldSEnder: Thanks @MitchSchwartz, pretty much parse from right, instead of left, gotcha
• WorldSEnder: Otherway, left instead of right, ~~~

Answer 12

SED, (削除) 75 74 68 (削除ここまで) (40 + 1 for -r) 41

:
s,(.*)1\?(.):.,1円2,円
s,(.*)0\?.:,1,円
t

• Neil: You can probably cut this down using @MitchSchwartz's trick in his comment, although you may have to use (.*) and add an extra replacement term.
• Riley: @Neil, you could be right, but I can't figure out how to make it work.
• Mitch Schwartz: I wrote it in chat, since formatting in a comment might be confusing: chat.stackexchange.com/transcript/message/31709640#31709640
• Neil: @MitchSchwartz Heh, blank labels work? But I think you meant 3円 instead of 2円. Also, you can join the lines with ; to get :;s/(.*)(1\?(.):.|0\?.:)/1円3円/;t.
• Mitch Schwartz: @Neil I had 3円 so that means I accidentally copied a previous version. I know about semicolons. But yuck, why would you want to use semicolons.

Answer 13

Bash + GNU utilities, 42

rev|sed -r ':
s/(.):.\?0|.:(.)\?1/1円2円/
t'

Similar idea to most of the other pattern-matching answers.

Ideone.

• Neil: You don't need to capture the first character in the 0 case, that saves you 5 bytes.