Considere una gramática sobre el alfabeto { 0, 1, ?, :} definido por la regla de producción

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

Dada una cadena generada a partir de s , analícela como una expresión donde ?:sea ​​asociativa a la derecha (por ejemplo, a?B?X:Y:c?d:e?f:gsignifica a?(B?X:Y):(c?d:(e?f:g))) y evalúela con la siguiente semántica:

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

Si el resultado es 0 , genera un valor fijo; si la salida es 1 , genera un valor fijo diferente. Especificar sus valores de salida elegidos (por ejemplo, 0/ 1o False/ True) en su respuesta.

Casos de prueba

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

Reglas

• No puede utilizar el lenguaje incorporado que interpreta cadenas como código en algún lenguaje de programación y ejecutarlo (como JavaScript / Perl / Ruby / Python eval).
• Dicho esto, su código en realidad no tiene que analizar y luego evaluar la cadena de entrada. Puede adoptar cualquier enfoque que logre resultados equivalentes y no viole la regla anterior.
• Su programa será verificado contra perl -le 'print eval<>'.
• El código más corto (en bytes) gana.

GolfScript, 21 bytes

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

Esto produce 0o 1. Se supone que la entrada tiene una nueva línea final. El uso ~(que evalúa las cadenas) guardaría un byte:

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

Esto se basa en http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails_1462638030&gs .

Retina , 23 bytes

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

Pruébalo en línea! (La primera línea habilita un conjunto de pruebas separado por salto de línea).

Explicación

Es bastante simple en realidad. La entrada se reduce al resultado +evaluando repetidamente ( ) ternaries que contienen solo literales. Para asegurarnos de que esto se haga de forma asociativa a la derecha, buscamos coincidencias de derecha a izquierda ( r) y reemplazamos solo la última coincidencia que encontramos ( -1=).

La expresión regular en sí coincide 0\?.:o la elimina (dejando solo las cosas después :) o la 1\?.:.reemplaza con el valor después de ?.

Haskell, 106101100 90 83 bytes

Esto depende en gran medida de las capacidades de coincidencia de patrones de Haskell. En primer lugar, invertimos la cadena de modo que podamos buscar la primera ocurrencia de b:a?x(que normalmente se leería como x?a:b) y reemplazarla por su valor. Esto proporciona automáticamente la asociatividad correcta . Aquí hacemos uso del x:xspatrón. Esto es lo que festá haciendo la función . Luego, básicamente aplicamos fa su salida una y otra vez, hasta que nos quede un solo número (0 o 1).

¡Gracias @Lynn por 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

Brainfuck, 82 64 63 bytes

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

La salida es \xffpara 0y \x00para 1. La implementación de brainfuck debe permitir ir a la izquierda de la celda inicial.

Esto utiliza esencialmente el mismo enfoque que la respuesta de Python de xsot , pero la ramificación es probablemente más difícil de seguir en comparación con mi envío inicial de 82 bytes:

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

(Para esta solución, la salida es \xfepara 0y \xffpara 1, y se logra una compatibilidad más amplia cuando la entrada termina con una nueva línea).

Si no puede molestarse en analizar la solución de xsot, la idea es la siguiente: proceder de izquierda a derecha. Si ve 1?, deseche con avidez. Si ve 0?, descarte todo lo que se encuentre entre eso y el correspondiente :. Cuando ?no aparece como el segundo carácter, deje de recorrer e imprima el primer carácter de la cadena restante.

Entonces, la solución de 82 bytes en realidad refleja ese esquema bastante de cerca. El bucle interno se maneja 0?, al igual que el bucle interno de xsot. Se debe tener cuidado para ingresar al bucle principal sin verificar ningún carácter de entrada; es decir, queremos verificar si el segundo carácter está ?solo una vez al final del ciclo principal, y no también al principio antes de ingresar al ciclo principal.

La solución de 63 bytes combina esencialmente los bucles interno y externo en uno, lo que sospechaba que era posible dada la similitud entre esos bucles. El diseño de la memoria en el bucle principal podría describirse como:

[s] d c

