Mengevaluasi ekspresi operator ternary

29

Pertimbangkan tata bahasa lebih alfabet { 0, 1, ?, :} yang didefinisikan oleh aturan produksi

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

Diberikan string yang dihasilkan dari s , parsing sebagai ekspresi di mana ?:asosiatif-benar (misalnya, a?B?X:Y:c?d:e?f:gberarti a?(B?X:Y):(c?d:(e?f:g))) dan mengevaluasinya dengan semantik berikut:

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

Jika hasilnya 0 , hasilkan beberapa nilai tetap; jika output 1 , output nilai tetap berbeda. Tentukan nilai output yang Anda pilih (misalnya 0/ 1, atau False/ True) dalam jawaban Anda.

Uji kasus

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

Aturan

  • Anda tidak boleh menggunakan bahasa bawaan yang menafsirkan string sebagai kode dalam beberapa bahasa pemrograman dan menjalankannya (seperti JavaScript / Perl / Ruby / Python eval).
  • Yang mengatakan, kode Anda sebenarnya tidak harus diuraikan dan kemudian mengevaluasi string input. Anda dapat mengambil pendekatan apa pun untuk mencapai hasil yang setara dan tidak melanggar aturan sebelumnya.
  • Program Anda akan diperiksa perl -le 'print eval<>'.
  • Kode terpendek (dalam byte) menang.
Lynn
sumber
Bagaimana kalau menggunakan built-in bahasa seperti eval yang mengartikan string sebagai $ my_language code setelah mengubah string secara radikal?
Adám
Bagaimana dengan builtin yang mengartikan string sebagai $ some_other_language kode?
Mego
@ Adám Itu tidak diizinkan, maaf.
Lynn
@Mego Hmm, ada peluang curang yang sepele di sana, jadi saya memperpanjang aturan untuk mencakup semua built-in tersebut.
Lynn
1
Dalam terang uji Martin kasus, mungkin akan lebih sederhana untuk menentukan tata bahasa sebagai S → T | T ? S : S, T → 0 | 1, menghilangkan kebutuhan untuk berbicara tentang associativity?
Peter Taylor

Jawaban:

17

Retina , 23 byte

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

Cobalah online! (Baris pertama memungkinkan suite tes yang dipisahkan dengan linefeed.)

Penjelasan

Ini sebenarnya cukup sederhana. Input dikurangi ke hasil dengan berulang kali ( +) mengevaluasi terner yang hanya mengandung literal. Untuk memastikan ini dilakukan dengan benar secara asosiatif, kami mencari kecocokan dari kanan ke kiri ( r) dan hanya mengganti kecocokan terakhir yang kami temukan ( -1=).

Regex itu sendiri cocok 0\?.:dan menghapusnya (hanya menyisakan barang setelah :) atau 1\?.:.dan menggantinya dengan nilai setelah ?.

Martin Ender
sumber
Jika regex dimulai dari kanan maka bukankah seharusnya Anda memproses 1pertandingan st bukan -1st?
Leaky Nun
@ LeakyNun Sayangnya, saya pikir saya membalik pertandingan sebelum menerapkan batas.
Martin Ender
10

Haskell, 106 101 100 90 83 byte

Ini sangat bergantung pada kemampuan pencocokan pola pola Haskell. Pertama-tama, kita membalikkan string sehingga kita bisa mencari kejadian pertama b:a?x(yang biasanya dibaca sebagai x?a:b) dan menggantinya dengan nilainya. Ini secara otomatis memberikan asosiasi yang tepat . Di sini kita menggunakan x:xspola. Inilah fungsi fyang dilakukan. Kemudian kami pada dasarnya berlaku funtuk output itu berulang-ulang, sampai kami memiliki satu nomor (0 atau 1) yang tersisa.

Terima kasih @ Lynn untuk 12 byte!

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
cacat
sumber
8

Brainfuck, 82 64 63 byte

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

