Terapkan Notasi Anyfix!

16

Dalam notasi awalan, operator datang sebelum argumen, sehingga Anda bisa membayangkan bahwa operator memanggil next()yang secara rekursif dipanggil. Dalam notasi infiks, operator beralih di antara argumen, sehingga Anda dapat membayangkannya hanya sebagai parse tree. Dalam notasi postfix, operator datang setelah argumen, jadi Anda bisa membayangkannya sebagai berbasis stack.

Dalam notasi perbaikan apa pun, operator dapat pergi ke mana saja * . Jika operator muncul dan tidak ada cukup argumen, maka operator menunggu sampai ada cukup argumen. Untuk tantangan ini, Anda harus menerapkan evaluator perbaikan apa pun yang sangat mendasar. (Perhatikan bahwa perbaikan apa pun adalah bahasa rekreasional yang saya tinggalkan yang dapat Anda mainkan di sini atau lihat di sini )

Anda harus mendukung perintah berikut:

(Arity 1)

  • duplikat
  • negatif

(Arity 2)

  • tambahan
  • perkalian
  • kesetaraan: pengembalian 0atau 1.

Anda dapat memilih untuk menggunakan lima simbol non-spasi putih untuk perintah ini. Untuk tujuan demonstrasi, saya akan menggunakan "sebagai duplikat, ×sebagai perkalian, dan +sebagai tambahan.

Untuk literal, Anda hanya perlu mendukung bilangan bulat non-negatif, tetapi juru bahasa Anda harus dapat memuat semua bilangan bulat (dalam rentang bilangan bulat (wajar) bahasa Anda).

Mari kita lihat sebuah contoh: 10+5. Penyimpanan harus berperilaku sebagai tumpukan, bukan antrian. Jadi pertama-tama, tumpukan dimulai [], dan daftar operator yang antri dimulai pada []. Kemudian, literal 10dievaluasi yang membuat stack [10]. Selanjutnya, operator +dievaluasi, yang membutuhkan dua argumen. Namun, hanya ada satu argumen di stack, sehingga daftar operator yang antri menjadi ['+']. Kemudian, literal 5dievaluasi yang membuat stack [10, 5]. Pada titik ini, operator '+'dapat dievaluasi sehingga, membuat tumpukan [15]dan antrian [].

Hasil akhir harus [15]untuk + 10 5, 10 + 5, dan 10 5 +.

Mari kita lihat contoh lebih keras: 10+". Tumpukan dan antrian dimulai dengan []dan []. 10dievaluasi terlebih dahulu yang membuat stack [10]. Selanjutnya, +dievaluasi, yang tidak mengubah tumpukan (karena tidak ada cukup argumen) dan membuat antrian ['+']. Kemudian, "dievaluasi. Ini bisa langsung berjalan begitu saja, membuat stack [10, 10]. +sekarang dapat dievaluasi sehingga tumpukan menjadi [20]dan antrian []. Hasil akhirnya adalah [20].

Bagaimana dengan urutan operasi?

Mari kita lihat ×+"10 10. Tumpukan dan antrian memulai keduanya sebagai []:

  • ×: Tumpukan tidak berubah dan antrian menjadi ['×'].
  • +: Tumpukan tidak berubah dan antrian menjadi ['×', '+'].
  • ": Tumpukan tidak berubah dan antrian menjadi ['×', '+', '"'].
  • 10: Tumpukan menjadi [10]. Meskipun ×harus menjadi operator pertama yang dievaluasi sejak muncul pertama kali, "dapat segera berjalan dan tidak ada operator sebelum itu, sehingga dievaluasi. Tumpukan menjadi [10, 10]dan antrian ['×', '+']. ×sekarang dapat dievaluasi, yang membuat tumpukan [100]dan antrian ['+'].
  • 10: Tumpukan menjadi [100, 10], yang memungkinkan +untuk dievaluasi. Tumpukan menjadi [110]dan antrian [].

Hasil akhirnya adalah [110].

