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.

Answer 1

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 2

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 ?.

Answer 3

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 4

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 5

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>.

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

Answer 9

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.

Answer 10

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%.

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

Answer 12

SED, 75 74 68 (40 + 1 for -r) 41

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

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.