Konversi Ekspresi menjadi Notasi Panfix

19

Saya sedang menjelajahi esolang, dan kebetulan menggunakan bahasa ini: https://github.com/catseye/Quylthulg .

Satu hal yang menarik tentang bahasa ini, adalah bahwa ia tidak menggunakan awalan, postfix, atau infix, ia menggunakan ketiganya , menyebutnya "panfix" notasi.

Berikut ini sebuah contoh. Untuk mewakili infiks yang normal 1+2di panfix, menjadi: +1+2+. Perhatikan bagaimana operator keduanya sebelum, di antara, dan setelah operan. Contoh lain adalah (1+2)*3. Ini menjadi *+1+2+*3*. Perhatikan lagi bagaimana *di ketiga tempat sehubungan dengan operan +1+2+dan 3.

Tantangan

Seperti yang sudah Anda tebak, tugas Anda dalam tantangan ini adalah mengubah ekspresi dari infix ke panfix.

Beberapa klarifikasi:

  • Anda hanya perlu berurusan dengan empat operasi dasar: +-*/
  • Anda tidak perlu berurusan dengan versi unary itu, hanya biner
  • Anda harus berurusan dengan tanda kurung
  • Asumsikan aturan presedensi normal */saat itu +-dan tinggalkan asosiasi untuk mereka semua.
  • Angka-angka akan menjadi bilangan bulat tidak negatif
  • Secara opsional Anda dapat memiliki spasi di input dan output

Uji Kasus

1+2  ->  +1+2+
1+2+3  ->  ++1+2++3+
(1+2)*3  ->  *+1+2+*3*
10/2*5  ->  */10/2/*5*
(5+3)*((9+18)/4-1)  ->  *+5+3+*-/+9+18+/4/-1-*

Ini adalah kode-golf , jadi kode terpendek dalam byte menang!

code-golf parsing conversion Maltysen
sumber

Jawaban:

3

JavaScript (ES6), 160 byte

f=(s,t=s.replace(/[*-/]/g,"'$&'"),u=t.replace(/^(.*?)([*-9]+)'([*/])'([*-9]+)|([*-9]+)'([+-])'([*-9]+)|\(([*-9]+)\)/,"$1$3$2$3$4$3$6$5$6$7$6$8"))=>t==u?t:f(s,u)

Bekerja dengan mengutip semua operator (yang memberi mereka kode karakter sebelumnya *), kemudian mencari tersedia '*'atau '/'operasi, '+'atau '-'operasi atau ()s, dan mengganti yang pertama dengan notasi perbaikannya. Contoh:

(5+3)*((9+18)/4-1)
(5'+'3)'*'((9'+'18)'/'4'-'1)
(+5+3+)'*'((9'+'18)'/'4'-'1)
+5+3+'*'((9'+'18)'/'4'-'1)
+5+3+'*'((+9+18+)'/'4'-'1)
+5+3+'*'(+9+18+'/'4'-'1)
+5+3+'*'(/+9+18+/4/'-'1)
+5+3+'*'(-/+9+18+/4/-1-)
+5+3+'*'-/+9+18+/4/-1-
*+5+3+*-/+9+18+/4/-1-*
Neil
sumber
3

JavaScript (ES6), 285 282 281 267 251 243 241 238 234 232 231 byte

~ 15 byte terima kasih kepada Neil .

f=(I,E=I.match(/\d+|./g),i=0)=>(J=T=>T.map?T.map(J).join``:T)((R=(H,l=(P=_=>(t=E[i++])<")"?R(0):t)(),C,F)=>{for(;(C=P())>")"&&(q=C>"*"&&C<"/")*H-1;)F=q+H?l=[C,l,C,P(),C]:F?l[3]=[C,l[3],C,R(1),C]:l=R(1,l,i--)
i-=C>")"
return l})(0))

Dalam JavaScript ini sedikit lebih sulit daripada di Mathematica. Ini pada dasarnya adalah parser prioritas operator yang terlalu khusus dan golf .

Menyebabkan stack overflow pada input yang tidak valid.

Demo

Tampilkan cuplikan kode

Tidak disatukan

convert = input => {
  tokens = input.match(/\d+|./g);
  i = 0;
  parse_token = () => (token = tokens[i++]) == "(" ? parse_tree(false) : token;
  parse_tree = (mul_div_mode, left = parse_token()) => {
    while ((oper = parse_token()) != ")" && !((is_plus_minus = oper == "+" || oper == "-") && mul_div_mode)) {
      if (is_plus_minus || mul_div_mode)
        left = [oper, left, oper, parse_token(), oper];
      else if (non_first)
        left[3] = [oper, left[3], oper, parse_tree(true), oper];
      else
        left = parse_tree(true, left, i--);
      non_first = true;
    }
    if (oper != ")")
      i--;
    return left;
  };
  format_tree = tree => tree.map ? tree.map(format_tree).join("") : tree;
  return format_tree(parse_tree(false));
}
PurkkaKoodari
sumber
S.split``seharusnya [...S], meskipun sebenarnya bisa membantu untuk mencocokkan di /\d+|./gmuka dan bekerja sebagai gantinya.
Neil
@Neil Terima kasih. Saya akan melihat itu.
PurkkaKoodari
2