Perintah yang digunakan dalam demonstrasi ini konsisten dengan perintah dari bahasa perbaikan apa pun; namun, contoh terakhir tidak akan berfungsi karena ada bug pada juru bahasa saya. (Penafian: Kiriman Anda tidak akan digunakan dalam penerjemah perbaikan apa pun)

Tantangan

Pilih satu set 5 karakter non-spasi-kosong non-digit dan buat penerjemah perbaikan apa pun sesuai dengan spesifikasi di atas. Program Anda dapat menampilkan array tunggal atau nilai yang terkandung di dalamnya; dijamin bahwa tumpukan nilai hanya akan berisi nilai tunggal pada akhir eksekusi dan bahwa antrian operator akan kosong pada akhir eksekusi.

Ini adalah sehingga kode terpendek dalam byte menang.

Uji Kasus

Untuk kasus uji ini, duplikat adalah ", negatif adalah -, tambahan adalah +, perkalian adalah ×, dan kesetaraan =.

Input -> Output
1+2×3 -> 9
1"+"+ -> 4
2"××" -> 16
3"×+" -> 18
3"+×" -> 36
123"= -> 1 ("= always gives 1)
1+2=3 -> 1
1"=2+ -> 3
1-2-+ -> -3
-1-2+ -> 3 (hehe, the `-1` becomes `+1` at the `-` rather than making the `2` a `-1`)
+×"10 10 -> 200 (after the 10 is duplicated (duplication is delayed), 10 + 10 is performed and then 20 * 10, giving 200)

Aturan

  • Celah Standar Berlaku
  • Anda dapat mengambil juru bahasa resmi apa pun dan mengubahnya jika Anda mau. Harapkan untuk kehilangan mengerikan.

Input akan diberikan sebagai string dan output sebagai array, integer tunggal, keluar dari representasi string keduanya. Anda dapat berasumsi bahwa input hanya akan berisi spasi, digit, dan 5 karakter yang Anda pilih.

* sebenarnya tidak

HyperNeutrino
sumber
2
Pergi ke mana saja * ™.
Jonathan Allan
Apa hasil dari operator kesetaraan? 0dan 1?
Felix Palmen
1
@ Jonathan Allan lihat di atas; Saya menghapus perintah rip
HyperNeutrino
1
@RickHitchcock Tentu.
HyperNeutrino
1
Anda mungkin harus memasukkan ×+"10 10dalam kasus uji, atau contoh lain yang 1) menggunakan spasi dan 2) menunda penggunaan operator duplikat (dua hal yang saya lewatkan sepenuhnya).
Arnauld

Jawaban:

5

JavaScript (ES6), 204 203 200 byte

Mengembalikan bilangan bulat.

e=>e.replace(/\d+|\S/g,v=>{for((1/v?s:v>','?u:b)[U='unshift'](v);!!u[0]/s[0]?s[U](u.pop()>'c'?s[0]:-S()):!!b[0]/s[1]?s[U](+eval(S(o=b.pop())+(o<'$'?'==':o)+S())):0;);},s=[],u=[],b=[],S=_=>s.shift())|s

Karakter yang digunakan:

  • +: tambahan
  • *: perkalian
  • #: kesetaraan
  • d: duplikat
  • -: negatif

Uji kasus

Diformat dan dikomentari