Outputnya adalah \xffuntuk 0dan \x00untuk 1. Implementasi brainfuck harus memungkinkan untuk pergi ke kiri sel awal.

Ini pada dasarnya menggunakan pendekatan yang sama dengan jawaban Python xsot , tetapi percabangannya mungkin lebih sulit untuk diikuti dibandingkan dengan pengiriman 82 byte awal saya:

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

(Untuk solusi ini, output adalah \xfeuntuk 0dan \xffuntuk 1, dan kompatibilitas yang lebih luas dicapai ketika input berakhir dengan baris baru.)

Jika Anda tidak dapat repot-repot menganalisis solusi xsot, idenya adalah ini: Lanjutkan dari kiri ke kanan. Jika Anda melihat 1?maka dengan rakus buanglah. Jika Anda melihat 0?maka buang semuanya antara itu dan yang sesuai :. Ketika ?tidak muncul sebagai karakter kedua, hentikan perulangan dan cetak karakter pertama dari string yang tersisa.

Jadi, solusi 82-byte sebenarnya mencerminkan skema itu dengan cukup dekat. Loop dalam menangani 0?, seperti loop dalam xsot. Beberapa perhatian diambil untuk memasuki loop utama tanpa memeriksa karakter input apa pun; yaitu, kami ingin memeriksa apakah karakter kedua ?hanya sekali di akhir loop utama, dan tidak juga di awal sebelum memasukkan loop utama.

Solusi 63-byte pada dasarnya menggabungkan loop dalam dan luar menjadi satu, yang saya duga dimungkinkan karena kesamaan antara loop tersebut. Tata letak memori dalam loop utama dapat digambarkan sebagai:

[s] d c

di mana [x]berarti sel saat ini - sdimulai sebagai nilai bukan nol boneka yang hanya menunjukkan kita masih mengulang, dan segera ditimpa dengan karakter input (baik 0atau 1). The dsel memegang (negatif) kedalaman dalam kasus kita berada di tengah-tengah 0?, sebaliknya 0. The cakan menjadi baik ?atau :atau baris baru atau EOF.

Setelah memperbarui sdan c, kami menangani 0?kasing dengan memperbarui yang dsesuai dan menyesuaikan pointer, jika tidak kami menggunakan nilai saat ini csebagai nilai ddalam iterasi berikutnya, atau berhenti jika kami selesai.

Mitch Schwartz
sumber
7

Python 2, 76 74 73 72 byte

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

Dengan input sebagai string literal yang harus dihindari raw_.

Outputnya 0atau 1diikuti oleh <built-in function id>.

Mitch Schwartz
sumber
1
Haha, saya baru saja membaca jawaban Anda untuk b lang dan akan memposting jawaban yang hampir identik! Berikut ini optimasi tambahan:3>>int(c)
xsot
Mau jelaskan bagaimana ini bekerja? Terlihat sangat rapi
WorldSEnder
@ WorldSEnder Saya pikir ini adalah jenis solusi yang bisa sulit untuk dibuat, tetapi mudah dimengerti setelah Anda melihatnya. Ini berjalan melalui string mundur dan berulang kali memproses kondisional paling kanan, seperti yang dilakukan pemecah lainnya juga.
Mitch Schwartz
Itu `id`trik ...! Bagus :)
Lynn
5

Python 2, 89 byte

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

Input diambil sebagai string literal.

xsot
sumber
5

Grime , 34 31 byte

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

Mencetak 1untuk input yang benar dan 0yang salah. Cobalah online! Kasing uji terakhir sayangnya kehabisan memori pada TIO.

Penjelasan

