Оценить выражение троичных операторов

29

Рассмотрим грамматику над алфавитом { 0, 1, ?, :} определяется правилом производства

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

Получив строку, сгенерированную из s , проанализируйте ее как выражение, где ?:ассоциативно справа (например, a?B?X:Y:c?d:e?f:gозначает a?(B?X:Y):(c?d:(e?f:g))), и оцените ее с помощью следующей семантики:

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

Если результат равен 0 , выведите некоторое фиксированное значение; если вывод равен 1 , выведите другое фиксированное значение. Укажите выбранные выходные значения (например, 0/ 1или False/ True) в своем ответе.

Контрольные примеры

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

правила

  • Вы не можете использовать встроенные языковые модули, которые интерпретируют строки как код в каком-либо языке программирования и запускают его (например, JavaScript / Perl / Ruby / Python eval).
  • Тем не менее, ваш код на самом деле не должен анализировать и затем оценивать входную строку. Вы можете использовать любой подход, чтобы получить эквивалентные результаты и не нарушать предыдущее правило.
  • Ваша программа будет проверена perl -le 'print eval<>'.
  • Самый короткий код (в байтах) выигрывает.
Линн
источник
Как насчет использования встроенных языковых модулей, таких как eval, которые интерпретируют строки как код $ my_language после радикального изменения строки?
Адам
А как насчет встроенных функций, которые интерпретируют строки как код $ some_other_language ?
Мего
@ Adám Это было бы запрещено, извини.
Линн
@Mego Хм, там есть тривиальная возможность обмана, поэтому я расширил правило, чтобы охватить все подобные встроенные модули.
Линн
1
В свете тестов Мартина, возможно , было бы проще определить грамматику , как S → T | T ? S : S, T → 0 | 1, устраняя необходимость говорить о ассоциативности?
Питер Тейлор

Ответы:

5

GolfScript, 21 байт

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

Это выводы 0или 1. Предполагается, что вход имеет одну завершающую новую строку. Использование ~(которое оценивает строки) позволит сохранить байт:

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

Это основано на http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails_1462638030&gs .

Митч Шварц
источник
17

Сетчатка , 23 байта

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

Попробуйте онлайн! (Первая строка включает набор тестов, разделенных переводом строки.)

объяснение

Это довольно просто на самом деле. Ввод сводится к результату путем многократного ( +) вычисления троичных символов, содержащих только литералы. Чтобы убедиться, что это сделано справа ассоциативно, мы ищем совпадения справа налево ( r) и заменяем только последнее найденное совпадение ( -1=).

Само регулярное выражение либо сопоставляет 0\?.:и удаляет его (оставляя только материал после :), либо 1\?.:.заменяет его значением после ?.

Мартин Эндер
источник
Если регулярное выражение начинается справа, разве вы не должны обрабатывать 1совпадение st вместо -1st?
Утренняя монахиня
@LeakyNun К сожалению, я думаю, что я изменяю спички прежде, чем применить предел.
Мартин Эндер
10

Haskell, 106 101 100 90 83 байта

Это в значительной степени зависит от возможностей сопоставления с образцом в Haskell. Прежде всего, мы переворачиваем строку так, что мы можем просто выполнить поиск для первого вхождения b:a?x(который обычно читается как x?a:b) и заменить ее значением. Это автоматически обеспечивает правильную ассоциативность . Здесь мы используем x:xsшаблон. Это то, что fделает функция . Затем мы в основном применяем fк его выводу снова и снова, пока у нас не останется ни одного числа (0 или 1).

Спасибо @Lynn за 12 байтов!

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
источник
8

Brainfuck, 82 64 63 байта

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

Выход \xffдля 0и \x00для 1. Реализация мозгового перста должна позволять идти налево от стартовой ячейки.

Это существенно использует тот же подход , как Python xsot в ответ , но ветвление, вероятно , труднее следовать по сравнению с моим первоначальным представлением 82 байт:

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

(Для этого решения выходные данные предназначены \xfeдля 0и \xffдля 1, и более широкая совместимость достигается, когда ввод заканчивается новой строкой.)

Если вам не мешает проанализировать решение xsot, идея заключается в следующем: действуйте слева направо. Если вы видите, 1?то жадно откажитесь от него. Если вы видите, 0?тогда отбросьте все между этим и соответствующим :. Если ?второй символ не отображается, прекратите цикл и напечатайте первый символ оставшейся строки.

