Quylthulg adalah bahasa oleh Chris Pressey yang mencoba memecahkan masalah notasi infiks menggunakan apa yang disebut panfix :
seperti postfix, panfix tidak memerlukan penyebaran perangkat misterius seperti tanda kurung untuk mengesampingkan prioritas operator default. Pada saat yang sama, panfix memungkinkan istilah yang akan ditentukan dalam urutan dan cara yang sama seperti infix, notasi alami dan intuitif yang tidak diragukan lagi bagi mereka yang telah terbiasa dengannya.
Bagaimana Anda mendapatkan kenyamanan notasi infiks bersama dengan ambiguitas awalan atau postfix? Gunakan ketiganya, tentu saja!
=y=+*3*x*+1+=
Secara lebih formal, mari +
menjadi operator, a
dan b
menjadi ekspresi. Kemudian (a+b)
adalah ekspresi infiks yang valid (dalam tanda kurung), representasi panfix dari ekspresi itu adalah +a+b+
, di mana penjajaran mewakili penggabungan.
Tujuan Anda adalah untuk mengambil string panfix dan mengonversinya menjadi infiks yang dipatenkan sepenuhnya:
(y=((3*x)+1))
Untuk mempermudah, kami akan melakukan perubahan berikut:
- Operator hanya dapat terdiri dari dua karakter unik (Anda dapat memilih, tetapi di sini saya akan menggunakan
*
dan+
). - Hanya ada satu literal, yang terdiri dari karakter lain yang berbeda (Anda dapat memilih salah satunya, tetapi di sini saya akan menggunakan
_
). - Input akan menjadi ekspresi panfix yang terbentuk dengan baik.
Untuk kompleksitas , kami akan melakukan perubahan berikut:
- Operator dapat terdiri dari sejumlah karakter positif , bukan hanya satu.
Ini membuat tantangan lebih rumit karena Anda tidak dapat selalu menentukan bagaimana substring yang diberikan karakter operator dipartisi tanpa melihat sisa string.
Berikut ini adalah implementasi referensi untuk tantangan, milik @ user202729.
Uji Kasus
format: input -> output
+*+_*+_*+++_+*+_*+_*+++ -> ((_*+_)+(_+(_*+_)))
**++*+***++_+_++_+*++*+***_*++*+*****_**_*_*** -> ((((_+_)+_)*++*+***_)*(_*(_*_)))
***_**_***_* -> ((_**_)*_)
+_+_+ -> (_+_)
*+*+++**+***+++++_*+*+++**+***+++++_*+*+++**+***+++++ -> (_*+*+++**+***+++++_)
*++++*+*_*_*+*+++****+_++****+_++****++*+*+++_*+++ -> (((_*_)+*+(_++****+_))*+++_)
+**+_*+_*+*_*+*_*+*_+*_+**+ -> (((_*+_)*_)+(_*(_+*_)))
+**+++++_+++++_+++++*_*+*+_++++++_+++++_+++++++* -> (((_+++++_)*_)+*(_+(_+++++_)))
+*+*+_+*+_+*+*_*+*_*+*+_+*+_+*+*+ -> (((_+*+_)*_)+(_*(_+*+_)))
**_**_**_*_****_* -> ((_*(_*(_*_)))*_)
Saya menggunakan program ini untuk menghasilkan string infiks untuk tantangan ini (mengkonversi ke panfix itu sepele, tetapi membalikkan tidak).
**_**_**_*_****_*
. Semua jawaban yang saya uji semuanya gagal.(_ + _)
?Jawaban:
Prolog (SWI) ,
194163 byteMenyimpan 31 byte kekalahan menggunakan tip ini dari 0 ' !
Operator
^
mengambil untuk argumen kirinya string yang berisi ekspresi panfix dan menetapkan argumen kanannya ke string yang berisi ekspresi infiks kurung yang sesuai. Ini digunakanx
sebagai literal di tempat_
.Cobalah online!
Penjelasan
Karena Prolog adalah bahasa deklaratif, kita hanya perlu menjelaskan hubungan antara panfix dan ekspresi yang di-kurung.
Penjelasannya menggunakan versi yang sedikit tidak diubah ini:
Produksi utama kami adalah
parenthesize
, yang menggunakan ekspresi panfixX
sebagai string dan mengirimkan ekspresi infiks kurung yang sesuaiP
sebagai string. Ini digunakanstring_chars
untuk mengubah string input menjadi daftar karakter dan kemudian meneruskannya keexpr
.expr
mengambil daftar karakterL
, mem-parsing ekspresi panfix pertama yang ditemukannyaL
, dan mengirimkan setara tanda kurungX
dan sisanya dari daftar karakterR
. Ada dua jenis ekspresi yang mungkin:L
adalahx
, maka ekspresi adalahx
dan sisanya adalah segalanya setelahx
.O
(lihat dioper
bawah); parsing ekspresiY
; parseO
lagi; uraikan ungkapan lainZ
; dan uraikanO
untuk ketiga kalinya. Sisanya adalah segalanya setelah instance ketiga dariO
. Ekspresi adalah hasil dari bergabungY
,O
danZ
, dikelilingi oleh kurung, ke dalam string.oper
mengambil daftar karakter, di mana karakter pertama beradaC
dan sisanya beradaT
; itu mem-parsing operator (yaitu menjalankan satu atau lebih karakter operator) dan mengirimkan operatorO
dan sisa daftar karakterR
. Untuk membentuk operator, karakterC
harus berupa sesuatu selainx
; jugaP
harus dapat diuraikan dariT
, dengan sisanyaR
; dalam hal ini,O
adalah gabungan dariC
danP
; atau,O
adalah karakter tunggalC
; dalam hal ini,R
adilT
.Contoh yang berhasil
Mari kita ambil input
+*+x+x++*x+*
sebagai contoh.+*+x+x++*x+*
. Ini tidak dimulai denganx
, jadi kami mengurai operator dari awal.oper
akan mem-parsing operator sebesar mungkin, jadi kami mencoba+*+
.x+x++*x+*
. Ini pastix
.+*+
,, dari+x++*x+*
. Namun, ini gagal .+*
sebagai gantinya.+x+x++*x+*
. Ini tidak dimulai denganx
, jadi kita perlu mengurai operator.+
.x+x++*x+*
. Ini pastix
.+
lagi dari+x++*x+*
.x++*x+*
. Ini pastix
.+
lagi dari++*x+*
.(x+x)
.+*
lagi+*x+*
.x+*
. Ini pastix
.+*
lagi dari+*
.((x+x)+*x)
.Karena tidak ada lagi karakter yang tersisa, kami telah berhasil menerjemahkan ekspresi.
sumber
Perl,
7860585750 byteTermasuk
+1
untukp
Penggunaan
1
untuk+
dan2
untuk*
(atau sebenarnya digit apa pun bekerja untuk operator apa pun)Untuk pengujian yang mudah dibandingkan contoh yang diberikan, Anda dapat menggunakan ini yang melakukan terjemahan dan penghapusan ruang untuk Anda:
sumber
Bersih ,
200192189 byteCobalah online!
Menentukan fungsi
f
, mengambilString
, dan mengembalikan singleton[String]
dengan hasil di dalamnya.Beberapa hal rapi:
_
sumber
Retina 0.8.2 , 138 byte
Cobalah online! Tautan termasuk kasus uji lebih cepat. Penjelasan: Mesin regex menggunakan backtracking untuk membagi string menjadi token yang kemudian didorong atau muncul dari
i
kelompok balancing. Selalu ada setidaknya satu operator yang didorong di awal sebelum variabel pertama. Setelah variabel, setidaknya satu operator muncul, pada titik mana operator didorong dijalankan atau variabel lain legal. Operator didorong ke grup dalam rangkap sehingga mereka dapat muncul dengan benar. Contoh:Sayangnya ini tidak membantu kami menangkap hasilnya untuk mengurungnya, sehingga operator luar dicocokkan secara manual. Tanda kurung ditambahkan di luar-dalam, jadi tahap pertama membungkus seluruh ekspresi dalam tanda kurung dan tahap terakhir menghapusnya sekarang karena mereka telah menyebar ke variabel.
sumber
**_**_**_*_****_*
.Haskell ,
167166 byteCobalah online! Contoh penggunaan:
head.e "**_**_**_*_****_*"
hasil((_*(_*(_*_)))*_)
. Semua karakter kecuali_
ditafsirkan sebagai operator,_
itu sendiri menunjukkan pengenal.sumber
Python 3, 226 byte
Menentukan fungsi anonim bernama
R
.Cobalah secara Online!
sumber
_*+
; itu hanya apa yang digunakan dalam contoh. Anda mungkin dapat menggunakan ini untuk mengatur regex Anda (misalnya dengan menggunakan\d
alih-alih[*+]
).