Avaliar uma expressão de operadores ternários

29

Considere uma gramática sobre o alfabeto { 0, 1, ?, :} definido pela regra de produção

s → 010 ?s :s ┃ 1 ?s :s

Dada uma sequência gerada a partir de s , analise-a como uma expressão ?:associativa à direita (por exemplo, a?B?X:Y:c?d:e?f:gsignifica a?(B?X:Y):(c?d:(e?f:g))) e avalie-a com a seguinte semântica:

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

Se o resultado for 0 , produza algum valor fixo; se a saída for 1 , produza um valor fixo diferente. Especifique seus valores de saída escolhidos (por exemplo, 0/ 1ou False/ True) em sua resposta.

Casos de teste

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

Regras

  • Você não pode usar built-ins de linguagem que interpretam seqüências de caracteres como código em alguma linguagem de programação e as executam (como JavaScript / Perl / Ruby / Python eval).
  • Dito isto, seu código não realmente têm para analisar e, em seguida, avaliar a cadeia de entrada. Você pode adotar qualquer abordagem que alcance resultados equivalentes e não viole a regra anterior.
  • Seu programa será verificado perl -le 'print eval<>'.
  • O código mais curto (em bytes) vence.
Lynn
fonte
Que tal usar built-ins de linguagem, como eval, que interpretam cadeias de caracteres como código $ my_language depois de alterar radicalmente a cadeia de caracteres?
Adám 15/08/16
E quanto aos builtins que interpretam cadeias de caracteres como código $ some_other_language ?
Mego
@ Adám Isso seria proibido, desculpe.
Lynn
@Mego Hmm, há uma oportunidade de trapaça trivial por lá, então estendi a regra para cobrir todos esses embutidos.
Lynn
11
À luz de casos de teste de Martin, talvez seria mais simples para definir a gramática como S → T | T ? S : S, T → 0 | 1, eliminando a necessidade de falar sobre associatividade?
Peter Taylor

Respostas:

17

Retina , 23 bytes

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

Experimente online! (A primeira linha ativa um conjunto de testes separado por avanço de linha.)

Explicação

Na verdade, é bastante simples. A entrada é reduzida ao resultado +avaliando repetidamente ( ) ternários que contêm apenas literais. Para garantir que isso seja feito de maneira associativa, procuramos correspondências da direita para a esquerda ( r) e substituímos apenas a última correspondência que encontramos ( -1=).

A própria expressão regular corresponde 0\?.:e a remove (deixando apenas o material depois :) ou 1\?.:.e o substitui pelo valor após o ?.

Martin Ender
fonte
Se o regex iniciar da direita, você não deve processar a 1correspondência st em vez de -1st?
Leaky Nun
@LeakyNun Infelizmente, acho que inverto as partidas antes de aplicar o limite.
Martin Ender
10

Haskell, 106 101 100 90 83 bytes

Isso depende muito dos recursos de correspondência de padrões de Haskell. Antes de tudo, invertemos a string de modo que possamos buscar pela primeira ocorrência de b:a?x(que normalmente seria lida como x?a:b) e a substituímos por seu valor. Isso fornece automaticamente a associatividade correta . Aqui fazemos uso do x:xspadrão. É isso que a função festá fazendo. Basicamente, aplicamos fsua saída repetidamente, até termos um único número (0 ou 1).

Obrigado @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
flawr
fonte
8

Brainfuck, 82 64 63 bytes

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

A saída é \xffpara 0e \x00para 1. A implementação do brainfuck deve permitir ir para a esquerda da célula inicial.

Isso usa essencialmente a mesma abordagem da resposta Python do xsot , mas a ramificação é provavelmente mais difícil de seguir em comparação com meu envio inicial de 82 bytes:

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

(Para esta solução, a saída é \xfepara 0e \xffpara 1, e uma compatibilidade mais ampla é alcançada quando a entrada termina com uma nova linha.)

Se você não se incomoda em analisar a solução da xsot, a idéia é a seguinte: Prossiga da esquerda para a direita. Se você 1?vir, descarte-o avidamente. Se você 0?vir, descarte tudo entre isso e o correspondente :. Quando ?não aparecer como o segundo caractere, pare o loop e imprima o primeiro caractere da seqüência restante.

Portanto, a solução de 82 bytes realmente reflete esse esquema de perto. O loop interno lida com 0?, assim como o loop interno do xsot. Alguns cuidados são tomados para entrar no loop principal sem verificar nenhum caractere de entrada; ou seja, queremos verificar se o segundo caractere é ?apenas uma vez no final do loop principal e não também no início antes de entrar no loop principal.