Таким образом, 82-байтовое решение фактически очень близко отражает эту схему. Внутренний цикл обрабатывает 0?, как внутренний цикл xsot. Некоторое внимание уделяется тому, чтобы войти в основной цикл без проверки любых вводимых символов; т.е. мы хотим проверить, находится ли второй символ ?только один раз в конце основного цикла, а не также в начале перед входом в основной цикл.

63-байтовое решение по существу объединяет внутренние и внешние циклы в один, что, как я подозревал, было возможно, учитывая сходство между этими циклами. Схема памяти в основном цикле может быть описана как:

[s] d c

где [x]означает текущую ячейку - sначинается как фиктивное ненулевое значение, которое просто указывает, что мы все еще выполняем цикл, и немедленно перезаписывается вводимым символом (или, 0или 1). dКлетка удерживает (отрицательную) глубину в случае , если мы находимся в середине 0?, в противном случае 0. Это cбудет либо ?либо, :либо перевод строки или EOF.

После обновления sи cмы обрабатываем 0?регистр, соответственно обновляя dи корректируя указатель, в противном случае мы используем текущее значение в cкачестве значения dна следующей итерации или остановим, если мы закончили.

Митч Шварц
источник
7

Python 2, 76 74 73 72 байта

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

С вводом в виде строкового литерала, чтобы избежать raw_.

Вывод 0или 1после <built-in function id>.

Митч Шварц
источник
1
Хаха, я только что прочитал твой ответ для b lang и собирался опубликовать почти идентичный ответ! Вот дополнительная оптимизация:3>>int(c)
xsot
Не хочешь объяснить, как это работает? Выглядит очень аккуратно
WorldSEnder
@WorldSEnder Я думаю, что это тип решения, который может быть сложно придумать, но легко понять, как только вы его увидите. Он проходит через строку назад и многократно обрабатывает крайнее правое условие, как и другие решатели.
Митч Шварц
Этот `id`трюк ... Молодцы :)
Линн
5

Python 2, 89 байт

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

Ввод принимается как строковый литерал.

xsot
источник
5

Грязь , 34 31 байт

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

Отпечатки 1для правдивых входов и 0ложных. Попробуйте онлайн! К сожалению, в последнем тесте на TIO не хватает памяти.

объяснение

Право-ассоциативность по сути означает, что в a?b:c, aвсегда либо, 0либо 1никогда более длинное выражение. Я просто рекурсивно определю шаблон, который соответствует истинному выражению, подобному этому, и проверю входные данные по нему. Также нет необходимости проверять, что каждое :действительно является a :, если все ?s проверены: во входных данных есть равное количество ?s и :s, и если некоторые из ?них неправильно классифицированы как a :, соответствующее :не будет соответствовать, и соответствие Грайма двигатель будет возвращаться назад.

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
источник
5

Haskell, 79 71 70 62 60 56 байт

Редактировать: Спасибо @Zgarb за 3 байта и @nimi за 4 байта!

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

Это рекурсивный подход, который несколько нарушает правило вывода с некоторым фиксированным значением . Редактирование: избавление от кортежей не только экономит 8 байтов, но также дает более хороший результат: "0"или "1".

Безголовая версия:

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)

Как это работает? Функция пересекает неявное дерево выражений
eval

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

и возвращает кортеж формы (result, rest).
Первый шаблон (x:'?':r1)совпадает xс '1'и r1с "0?0:1:0?1:0". Рекурсивное применение evalк r1вычисляет подвыражение 0?0:1и возвращает (0,":0?1:0"). Соответствие этому образцу (a,':':r2)дает a=0и r2=0?1:0. Эта под формула также рекурсивно оценивается так, что b='0'и r3="". Проверьте, если xесть '1'или '0'и верните либо (a, r3)или (b, r3).

Laikoni
источник
1
Хороший подход! Будет x>'0'работать на месте x=='1'?
Згарб
Спасибо, я не думал об этом, когда имел дело с символами.
Лайкони
1
Я думаю, что вы также можете заменить ':'на _.
Згарб
Да, тогда код работает даже для произвольных разделителей, а не просто :. Еще раз спасибо!
Лайкони
1
Ницца! Вы можете заменить if .. then .. elseс last$e s:[a:tail(e s)|x>'0'].
Ними
3

JavaScript (ES6), 53 байта

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

Возвращает 0или 1для правильного ввода; зависает для неверного ввода. Объяснение: поскольку в JavaScript изменение строки неудобно, моя первая попытка в 71 байт сработала с использованием отрицательного предвкушения для a, ?которое в противном случае нарушило бы ассоциативность:

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

Поскольку это было довольно долго, я задавался вопросом, могу ли я улучшить положение дел, включив принятие решений в регулярное выражение. Как оказалось, это не был немедленный успех, так как он также занимал 71 байт:

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