Asosiatif-kanan pada dasarnya berarti bahwa a?b:c, aselalu 0atau 1tidak pernah, merupakan ekspresi yang lebih panjang. Saya hanya akan secara rekursif mendefinisikan pola yang cocok dengan ekspresi yang benar seperti itu, dan memeriksa input yang menentangnya. Ini juga tidak perlu untuk memeriksa bahwa setiap :benar-benar a :, jika ?s semua dicentang: ada jumlah ?s dan :s yang sama dalam input, dan jika ada ?yang salah diklasifikasikan sebagai :, yang sesuai :akan gagal untuk mencocokkan, dan pencocokan Grime mesin akan mundur.

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
sumber
5

Haskell, 79 71 70 62 60 56 byte

Sunting: Terima kasih kepada @Zgarb selama 3 byte dan untuk @nimi selama 4 byte!

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

Ini pendekatan rekursif yang agak menyalahgunakan aturan "beberapa nilai tetap" . Sunting: Menyingkirkan tuple tidak hanya menghemat 8 byte, ia juga menghasilkan output yang lebih bagus: "0"atau "1".

Versi tidak disatukan:

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)

Bagaimana cara kerjanya?
The evalFungsi melintasi pohon implisit dari ekspresi

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

dan mengembalikan tuple formulir (result, rest).
Pola pertama (x:'?':r1)cocok xdengan '1'dan r1ke "0?0:1:0?1:0". Melamar secara rekursif evaluntuk r1mengevaluasi sub ekspresi 0?0:1dan pengembalian (0,":0?1:0"). Mencocokkan ini dengan (a,':':r2)hasil pola a=0dan r2=0?1:0. Sub-formula ini juga dievaluasi secara rekursif sehingga b='0'dan r3="". Periksa apakah xini '1'atau '0'dan kembali baik (a, r3)atau (b, r3).

Laikoni
sumber
1
Pendekatan yang bagus! Akan x>'0'bekerja di tempat x=='1'?
Zgarb
Terima kasih, saya tidak memikirkan itu saat berurusan dengan karakter.
Laikoni
1
Saya pikir Anda juga bisa menggantinya ':'dengan _.
Zgarb
Ya, maka kode itu bahkan berfungsi untuk pembatas yang arbitrer, bukan hanya :. Terima kasih lagi!
Laikoni
1
Bagus! Anda dapat mengganti if .. then .. elsedengan last$e s:[a:tail(e s)|x>'0'].
nimi
3

JavaScript (ES6), 53 byte

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

Pengembalian 0atau 1untuk input yang valid; hang untuk input yang tidak valid. Penjelasan: karena membalikkan string adalah canggung dalam JavaScript, upaya 71-byte pertama saya berhasil dengan menggunakan lookahead negatif untuk ?yang akan mengganggu asosiatif:

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

Karena ini agak lama saya bertanya-tanya apakah saya bisa memperbaiki masalah dengan memasukkan pengambilan keputusan ke dalam regexp. Ternyata, itu bukan kesuksesan langsung, karena juga butuh 71 byte:

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

Kemudian terpikir olehku bahwa 0?0:dan 0?1:selalu tanpa usaha, tanpa memperhatikan asosiatif. Ini menyelamatkan saya hampir 25%.

Neil
sumber
Blok kode Anda di bagian atas tidak ada f= . Saya belum memeriksa apakah jumlah byte Anda memperhitungkannya atau tidak.
Patrick Roberts
@ PatrickRoberts Saya selamanya melakukan itu, karena saya salin dari log, yang hanya menunjukkan hasil tugas (yang tentu saja cukup untuk fungsi non-rekursif).
Neil
@Nil, Anda dapat menyalin dari input log bukan output
ASCII-hanya
@MarsUltor Input log berisi prompt, yang harus saya ingat untuk mengecualikannya. Ini adalah langkah ekstra canggung untuk fungsi non-rekursif, itulah sebabnya saya menyalin dari output secara default.
Neil
3

Perl, 32 + 1 ( -pflag) = 33 byte

Penghargaan penuh untuk @Mitch Swartch , karena solusinya 14 byte lebih pendek dari saya!
Terima kasih juga kepada @Neil yang menyarankan solusi 1 byte lebih lama dari Mitch.

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