A solução de 63 bytes combina essencialmente os loops internos e externos em um, que eu suspeitava ser possível, dada a semelhança entre esses loops. O layout da memória no loop principal pode ser descrito como:

[s] d c

where [x]significa célula atual - scomeça como um valor fictício diferente de zero que apenas indica que ainda estamos em loop e é imediatamente substituído por um caractere de entrada ( 0ou 1). A dcélula mantém a profundidade (negativa) no caso de estarmos no meio de uma 0?, caso contrário 0. O cque vai ser ?ou :ou nova linha ou EOF.

Após a atualização se c, lidamos com o 0?caso atualizando de dacordo e ajustando o ponteiro; caso contrário, usamos o valor atual de ccomo o valor da dpróxima iteração ou paramos se tivermos terminado.

Mitch Schwartz
fonte
7

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

Com entrada como string literal para evitar raw_.

A saída é 0ou é 1seguida por <built-in function id>.

Mitch Schwartz
fonte
11
Haha, acabei de ler sua resposta para b lang e estava prestes a postar uma resposta quase idêntica! Aqui está uma otimização adicional:3>>int(c)
xsot 15/08/16
Gostaria de explicar como isso funciona? Parece realmente arrumado
WorldSEnder
@WorldSEnder Acho que é o tipo de solução que pode ser difícil de encontrar, mas fácil de entender quando você a vê. Ele percorre a string para trás e processa repetidamente a condicional mais à direita, como outros solucionadores também fizeram.
Mitch Schwartz
Esse `id`truque…! Bem-feito :) #
1112 Lynn Lynn
5

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]

A entrada é aceita como uma string literal.

xsot
fonte
5

Grime , 34 31 bytes

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

Imprime 1para entradas 0verdadeiras e falsas. Experimente online! Infelizmente, o último caso de teste fica sem memória no TIO.

Explicação

A associatividade correta significa essencialmente que em a?b:c, asempre é um 0ou 1, nunca uma expressão mais longa. Definirei recursivamente um padrão que corresponda a uma expressão verdadeira como essa e verificarei a entrada. Também é desnecessário verificar se every :é realmente a :, se todos os ?s estão marcados: existe um número igual de ?s e :s na entrada e se alguns ?são classificados incorretamente como a :, o correspondente :falhará em corresponder e o emparelhamento do Grime o motor retornará.

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.
Zgarb
fonte
5

Haskell, 79 71 70 62 60 56 bytes

Edit: Obrigado a @ Zgarb por 3 bytes e a @nimi por 4 bytes!

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

Essa é uma abordagem recursiva que abusa um pouco da regra de saída "algum valor fixo" . Edit: Livrar-se das tuplas não apenas salva 8 bytes, mas também produz uma saída melhor: "0"ou "1".

Versão não destruída:

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?
A evalfunção percorre a árvore implícita das expressões

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

e retorna uma tupla do formulário (result, rest).
O primeiro padrão (x:'?':r1)corresponde xa '1'e r1para "0?0:1:0?1:0". Aplicando recursivamente evalpara r1avaliar a subexpressão 0?0:1e retornos (0,":0?1:0"). Combinar isso com o padrão (a,':':r2)gera a=0e r2=0?1:0. Essa subfórmula também é avaliada recursivamente para que b='0'e r3="". Verifique se xé '1'ou '0'e retorne (a, r3)ou (b, r3).

Laikoni
fonte
11
Boa abordagem! Iria x>'0'trabalhar no lugar de x=='1'?
Zgarb
Obrigado, eu não pensei nisso enquanto lidava com caracteres.
Laikoni
11
Eu acho que você também pode substituir ':'por _.
Zgarb
Sim, então o código funciona até para delimitadores arbitrários em vez de justos :. Obrigado novamente!
Laikoni
11
Agradável! Você pode substituir o if .. then .. elsecom last$e s:[a:tail(e s)|x>'0'].
N
3

JavaScript (ES6), 53 bytes

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

Retorna 0ou 1para entrada válida; trava para entrada inválida. Explicação: como a reversão de uma string é desajeitada no JavaScript, minha primeira tentativa de 71 bytes funcionou usando um cabeçote negativo negativo para um ?que, de outra forma, perturbaria a associatividade:

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

Como isso foi um pouco longo, fiquei pensando se poderia melhorar as coisas incorporando a tomada de decisão no regexp. Como se viu, não foi um sucesso imediato, pois também levou 71 bytes:

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