donde [x]significa celda actual: scomienza como un valor ficticio distinto de cero que solo indica que todavía estamos en bucle e inmediatamente se sobrescribe con un carácter de entrada (ya sea 0o 1). La dcelda tiene la profundidad (negativa) en caso de que estemos en el medio de a 0?, de lo contrario 0. El cva a ser ?o :o nueva línea o EOF.

Después de actualizar sy c, manejamos el 0?caso actualizando en dconsecuencia y ajustando el puntero, de lo contrario, usamos el valor actual de ccomo el valor de den la próxima iteración, o nos detenemos si hemos terminado.

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

Con entrada como cadena literal para evitar raw_.

La salida es 0o 1seguida de <built-in function id>.

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]

La entrada se toma como un literal de cadena.

Grime , 34 31 bytes

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

Imprime 1para entradas verdaderas y 0falsas. Pruébalo en línea! Desafortunadamente, el último caso de prueba se queda sin memoria en TIO.

Explicación

La asociatividad correcta significa esencialmente que en a?b:c, aes siempre una 0o 1, nunca, una expresión más larga. Definiré recursivamente un patrón que coincida con una expresión veraz como esa, y comprobaré la entrada contra él. También es necesario comprobar que cada :es realmente una :, si los ?s son todos verificado: hay un número igual de ?s y :S en la entrada, y si alguna ?se clasifica incorrectamente como :, los correspondientes :no se adapte, y la coincidencia de Grime El motor retrocederá.

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.

Haskell, 79 71 70 62 60 56 bytes

Editar: ¡ Gracias a @Zgarb por 3 bytes y a @nimi por 4 bytes!

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

Este es un enfoque recursivo que de alguna manera abusa de la regla de salida de "algún valor fijo" . Editar: deshacerse de las tuplas no solo ahorra 8 bytes, sino que también produce una salida más agradable: "0"o "1".

Versión sin golf:

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)

¿Como funciona?
La evalfunción atraviesa el árbol implícito de las expresiones.

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

y devuelve una tupla del formulario (result, rest).
El primer patrón (x:'?':r1)coincide xcon '1'y r1para "0?0:1:0?1:0". La aplicación recursiva evala r1evalúa la subexpresión 0?0:1y devuelve (0,":0?1:0"). Al hacer coincidir esto con los (a,':':r2)rendimientos del patrón a=0y r2=0?1:0. Esta sub-fórmula también se evalúa recursivamente para que b='0'y r3="". Compruebe si xes '1'o '0'y devuelva (a, r3)o (b, r3).

JavaScript (ES6), 53 bytes

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

Devoluciones 0o 1para entrada válida; se bloquea por entrada no válida. Explicación: debido a que revertir una cadena es incómodo en JavaScript, mi primer intento de 71 bytes funcionó usando una búsqueda anticipada negativa de una ?que de otro modo perturbaría la asociatividad:

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

Como esto fue algo largo, me pregunté si podría mejorar las cosas incorporando la toma de decisiones en la expresión regular. Al final resultó que no fue un éxito inmediato, ya que también tomó 71 bytes:

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

Entonces se me ocurrió eso 0?0:y 0?1:siempre son no-ops, sin preocupación por la asociatividad. Esto me ahorró casi el 25%.

Perl, 32 + 1 ( -pbandera) = 33 bytes

¡Crédito total a @Mitch Swartch , ya que su solución fue 14 bytes más corta que la mía!
Gracias también a @Neil que sugirió una solución 1 byte más larga que Mitch.

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

Necesita -pbandera, así como -M5.010o -Epara correr. Por ejemplo :

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"

Explicaciones : Básicamente, reduce los bloques de a?b:c(comenzando desde el final para asegurarse de que no ?sigue) en bo cdependiendo de la veracidad de a, una y otra vez hasta que la cadena solo contiene 1o 0.

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

La entrada es la cadena como una lista de caracteres, la salida es "0"o"1"

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

Versión sin golf:

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

Otro intento, pero con considerablemente más 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])

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

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

Bash + GNU utilidades, 42

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

Idea similar a la mayoría de las otras respuestas de coincidencia de patrones.

Ideone .