Membutuhkan -pflag, juga -M5.010atau -Euntuk menjalankan. Contohnya :

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"

Penjelasan : Ini pada dasarnya mengurangi bloka?b:c (mulai dari akhir untuk memastikan tidak ada yang ?mengikuti) menjadi batau ctergantung pada kebenaran a, berulang dan berulang sampai string hanya berisi 1atau 0.

Dada
sumber
Apakah -tidak diperhitungkan skor Anda? Hrm Menarik ... Jawaban bagus!
MayorMonty
@ MayorMonty Untuk 1-liner Anda dapat memanggilnya pada baris perintah perl -e '<code>'dengan menggunakan sehingga phanya menambah biaya 1 byte perl -pe '<code>'.
Neil
@Neil Ahh, itu masuk akal
MayorMonty
Sebenarnya Anda tidak perlu membalikkan string, Anda hanya bisa mencari negatif ke depan untuk ?, saya bisa memotong ini menjadi 34 byte dengan cara ini.
Neil
Berikut ini 32 + 1:s/.*\K(1\?(.)..|0\?..)/\2/&&redo
Mitch Schwartz
2

Python 3, 93 69 byte

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

Input adalah string sebagai daftar karakter, output dapat "0"atau"1"

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

Versi tidak disatukan:

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

Percobaan lain, tetapi dengan byte lebih banyak:

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
sumber
Jawaban Anda mungkin sebuah fungsi - Anda dapat menghapus baris kedua.
Lynn
Ini jelas belum teruji, karena tidak lulus uji kasus, dan versi yang tidak diklik memberikan kesalahan runtime. Ide dasar Anda bagus. Dengan beberapa penyesuaian saya mendapatkan 68 di Python 2 dan 69 di Python 3.
Mitch Schwartz
1
Yah saya pikir lebih masuk akal bagi saya untuk memberi Anda jawaban daripada mengeditnya sendiri (karena saya tidak memikirkan pendekatan semacam ini sebelum saya melihat jawaban Anda) atau duduk-duduk menunggu sementara jawaban Anda bermasalah. Berikut adalah 68 yang saya sebutkan def f(s):x=s.pop(0);return[]<s<s.pop(0)>'>'and(f(s),f(s))[x<'1']or x, dan untuk Python 3 dengan jarak edit kecil untuk Anda, ada 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
Terima kasih @MitchSchwartz, cukup banyak parse dari kanan, bukannya kiri, gotcha
WorldSEnder
1
Di sisi lain, kiri bukannya kanan, ~~~
WorldSEnder
1

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

:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t
Riley
sumber
Anda mungkin dapat mengurangi ini menggunakan trik @ MitchSchwartz dalam komentarnya , meskipun Anda mungkin harus menggunakan (.*)dan menambahkan istilah penggantian tambahan.
Neil
@Neil, Anda mungkin benar, tapi saya tidak tahu cara membuatnya bekerja.
Riley
Saya menulisnya dalam obrolan, karena memformat dalam komentar mungkin membingungkan: chat.stackexchange.com/transcript/message/31709640#31709640
Mitch Schwartz
@MitchSchwartz Heh, label kosong berfungsi? Tapi saya pikir Anda maksudkan \3bukan \2. Anda juga dapat bergabung dengan garis ;untuk mendapatkan :;s/(.*)(1\?(.):.|0\?.:)/\1\3/;t.
Neil
@Neil saya sudah \3jadi itu berarti saya tidak sengaja menyalin versi sebelumnya. Saya tahu tentang titik koma. Tapi yuck, mengapa Anda ingin menggunakan titik koma.
Mitch Schwartz
0

Utilitas Bash + GNU, 42

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

Ide yang mirip dengan sebagian besar jawaban pencocokan pola lainnya.

Ideone .

Trauma Digital
sumber
Anda tidak perlu menangkap karakter pertama dalam 0kasing, yang menghemat 5 byte.
Neil