Mengevaluasi Kurung dan Kurung sebagai Integer

20

Tulis sebuah program yang memuat empat karakter ()[]yang memenuhi poin-poin ini:

  • Setiap tanda kurung kiri (memiliki tanda kurung kanan yang cocok ).
  • Setiap braket kiri [memiliki braket kanan yang cocok ].
  • Pasangan kurung dan kurung yang cocok tidak akan tumpang tindih. mis. [(])tidak valid karena tanda kurung tidak sepenuhnya terkandung dalam tanda kurung yang cocok, atau sebaliknya.
  • Karakter pertama dan terakhir adalah pasangan kurung atau kurung yang cocok. Jadi ([]([]))dan [[]([])]valid tetapi []([])tidak.

( Tata bahasa untuk format input adalah <input> ::= [<input>*] | (<input>*).)

Setiap pasangan kurung dan kurung yang cocok dievaluasi menjadi bilangan bulat non-negatif:

  • Nilai pasangan di dalam tanda kurung yang cocok semuanya dijumlahkan . Pencocokan kosong ()memiliki nilai 0.
  • Nilai pasangan di dalam tanda kurung cocok dikalikan . Pencocokan kosong []memiliki nilai 1.

( Jumlah atau produk dari satu nomor adalah nomor yang sama.)

Misalnya, ([](())([][])[()][([[][]][][])([][])])dapat dipecah dan dievaluasi sebagai 9:

([](())([][])[()][([[][]][][])([][])])    <input>
(1 (0 )(1 1 )[0 ][([1 1 ]1 1 )(1 1 )])    <handle empty matches>
(1 0   2     0   [(1     1 1 )2     ])    <next level of matches>
(1 0   2     0   [3           2     ])    <and the next>
(1 0   2     0   6                   )    <and the next>
9                                         <final value to output>

Contoh lain:

[([][][][][])([][][])([][][])(((((([][]))))))]    <input>
[(1 1 1 1 1 )(1 1 1 )(1 1 1 )((((((1 1 ))))))]
[5           3       3       (((((2     )))))]
[5           3       3       ((((2       ))))]
[5           3       3       (((2         )))]
[5           3       3       ((2           ))]
[5           3       3       (2             )]
[5           3       3       2               ]
90                                                <output>

Program Anda perlu mengevaluasi dan mencetak bilangan bulat yang diwakili oleh seluruh string input. Anda dapat menganggap input tersebut valid. Kode terpendek dalam byte menang.

Alih-alih sebuah program, Anda dapat menulis fungsi yang mengambil string dan mencetak atau mengembalikan integer.

Hobi Calvin
sumber
Bertanya atas nama pengajuan Python untuk klarifikasi: Program saja, atau apakah fungsi / nilai pengembalian baik-baik saja?
Sp3000
Mungkin baik untuk mengedit pertanyaan itu. Dalam pertanyaan sebelumnya, saya diberitahu bahwa fungsi tidak valid jika dikatakan "menulis program" dalam pertanyaan.
Reto Koradi

Jawaban:

11

CJam, 23

q"])(""1]:*0]:+["4/ers~

Dengan kredit BESAR untuk Dennis! Cobalah online

Penjelasan:

Program mengonversi input ke ekspresi CJam kemudian mengevaluasinya.
[…]menjadi […1]:*(tambahkan 1 dan kalikan)
(…)menjadi […0]:+(tambahkan 0 dan tambahkan)

q              read input
"])("          characters we want to replace
"1]:*0]:+["    replacement strings, concatenated
4/             split into strings of length 4: ["1]:*" "0]:+" "["]
er             replace (transliterate) the 3 characters with the 3 strings
s              convert the result (mixed characters and strings) to string
~              evaluate
aditsu
sumber
1
Transliterasi menghemat 4 byte:q"])(""1]:*0]:+["4/ers~
Dennis
2
@Dennis whaaa! Itu gila, Anda bisa melakukan itu ??
aditsu
3
Anda bertanya kepada saya ? : P
Dennis
4
@ Dennis Bagaimana pencipta CJam tahu tentang keberadaan fitur seperti itu ??
Pengoptimal
8