e => e.replace(                     // given an expression e, for each value v matching
  /\d+|\S/g, v => {                 // a group of digits or any other non-whitespace char.
    for(                            //   this loop processes as many operators as possible
      (                             //   insert v at the beginning of the relevant stack:
        1 / v ? s : v > ',' ? u : b //     either value, unary operator or binary operator
      )[U = 'unshift'](v);          //     (s[], u[] or b[] respectively)
      !!u[0] / s[0] ?               //   if there's at least 1 value and 1 unary operator:
        s[U](                       //     unshift into s[]:
          u.pop() > 'c' ?           //       for the duplicate operator:
            s[0]                    //         a copy of the last value
          :                         //       else, for the negative operator:
            -S()                    //         the opposite of the last value
        ) :                         //     end of unshift()
      !!b[0] / s[1] ?               //   if there's at least 2 values and 1 binary operator:
        s[U](                       //     unshift into s[]:
          +eval(                    //       the result of the following expression:
            S(o = b.pop()) +        //         the last value, followed by the
            (o < '$' ? '==' : o) +  //         binary operator o with '#' replaced by '=='
            S()                     //         followed by the penultimate value
          )                         //       end of eval()
        ) : 0;                      //     end of unshift()
    );                              //   end of for()
  },                                // end of replace() callback
  s = [],                           // initialize the value stack s[]
  u = [],                           // initialize the unary operator stack u[]
  b = [],                           // initialize the binary operator stack b[]
  S = _ => s.shift()                // S = helper function to shift from s[]
) | s                               // return the final result
Arnauld
sumber
Jangan pikir ini berhasil -1+-2. Mengembalikan 3 bukannya -3.
Rick Hitchcock
1
@RickHitchcock Pemahaman saya adalah ke-2 -harus segera diterapkan -1.
Arnauld
Saya akan berpikir ke-2 -akan pergi 2karena datang setelah operator lain. Mungkin @HyperNeutrino dapat mengklarifikasi. Operator negatif mungkin ambigu dalam beberapa situasi.
Rick Hitchcock
3

JavaScript (ES6), 162 152 143 150 byte

(s,N=s.replace(/(-?\d+)-|-(-)/g,'- $1 ').match(/(- ?)*?\d+|R/g))=>+eval(`R=${N[0]>'9'?N[1]:N[0]},${s.match(/[+*=]/g).map((o,i)=>'R=R'+o+'='+N[i+1])}`)

Sedikit tidak berbulu:

(s,
 N=s.replace(/(-?\d+)-|-(-)/g,'- $1 ').      //change postfix negatives to prefix,
                                             //and change "--" to "- - "
     match(/(- ?)*?\d+|R/g)                  //grab numbers and duplicates
)=>+eval(`R=${N[0] > '9' ?  N[1] : N[0]},    //handle a delayed duplicate
          ${s.match(/[+*=]/g).               //grab the operators
              map((o,i)=>'R=R'+o+'='+N[i+1]) //create a comma-separated list of assignments
           }
         `)

Penjelasan

Saya menggunakan *untuk perkalian dan Rduplikat. Operator lain sama seperti dalam pertanyaan.

N menjadi array angka (termasuk duplikat).

The replacemenangani kasus di mana tanda negatif datang setelah nomor. Misalnya, itu akan berubah 1-ke - 1dan -1-ke - -1.

Di dalam eval, s.matchmenciptakan array dari operator biner. Perhatikan bahwa ini akan selalu memiliki satu elemen lebih sedikit daripada N.

Hasil dari fungsi adalah evalpemetaan angka dan operator.

Berikut ini apa yang harus dilakukan evaluntuk setiap kasus uji:

0+2*3        R=0,R=R+=2,R=R*=3        = 6 
1+2*3        R=1,R=R+=2,R=R*=3        = 9 
1R+R+        R=1,R=R+=R,R=R+=R        = 4 
2R**R        R=2,R=R*=R,R=R*=R        = 16 
3R*+R        R=3,R=R*=R,R=R+=R        = 18 
3R+*R        R=3,R=R+=R,R=R*=R        = 36 
123R=        R=123,R=R==R             = 1 
1+2=3        R=1,R=R+=2,R=R==3        = 1 
1R=2+        R=1,R=R==R,R=R+=2        = 3 
1-2-+        R=- 1,R=R+=- 2           = -3 
-1-2+        R=1,R=R+=2               = 3 
*+R10 10     R=10,R=R*=10,R=R+=10     = 110 
+*R10 10     R=10,R=R+=10,R=R*=10     = 200 
-1+--2       R=-1,R=R+=- -2           = 1 
-1+-2        R=-1,R=R+=-2             = -3 