Тогда мне пришло в голову, что 0?0:и 0?1:всегда бездельники, не заботясь об ассоциативности. Это спасло меня почти на 25%.

Нил
источник
Ваш кодовый блок в верхней части отсутствует f=. Я не проверял, учитывает ли это количество ваших байтов или нет.
Патрик Робертс
@PatrickRoberts Я всегда так делаю, потому что копирую из журнала, который показывает только результат присваивания (которого, конечно, достаточно для нерекурсивных функций).
Нил
@Neil, вы можете копировать из журнала ввода вместо вывода
только ASCII
@MarsUltor Вход в журнал включает подсказку, которую я должен потом не забыть исключить. Это неуклюжий дополнительный шаг для нерекурсивных функций, поэтому я копирую из вывода по умолчанию.
Нил
3

Perl, 32 + 1 ( -pфлаг) = 33 байта

Полная заслуга @Mitch Swartch , поскольку его решение было на 14 байт короче моего!
Спасибо также @Neil, который предложил решение на 1 байт длиннее, чем Митч.

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

Необходимо -pпометить, как -M5.010или -Eзапустить. Например :

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"

Пояснения : Это в основном уменьшает блоки a?b:c(начиная с конца, чтобы убедиться, что не ?следует) в bили в cзависимости от истинности a, снова и снова, пока строка не содержит только 1или 0.

папа
источник
Не -засчитывается ли ваш счет? Хмм. Интересно ... Хороший ответ!
MayorMonty
@MayorMonty Для 1-строки вы можете вызвать ее из командной строки, perl -e '<code>'добавив, таким образом, pтолько 1 байт perl -pe '<code>'.
Нил
@ Нил Ааа, это имеет смысл
MayorMonty
На самом деле вам не нужно переворачивать строку, вы можете просто посмотреть отрицательно ?, я смог сократить это до 34 байт таким образом.
Нил
Вот 32 + 1:s/.*\K(1\?(.)..|0\?..)/\2/&&redo
Митч Шварц
2

Python 3, 93 69 байт

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

Ввод является строка в виде списка символов, выход либо "0"или"1"

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

Безголовая версия:

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

Еще одна попытка, но со значительно большим количеством байтов:

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
источник
Ваш ответ может быть функцией - вы можете удалить вторую строку.
Линн
Это явно не проверено, так как оно не проходит тестовые случаи, а версия без заглядывания выдает ошибку времени выполнения. Ваша основная идея хороша, хотя. С некоторыми изменениями я получаю 68 в Python 2 и 69 в Python 3.
Митч Шварц
1
Ну, я думаю, что для меня имеет больше смысла дать вам ответ, чем отредактировать его в своем собственном (так как я не думал об этом подходе, прежде чем я увидел ваш ответ) или сидеть без дела, пока ваш ответ глючит. Вот 68 я упомянул def f(s):x=s.pop(0);return[]<s<s.pop(0)>'>'and(f(s),f(s))[x<'1']or x, и для Python 3 с небольшим расстоянием редактирования до вашего, есть def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r.
Митч Шварц
Спасибо @MitchSchwartz, в основном разбираю справа, а не слева,
попал
1
В противном случае, слева вместо права, ~~~
WorldSEnder
1

САС, 75 74 68 (40 + 1 для -r) 41

:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t
Райли
источник
Вы, вероятно, можете сократить это, используя трюк @ MitchSchwartz в его комментарии , хотя вам, возможно, придется использовать (.*)и добавить дополнительный термин замены.
Нил
@ Нил, ты можешь быть прав, но я не могу понять, как заставить это работать.
Райли
Я написал это в чате, так как форматирование в комментарии может сбивать с толку: chat.stackexchange.com/transcript/message/31709640#31709640
Митч Шварц
@ MitchSchwartz Хех, пустые ярлыки работают? Но я думаю, что вы имели в виду \3вместо \2. Кроме того, вы можете присоединиться к линии, ;чтобы получить :;s/(.*)(1\?(.):.|0\?.:)/\1\3/;t.
Нил
@ Нейл у меня \3так, значит я случайно скопировал предыдущую версию. Я знаю о точках с запятой. Но чёрт, зачем вам использовать точку с запятой.
Митч Шварц
0

Утилиты Bash + GNU, 42

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

Подобная идея для большинства других совпавших по шаблону ответов.

Ideone .

Цифровая травма
источник
Вам не нужно захватывать первый символ в 0футляре, который экономит 5 байтов.
Нил