Então me ocorreu que 0?0:e 0?1:sempre são não-ops, sem preocupação com associatividade. Isso me salvou quase 25%.

Neil
fonte
Seu bloco de código na parte superior está ausente f=. Não verifiquei se sua contagem de bytes está levando em consideração ou não.
Patrick Roberts
@PatrickRoberts Estou sempre fazendo isso, porque copio do log, que mostra apenas o resultado da atribuição (o que é suficiente para funções não recursivas, é claro).
Neil
@Neil você pode copiar a partir da entrada log em vez de saída
ASCII-only
@MarsUltor A entrada do log inclui o prompt, que eu tenho que lembrar de excluir. Este é um passo extra estranho para funções não recursivas, e é por isso que copio da saída por padrão.
Neil
3

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

Crédito total para @Mitch Swartch , pois sua solução era 14 bytes menor que a minha!
Agradecemos também a @ Neil, que sugeriu uma solução 1 byte mais que Mitch.

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

Precisa de -psinalizador, bem como -M5.010ou -Epara executar. Por exemplo :

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"

Explicações : Basicamente, reduz os blocos de a?b:c(começando do final para garantir que não se ?segue) em bou cdependendo da verdade de a, repetidamente, até que a sequência contenha apenas 1ou 0.

dada
fonte
Isso -não conta para a sua pontuação? Hrm. Interessante ... Boa resposta!
MayorMonty 15/08/16
@MayorMonty Para um liner de 1 linha, você pode invocá-lo na linha de comando perl -e '<code>', adicionando assim papenas 1 byte de custo perl -pe '<code>'.
Neil
@Neil Ahh, isso faz sentido
MayorMonty
Na verdade, você não precisa inverter a string, você pode apenas procurar um negativo ?, eu consegui reduzir para 34 bytes dessa maneira.
Neil
Aqui está um 32 + 1: #s/.*\K(1\?(.)..|0\?..)/\2/&&redo
Mitch Schwartz
2

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

Entrada é a sequência como uma lista de caracteres, a saída é "0"ou"1"

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

Versão não destruída:

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

Outra tentativa, mas com consideravelmente mais 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])
WorldSEnder
fonte
Sua resposta pode ser uma função - você pode remover a segunda linha.
Lynn
Isso é claramente não testado, pois não passa nos casos de teste, e a versão não armazenada gera um erro de tempo de execução. Sua idéia básica é boa. Com alguns ajustes, recebo 68 no Python 2 e 69 no Python 3. #
Mitch Schwartz
11
Bem, acho que faz mais sentido para você dar a resposta do que editá-la por conta própria (já que eu não estava pensando nesse tipo de abordagem antes de ver sua resposta) ou ficar esperando enquanto sua resposta está com erros. Aqui estão os 68 que mencionei def f(s):x=s.pop(0);return[]<s<s.pop(0)>'>'and(f(s),f(s))[x<'1']or x, e para o Python 3 com pequena distância de edição da sua, existe def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r.
Mitch Schwartz
Graças @MitchSchwartz, praticamente parse da direita, em vez da esquerda, gotcha
WorldSEnder
11
Otherway, esquerda em vez da direita, ~~~
WorldSEnder
1

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

:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t
Riley
fonte
Provavelmente, você pode reduzir isso usando o truque de @ MitchSchwartz em seu comentário , embora seja necessário usar (.*)e adicionar um termo de substituição extra.
Neil
@ Neil, você pode estar certo, mas não consigo descobrir como fazê-lo funcionar.
Riley
Eu escrevi isso no bate-papo, uma vez que a formatação em um comentário pode ser confuso: chat.stackexchange.com/transcript/message/31709640#31709640
Mitch Schwartz
@MitchSchwartz Heh, etiquetas em branco funcionam? Mas acho que você quis dizer em \3vez de \2. Além disso, você pode juntar as linhas com ;a get :;s/(.*)(1\?(.):.|0\?.:)/\1\3/;t.
Neil
@ Neil eu tinha \3, o que significa que eu acidentalmente copiei uma versão anterior. Eu sei sobre ponto e vírgula. Mas eca, por que você quer usar ponto e vírgula.
Mitch Schwartz
0

Utilitários Bash + GNU, 42

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

Idéia semelhante à maioria das outras respostas de correspondência de padrões.

Ideone .

Trauma Digital
fonte
Você não precisa capturar o primeiro caractere no 0caso, que economiza 5 bytes.
Neil