Operator koma dalam ekspresi JavaScript mengembalikan hasil dari ekspresi terakhirnya, sehingga mapsecara otomatis mengembalikan ekspresi yang dapat digunakan.

The +tanda diperlukan sebelum evalberubah trueuntuk 1dan falseuntuk 0.

Penggunaan Rsebagai variabel dan operator duplikat sangat menyederhanakan mapsub-ekspresi.

Kasus uji:

Rick Hitchcock
sumber
2
Saya tidak berpikir replacepekerjaan seperti yang dimaksudkan. Ini mengembalikan 3untuk -1+--2dan saya pikir 1akan benar ( 1perubahan menandatangani tiga kali sebelum ada argumen kedua untuk yang +tersedia, menghasilkan -1 + 2).
Felix Palmen
Tangkapan hebat, @FelixPalmen. Sekarang sudah diperbaiki.
Rick Hitchcock
2

JavaScript, 321 311 byte

_="f=a=>(a.replace(/\\d+|./g,mq!~(b='+*=\"- '.indexOf(a))|b>2j3j4j5&&o+aw1/y?(y*=-1wcz:1/y?oywcz:hz,rql.map(z=>m(lki,1)[0],i)),hq1/s[1]?sk0,2,+eval(`y${a=='='?a+a:a}s[1]`)):cz,cqlki,0,a),s=[],l=[],e='splice'),s)z(a,i)ys[0]w)^r``:q=z=>os.unshift(k[e](j?b-";for(i of"jkoqwyz")with(_.split(i))_=join(pop());eval(_)

Cobalah online!

Kelima karakter itu sama seperti dalam pertanyaan, kecuali *untuk perkalian.
Script dikompres menggunakan RegPack . Script asli disimpan dalam variabel _setelah evaluasi.


sumber
Jangan pikir ini berhasil -1+-2. Mengembalikan 3 bukannya -3.
Rick Hitchcock
@RickHitchcock. Mengapa Anda percaya harus kembali -3bukan 3?
Saya mungkin salah paham operator negatif. Secara umum, -1 + -2apakah -3, tetapi harus diuraikan sebagai --1 + 2gantinya?
Rick Hitchcock
1
@RickHitchcock. Saya cukup yakin hasilnya 3. 2Bahkan sebelum datang di tumpukan, yang kedua -dievaluasi, dan oleh karena itu kita punya 1 2 +yang memang 3. Ah, dan mungkin Anda harus mengedit jawaban Anda juga.
Kamu mungkin benar. Anda dan Arnauld mendapatkan jawaban yang sama, dan saya telah meminta OP untuk klarifikasi. Akan memilih Anda lagi jika saya bisa.
Rick Hitchcock
1

Haskell , 251 byte