Mathematica, 203 195 byte

Ini mungkin kurang efisien, tetapi tampaknya melakukan pekerjaan itu.

Function[f,ReleaseHold[(Inactivate@f/._[Plus][a_,b_/;b<0]:>a~"-"~-b//Activate@*Hold)//.a_/b_:>a~"/"~b/.{a_Integer:>ToString@a,Plus:>"+",Times:>"*"}]//.a_String~b_~c_String:>b<>a<>b<>c<>b,HoldAll]

Ini adalah fungsi anonim yang mengambil ekspresi aktual dan mengembalikan string dengan notasi panfix. Mathematica memilah prioritas operator pada waktu parsing, daripada waktu evaluasi, sehingga sarang harus benar secara otomatis. Setidaknya kasus uji berfungsi seperti yang diharapkan.

Penjelasan: Cukup mudah untuk menafsirkan seluruh ekspresi sebagai pohon, seperti:

pohon

Pada tahap ini operator (setiap node yang bukan daun) bukan operator lagi, mereka sebenarnya telah dikonversi ke string seperti "+". Bilangan bulat juga dilemparkan ke string. Kemudian aturan penggantian berulang mengubah setiap node yang memiliki tepat dua daun untuk panfix parent-leaf1-parent-leaf2-parent. Setelah beberapa iterasi, pohon direduksi menjadi satu string.

Kerugian utama dalam jumlah byte adalah bahwa Mathematica mengartikan

5 - 4 -> 5 + (-4)
9 / 3 -> 9 * (3^(-1))

Dan ini terjadi juga pada saat penguraian.

Golf turun sedikit, karena polanya a_/b_juga diartikan sebagai a_ * (b_)^(-1). Juga beberapa optimasi kecil di tempat lain.

LLlAMnYP
sumber
1

Prolog, 87 byte

x(T)-->{T=..[O,A,B]}->[O],x(A),[O],x(B),[O];[T].
p:-read(T),x(T,L,[]),maplist(write,L).

Ini adalah fungsi (kebanyakan karena menulis program lengkap memiliki tingkat mimpi buruk boilerplate di Prolog; biasanya, bahkan jika Anda menyusun program, ia menghasilkan REPL saat dijalankan), dipanggil p. Dibutuhkan input dari stdin dan output di stdout. Perhatikan bahwa Anda perlu menambahkan periode pada input, yang merupakan konsekuensi yang tidak menguntungkan dari cara kerja rutin input Prolog (mereka menggunakan periode dalam input dengan cara yang sama seperti bahasa lain menggunakan baris baru); yang mungkin atau mungkin tidak mendiskualifikasi jawabannya.

Penjelasan

Operator aritmatika, dalam Prolog, biasanya ditafsirkan sebagai konstruktor tuple . Namun, mereka mematuhi aturan diutamakan yang sama dengan operator aritmatika aktual yang menjadi basis mereka; Anda dapat membentuk tupel dengan notasi infiks, dan +dan -mengikat kurang ketat dari *dan /, dengan diutamakan kiri ke kanan dalam suatu grup. Inilah tepatnya pertanyaan yang ditanyakan; dengan demikian, kita dapat membaca seluruh nested tuple dari input, dan sudah memiliki struktur yang tepat. Itu yang pdilakukannya.

Selanjutnya, kita perlu mengubahnya menjadi notasi perbaikan. xmengkonversi input ke dalam daftar panfixed dari konstruktor dan bilangan bulat, dan dapat dibaca sebagai sebuah kalimat bahasa Inggris hampir secara langsung: " xdari Tadalah: jika Tadalah tuple dengan konstruktor Odan argumen A, Bmaka O, xdari A, O, xdari B, O, yang lain T". Akhirnya, kita hanya perlu mencetak daftar tanpa pemisah (yaitu menggunakan maplistuntuk memanggil writesetiap elemen dari daftar).

Saya menggunakan SWI-Prolog untuk menguji ini, karena versi GNU Prolog saya maplistbelum (tampaknya sudah ditambahkan ke versi yang lebih baru), tetapi umumnya cukup portabel antara implementasi Prolog.

Komunitas
sumber