Gangguan Umum - 98

(lambda(s)(eval(read-from-string(#1=ppcre:regex-replace-all"\\["(#1#"]"(#1#"\\("s"(+")")")"(*"))))
  1. Ganti (oleh(+
  2. Ganti [oleh(*
  3. Ganti ]oleh)
  4. Baca dari string
  5. Eval

Ini membutuhkan cl-ppcrepustaka untuk dimuat dalam gambar lisp saat ini.

Penjelasan

Berfungsi *dan +bersifat variadik dan mengembalikan nilai netralnya saat tidak ada argumen Untuk contoh Anda, bentuk lisp yang dievaluasi adalah yang berikut:

(+ (*) (+ (+)) (+ (*) (*)) (* (+)) (* (+ (* (*) (*)) (*) (*)) (+ (*) (*))))
=> 9

dan

(* (+ (*) (*) (*) (*) (*)) (+ (*) (*) (*)) (+ (*) (*) (*))
   (+ (+ (+ (+ (+ (+ (*) (*))))))))
=> 90

Tanpa regex - 183 byte

(lambda(s)(do(r(x(coerce s'list))c)((not x)(eval(read-from-string(coerce(reverse r)'string))))(setq c(pop x))(push(case c(#\[ (push #\* r)#\()(#\] #\))(#\( (push #\+ r) #\()(t c))r)))

Ayo, Lisp - 16 byte (percobaan)

+((<r*([<r)]<rRE

Bahasa-bahasa lain begitu singkat sehingga saya tergoda untuk membuat bahasa golf saya sendiri berdasarkan Common Lisp, untuk manipulasi string yang lebih pendek. Saat ini tidak ada spec, dan fungsi eval adalah yang berikut:

(defun cmon-lisp (expr &rest args)
  (apply
   (lambda (s)
     (let (p q)
       (loop for c across expr
             do (case c
                  (#\< (push (pop p) q))
                  (#\r
                   (let ((a1 (coerce q 'string)) (a2 (coerce p 'string)))
                     (setf p nil
                           q nil
                           s
                             (cl-ppcre:regex-replace-all
                              (cl-ppcre:quote-meta-chars a1) s a2))))
                  (#\R
                   (setf s
                           (if (string= s "")
                               nil
                               (read-from-string s))))
                  (#\E (setf s (eval s)))
                  (t (push c p))))
       s))
   args))

Tes:

(cmon-lisp "+((<r*([<r)]<rRE" "([] [] ([] []))")
=> 4
  • ada argumen implisit yang disebut sdan dua tumpukan, pdan q.
  • karakter dalam kode sumber didorong ke p.
  • <: muncul dari pdan mendorong ke q.
  • r: menggantikan s(harus berupa string) dari karakter qke karakter di p; hasilnya disimpan di s; pdan qdikosongkan.
  • R: baca dari string s, simpan hasil dalam variabel s.
  • E: bentuk eval s, hasil toko dalam s.
coredump
sumber
1
Funyy bagaimana cadel digunakan untuk melakukan sesuatu dengan tanda kurung di sini.
Syd Kerckhove
@SydKerckhove Anda berkomentar hanya membuat saya memikirkan jawaban Clojure yang tepat. Terima kasih banyak!
coredump
6

Pyth, 35 34 33 byte

L?*F+1yMbqb+YbsyMbyvsXzJ"])"+R\,J

Demonstrasi.

1 byte berkat @Jakube.

Kami mulai dengan mem-parsing input. Format input dekat dengan Python, tetapi tidak cukup. Kita perlu koma setelah setiap kelompok kurung atau kurung kurung. Koma di akhir grup kurung tidak perlu, tetapi tidak berbahaya. Untuk mencapai ini, kami menggunakan kode ini:

vsXzJ"])"+R\,J
  X               Translate
   z              in the input
     "])"         the characters "])"
    J             which we will save to J to
             J    J
         +R\,     with each character mapped to itself plus a ",".
 s                Combine the list to a string.
v                  Evaluate as a Python literal.

Ini akan meninggalkan ekstra ,di akhir string, yang akan membungkus seluruh objek dalam sebuah tuple, tetapi ini tidak berbahaya, karena tuple akan dijumlahkan, dan memiliki nilai yang sama dengan elemennya.

Sekarang string diuraikan, kita harus menemukan nilainya. Ini dilakukan dengan menggunakan fungsi yang ditentukan pengguna y,, yang dipanggil pada objek yang diuraikan. fungsi didefinisikan sebagai berikut:

L?*F+1yMbqb+YbsyMb
L                     Define a function, y(b), which returns the following:
 ?       qb+Yb        We form a ternary whose condition is whether the input, b,
                      equals the inputplus the empty list, Y. This is true if
                      and only if b is a list.
      yMb             If so, we start by mapping y over every element of b.
  *F+1                We then take the product of these values. The +1 ensures
                      that the empty list will return 1.
                yMb   Otherwise, we start by mapping y over every element of b.
               s      Then, we sum the results.
isaacg
sumber
@Jakube Benar, penjumlahan unary tidak berpengaruh.
isaacg
3

Emacs lisp, 94

Formatnya terlihat sangat lispy, jadi saya pikir transformasi sederhana mungkin berhasil:

(defun e()(format-replace-strings'(("("."(+")("["."(*")("]".")")))(eval(read(buffer-string))))

Format perantara terlihat seperti (misalnya dalam pertanyaan):

(+(*)(+(+))(+(*)(*))(*(+))(*(+(*(*)(*))(*)(*))(+(*)(*))))

Kami terbantu oleh fakta bahwa penambahan dan perkalian sudah melakukan apa yang kami inginkan dengan daftar argumen kosong.

Sederhana, dan interaktif, untuk Anda bermain kesenangan:

(defun paren_eval()
  (interactive "*")
  (format-replace-strings '(("(" . "(+")
                            ("[" . "(*")
                            ("]" . ")")))
  (eval (read (buffer-string)))
)
Toby Speight
sumber
Saya seharusnya membaca lebih dekat - solusi Common Lisp mengambil pendekatan yang persis sama!
Toby Speight
1
Kami membutuhkan lebih banyak jawaban Emacs Lisp !. Btw, saya tidak menghitung tetapi Anda bisa golf sedikit lebih dengan menggunakan lambda, mengambil string sebagai parameter dan menghapus interactive (bukan buffer-string, gunakan read-from-string).
coredump
2

Retina , 111 byte

[\([](1+x)[]\)]
$1
\[]
1x
\(\)
x
(\[a*)1(?=1*x1*x)
$1a
a(?=a*x(1*)x)
$1
(\[1*x)1*x
$1
)`(\(1*)x(?=1*x)
$1
[^1]
<empty line>

Memberikan output secara unary.

Setiap baris harus menuju ke file sendiri tetapi Anda dapat menjalankan kode sebagai satu file dengan -sbendera. Misalnya:

> retina -s brackets <input_1
111111111

Penjelasannya datang kemudian.

randomra
sumber
2

Java, 349 karakter

Pendekatan rekursif sederhana. Mengharapkan string menjadi argumen pertama yang digunakan untuk memanggil program.

import java.util.*;class K{int a=0,b;String c;public static void main(String[]a){K b=new K();b.c=a[0];System.out.print(b.a());}int a(){switch(c.charAt(a++)){case'(':b=0;for(int a:b())b+=a;break;case'[':b=1;for(int a:b())b*=a;}a++;return b;}List<Integer>b(){List d=new ArrayList();char c;while((c=this.c.charAt(a))!=']'&&c!=')')d.add(a());return d;}}

Diperluas:

import java.util.*;

class K {
    int a =0, b;
    String c;
    public static void main(String[] a){
        K b = new K();
        b.c = a[0];
        System.out.print(b.a());
    }
    int a(){
        switch (c.charAt(a++)){
            case '(':
                b =0;
                for (int a : b())
                    b += a;
                break;
            case '[':
                b =1;
                for (int a : b())
                    b *= a;
        }
        a++;
        return b;
    }
    List<Integer> b(){
        List d = new ArrayList();
        char c;
        while ((c= this.c.charAt(a)) != ']' && c != ')')
            d.add(a());
        return d;
    }
}
TheNumberOne
sumber
2

Perl 5, 108

Dilakukan sebagai penerjemah alih-alih menulis ulang dan mengevaluasi. Bukan pertunjukan yang bagus, tapi tetap menyenangkan untuk menulis.

push@s,/[[(]/?[(ord$_&1)x2]:do{($x,$y,$z,$t)=(@{pop@s},@{pop@s});
[$t?$x*$z:$x+$z,$t]}for<>=~/./g;say$s[0][0]

Tidak golf:

# For each character in the first line of stdin
for (<> =~ /./g) {
    if ($_ eq '[' or $_ eq '(') {
        # If it's an opening...
        # ord('[') = 91 is odd, ord('(') = 40 is even
        push @stack, [ ( ord($_) & 1) x 2 ];
        # so we will push [1, 1] on the stack for brackets and [0, 0] for parens.
        # one of these is used as the flag for which operator the context is, and
        # the other is used as the initial (identity) value.
    } else {
        # otherwise, assume it's a closing
        ($top_value, $top_oper) = @{ pop @stack };
        ($next_value, $next_oper) = @{ pop @stack };
        # merge the top value with the next-to-top value according to the
        # next-to-top operator. The top operator is no longer used.
        $new_value = $next_oper
            ? $top_value * $next_value
            : $top_value + $next_value
        push @stack, [ $new_value, $next_oper ];
    }
}

say $stack[0][0]; # print the value remaining on the stack.
hobbs
sumber
2

Python, 99

Saya mencoba berbagai metode tetapi yang terpendek yang bisa saya dapatkan pada dasarnya hanyalah penggantian dan evaluasi. Saya terkejut menemukan bahwa saya bisa meninggalkan semua trailing ,, karena Python dapat mengurai [1,2,]dan koma akhir terakhir hanya menempatkan semuanya dalam sebuah tuple. Bagian non-mudah hanya lain akan menjadi ord(c)%31%7untuk memisahkan keluar karakter yang berbeda (mengevaluasi untuk 2, 3, 1, 0untuk (, ), [, ]masing-masing)

F=lambda s:eval(''.join(["],1),","reduce(int.__mul__,[","sum([","]),"][ord(c)%31%7]for c in s))[0]
KSab
sumber
1
Ini tidak berfungsi sebagai program, bukan? Pertanyaannya meminta program, jadi saya tidak berpikir menyediakan fungsi memenuhi persyaratan. Setidaknya itulah yang dikatakan orang kepada saya terakhir kali saya mengirimkan sebuah fungsi ketika dikatakan "program" dalam pertanyaan. :)
Reto Koradi
1

Jawa, 301

sedikit pendekatan yang berbeda dari jawaban TheNumberOne, meskipun milik saya juga bersifat rekursif. Input diambil dari baris perintah. Metode void menyimpan beberapa byte saat menghapus karakter yang tidak lagi diperlukan.

enum E{I;String n;public static void main(String[]r){I.n=r[0];System.out.print(I.e());}int e(){int v=0;if(n.charAt(0)=='('){for(s("(");n.charAt(0)!=')';)v+=e();s(")");}else if(n.charAt(0)=='['){v=1;for(s("[");n.charAt(0)!=']';)v*=e();s("]");}return v;}void s(String c){n=n.substring(1+n.indexOf(c));}}

diperluas:

enum EvaluatingParenthesesAndBrackets{
    AsIntegers;
    String input;
    public static void main(String[]args){
        AsIntegers.input=args[0];
        System.out.print(AsIntegers.evaluate());
    }
    int evaluate(){
        int value=0;
        if(input.charAt(0)=='('){
            for(substringAfterChar("(");input.charAt(0)!=')';)
                value+=evaluate();
            substringAfterChar(")");
        }
        else if(input.charAt(0)=='['){
            value=1;
            for(substringAfterChar("[");input.charAt(0)!=']';)
                value*=evaluate();
            substringAfterChar("]");
        }
        return value;
    }
    void substringAfterChar(String character){
        input=input.substring(1+input.indexOf(character));
    }
}
Jack Ammo
sumber
1

Python, 117 110 109 byte

def C(s,p=[0]):
 m=r=s[p[0]]=='[';p[0]+=1
 while s[p[0]]in'[(':t=C(s,p);r=r*t*m+(r+t)*(1-m)
 p[0]+=1;return r

Satu aspek yang saya perjuangkan adalah bahwa fungsi tersebut pada dasarnya memiliki dua nilai balik: produk / jumlah, dan posisi baru dalam string. Tapi saya butuh fungsi yang hanya mengembalikan hasilnya, jadi mengembalikan tuple tidak berfungsi. Versi ini menggunakan argumen "referensi" (daftar dengan satu elemen), untuk meneruskan posisi kembali dari fungsi.

Saya memiliki versi yang lebih pendek (103 byte) yang menggunakan variabel global untuk posisi itu. Tapi itu hanya akan berfungsi pada panggilan pertama. Dan fungsi yang hanya berfungsi sekali tampak agak mencurigakan. Tidak yakin apakah itu dapat diterima untuk golf kode.

Algoritma ini adalah rekursi langsung. Saya mencoba sejumlah variasi untuk ekspresi yang memperbarui produk / jumlah. Saya datang dengan beberapa versi yang panjangnya persis sama, tetapi tidak ada yang lebih pendek.

Saya agak berharap bahwa pendekatan yang mengubah ini menjadi ekspresi yang dievaluasi mungkin akan menang. Tetapi seperti yang mereka katakan: "Untuk beralih adalah manusia, untuk berulang ilahi."

Reto Koradi
sumber
Fungsinya sekarang secara eksplisit diizinkan :)
Calvin Hobi
@ Calvin'sHobbies Punya pertanyaan tentang aturan yang biasanya saya tanyakan, tetapi mungkin akan muncul di sini: Jika sebuah solusi diimplementasikan sebagai suatu fungsi, apakah ini menyiratkan bahwa fungsi tersebut dapat dipanggil lebih dari sekali dalam sekali jalan? Misalnya, jika menggunakan variabel global yang hanya diinisialisasi dengan benar pada panggilan pertama, apakah itu ... salah?
Reto Koradi
@Retro Saya akan mengatakan ya, itu salah. Fungsi ini harus bekerja beberapa kali tanpa menafsirkannya kembali.
Hobi Calvin
1

Clojure - 66 byte

Perhatikan bahwa itu ([] (()) ([] []) [()] [([[] []] [] []) ([] [])])adalah bentuk Clojure yang valid. Begitu:

#(letfn[(g[x](apply(if(list? x)+ *)(map g x)))](g(read-string %)))
  • Ini adalah fungsi anonim yang mengambil string, membacanya dan memberi g.
  • Fungsi lokal gberlaku +atau* untuk hasil doag pada sub-elemen argumennya.
  • Kasing dasar rekursi agak halus: tercapai saat xdalam urutan kosong; (map g x)mengembalikan nil, dan applymengembalikan nilai netral untuk operasi.
coredump
sumber
0

JavaScript (ES6), 116 byte

s=>+[...s].reduce((t,c)=>((x=c==']')||c==')'?t[1].push(t.shift().reduce((a,b)=>x?a*b:a+b,+x)):t.unshift([]),t),[[]])
Ry-
sumber