(#([],[]))
(x:r)#(o,n)|x>'9'=r#h(o++[x],n)|[(a,t)]<-lex$x:r=t#h(o,read a:n)
_#(o,n:_)=n
h=e.e
e(o:s,n:m:r)|o>'N'=e(s,g[o]n m:r)
e(o:s,n:r)|o=='D'=e(s,n:n:r)|o=='N'=e(s,-n:r)
e(o:s,n)|(p,m)<-e(s,n)=(o:p,m)
e t=t
g"a"=(+)
g"m"=(*)
g"q"=(((0^).abs).).(-)

Cobalah online! Gunakan karakter berikut: auntuk tambahan, muntuk perkalian, quntuk kesetaraan, Duntuk duplikat dan Nuntuk negasi. (Saya ingin menggunakan euntuk kesetaraan, tetapi mengalami masalah yang lexdiuraikan 2e3sebagai angka.) Contoh penggunaan:(#([],[])) "2a3 4m" hasil 20.

Laikoni
sumber
1

6502 kode mesin (C64), 697 byte

00 C0 A2 00 86 29 86 26 86 27 86 28 86 4B 86 4C 86 CC 20 E4 FF F0 FB C9 0D F0
10 C9 20 30 F3 A6 27 9D B7 C2 20 D2 FF E6 27 D0 E7 C6 CC A9 20 20 1C EA A9 0D
20 D2 FF 20 95 C0 20 09 C1 20 95 C0 A6 26 E4 27 F0 4E BD B7 C2 E6 26 C9 20 F0
E8 C9 2D D0 09 A6 4C A9 01 9D B7 C3 D0 32 C9 22 D0 09 A6 4C A9 02 9D B7 C3 D0
25 C9 2B D0 09 A6 4C A9 81 9D B7 C3 D0 18 C9 2A D0 09 A6 4C A9 82 9D B7 C3 D0
0B C9 3D D0 0D A6 4C A9 83 9D B7 C3 E6 28 E6 4C D0 A3 4C 8A C2 A6 29 F0 6F A4
28 F0 6B CA F0 4B C6 28 A6 4B E6 4B BD B7 C3 F0 F5 30 14 AA CA D0 0B 20 7B C2
20 E1 C1 20 4D C2 D0 D9 20 5C C2 D0 D4 29 0F AA CA D0 0B 20 6D C2 20 08 C2 20
4D C2 D0 C3 CA D0 0B 20 6D C2 20 16 C2 20 4D C2 D0 B5 20 6D C2 20 F4 C1 20 4D
C2 D0 AA A4 4B B9 B7 C3 F0 02 10 AC C8 C4 4C F0 0F B9 B7 C3 F0 F6 30 F4 AA A9
00 99 B7 C3 F0 A6 60 A0 00 A6 26 E4 27 F0 15 BD B7 C2 C9 30 30 0E C9 3A 10 0A
E6 26 99 37 C4 C8 C0 05 D0 E5 C0 00 F0 08 A9 00 99 37 C4 20 39 C2 60 A2 FF E8
BD 37 C4 D0 FA A0 06 88 CA 30 0A BD 37 C4 29 0F 99 37 C4 10 F2 A9 00 99 37 C4
88 10 F8 A9 00 8D 3D C4 8D 3E C4 A2 10 A0 7B 18 B9 BD C3 90 02 09 10 4A 99 BD
C3 C8 10 F2 6E 3E C4 6E 3D C4 CA D0 01 60 A0 04 B9 38 C4 C9 08 30 05 E9 03 99
38 C4 88 10 F1 30 D2 A2 06 A9 00 9D 36 C4 CA D0 FA A2 10 A0 04 B9 38 C4 C9 05
30 05 69 02 99 38 C4 88 10 F1 A0 04 0E 3D C4 2E 3E C4 B9 38 C4 2A C9 10 29 0F
99 38 C4 88 10 F2 CA D0 D6 C0 05 F0 06 C8 B9 37 C4 F0 F6 09 30 9D 37 C4 E8 C8
C0 06 F0 05 B9 37 C4 90 F0 A9 00 9D 37 C4 60 A9 FF 45 FC 85 9F A9 FF 45 FB 85
9E E6 9E D0 02 E6 9F 60 A2 00 86 9F A5 FB C5 FD D0 07 A5 FC C5 FE D0 01 E8 86
9E 60 A5 FB 18 65 FD 85 9E A5 FC 65 FE 85 9F 60 A9 00 85 9E 85 9F A2 10 46 FC
66 FB 90 0D A5 FD 18 65 9E 85 9E A5 FE 65 9F 85 9F 06 FD 26 FE CA 10 E6 60 20
33 C1 A6 29 AD 3D C4 9D 3F C4 AD 3E C4 9D 3F C5 E6 29 60 A6 29 A5 9E 9D 3F C4
A5 9F 9D 3F C5 E6 29 60 A6 29 BD 3E C4 9D 3F C4 BD 3E C5 9D 3F C5 E6 29 60 C6
29 A6 29 BD 3F C4 85 FD BD 3F C5 85 FE C6 29 A6 29 BD 3F C4 85 FB BD 3F C5 85
FC 60 A6 29 BD 3E C5 10 13 20 7B C2 20 E1 C1 20 4D C2 A9 2D 20 D2 FF A6 29 BD
3E C5 8D 3E C4 BD 3E C4 8D 3D C4 20 8B C1 A9 37 A0 C4 4C 1E AB

Demo online

Pemakaian sys49152 , lalu masukkan ekspresi perbaikan apa pun dan tekan kembali.

  • hampir tidak ada pengecekan kesalahan, jadi harapkan keluaran lucu pada ekspresi yang tidak valid.
  • simbol untuk multiplikasi adalah * , semua yang lain seperti yang disarankan.
  • panjang input maksimum adalah 256 karakter, tidak boleh ada lebih dari 127 operator yang antri.
  • Input rutin tidak menangani karakter kontrol, jadi jangan salah ketik;)
  • bilangan bulat ditandatangani 16bit, overflow akan diam-diam membungkus.
  • count byte agak besar karena CPU ini bahkan tidak tahu perkalian dan C64 OS / ROM tidak memberikan setiap aritmatika integer atau konversi ke / dari string desimal.

Inilah kode sumber assembler gaya ca65 yang dapat dibaca .

Felix Palmen
sumber
1

VB.NET (.NET 4.5) 615 576 byte

-39 byte terima kasih kepada Felix Palmen dengan mengubah \r\nke\n

Membutuhkan Imports System.Collections.Generic(termasuk dalam jumlah byte)

Dim s=New Stack(Of Long),q=New List(Of String),i=Nothing,t=0,c=0
Function A(n)
For Each c In n
If Long.TryParse(c,t)Then
i=i &"0"+t
Else
If c<>" "Then q.Add(c)
If i<>A Then s.Push(i)
i=A
End If
If i=A Then E
Next
If i<>A Then s.Push(i)
E
A=s
End Function
Sub E()
c=s.Count
If c=0Then Exit Sub
For Each op In q
If op="-"Or op="d"Or c>1Then
Select Case op
Case"*"
s.Push(s.Pop*s.Pop)
Case"+"
s.Push(s.Pop+s.Pop)
Case"="
s.Push(-(s.Pop=s.Pop))
Case"-"
s.Push(-s.Pop)
Case"d"
s.Push(s.Peek)
End Select
q.Remove(op)
E
Exit Sub
End If
Next
End Sub

Titik masuknya adalah Function A, yang mengambil string sebagai input dan mengembalikan aStack(Of Long) .

Simbol:

  • Tambahan - +
  • Perkalian - *
  • Kesetaraan - =
  • Negasi - -
  • Duplikasi - d

Gambaran:

Fungsi Amengambil input dan tokenizes itu. Ini menggunakan Long?untuk melakukan total berjalan untuk bilangan bulat multi-digit, yangNothing menandakan kita saat ini tidak membaca bilangan bulat.

Subroutine Emengambil tumpukan bilangan bulat dan antrian operator, dan mengevaluasi notasi perbaikan apa pun. Itu menyebut dirinya secara rekursif sampai tidak ada tindakan yang tersisa.

Saya mendeklarasikan params global sekaligus untuk menghemat byte pada deklarasi dan parameter yang lewat.

Nilai kembali dari Aditetapkan dengan menetapkan nilai ke variabel yang cocok A.

VB Truesetara dengan -1, sehingga operasi harus meniadakan hasil untuk mendapatkan nilai yang benar.

Cobalah online!

Brian J
sumber
sarankan untuk menambahkan Cobalah secara online!
Felix Palmen
btw, dengan Imports, saya mendapatkan hitungan byte saja 576- bisakah Anda salah menghitung ?
Felix Palmen
@FelixPalmen yang saya hitung \r\nalih - alih \n, jadi di situlah perbedaannya.
Brian J
@FelixPalmen Menambahkan TIO, terima kasih telah mengingatkan saya! :) (Oh, saya tidak sadar Anda sudah membuatnya untuk pos ini)
Brian J