Escreva um programa que use uma sequência de quatro caracteres ()[]que satisfaça esses pontos:

• Todo parêntese esquerdo (tem um parêntese direito correspondente ).
• Cada colchete esquerdo [tem um colchete direito correspondente ].
• Pares correspondentes de parênteses e colchetes não se sobrepõem. por exemplo, [(])é inválido porque os colchetes correspondentes não estão totalmente contidos nos parênteses correspondentes, nem vice-versa.
• O primeiro e o último caracteres são um par correspondente entre parênteses ou colchetes. Então, ([]([]))e [[]([])]são válidos, mas []([])não são.

(Uma gramática para o formato de entrada é <input> ::= [<input>*] | (<input>*).)

Cada par de parênteses e colchetes correspondentes é avaliado como um número inteiro não negativo:

• Os valores dos pares entre parênteses são todos somados . A correspondência vazia ()tem valor 0.
• Os valores dos pares entre colchetes são todos multiplicados . A correspondência vazia []tem valor 1.

^{(A soma ou o produto de um número é o mesmo número.)}

Por exemplo, ([](())([][])[()][([[][]][][])([][])])pode ser dividido e avaliado como 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>

Outro exemplo:

[([][][][][])([][][])([][][])(((((([][]))))))]    <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>

Seu programa precisa avaliar e imprimir o número inteiro representado por toda a cadeia de entrada. Você pode assumir que a entrada é válida. O código mais curto em bytes vence.

Em vez de um programa, você pode escrever uma função que pega uma string e imprime ou retorna o número inteiro.

CJam, 23

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

Com grandes créditos para Dennis! Experimente online

Explicação:

O programa converte a entrada em uma expressão CJam e a avalia.
[…]torna-se […1]:*(acrescente 1 e multiplique)
(…) torna-se […0]:+(acrescente 0 e adicione)

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

Lisp comum - 98

(lambda(s)(eval(read-from-string(#1=ppcre:regex-replace-all"\\["(#1#"]"(#1#"\\("s"(+")")")"(*"))))

1. Substituir (por(+
2. Substituir [por(*
3. Substituir ]por)
4. Ler da sequência
5. Eval

Isso requer que a cl-ppcrebiblioteca seja carregada na imagem lisp atual.

Explicação

Funções *e +são variadas e retornam seu valor neutro quando não recebem argumentos. Para seus exemplos, o formulário lisp avaliado é o seguinte:

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

e

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

Sem regexes - 183 bytes

(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)))

Vamos lá, Lisp - 16 bytes (experimental)

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

Outras línguas são tão concisas que sou tentado a criar minha própria linguagem de golfe com base no Common Lisp, para manipulações mais curtas de cordas. Atualmente, não há especificações e a função eval é a seguinte:

(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))

Testes:

(cmon-lisp "+((<r*([<r)]<rRE" "([] [] ([] []))")
=> 4

• existe um argumento implícito chamado se duas pilhas, pe q.
• caracteres no código-fonte são enviados para p.
• <: sai de pe empurra para q.
• r: substitui in s(deve ser uma string) de caracteres qpara caracteres em p; resultado é armazenado em s; peq são esvaziados.
• R: lê da string s, armazena o resultado na variável s.
• E: forma de avaliação s, resultado da loja em s.

Pitão, 35 34 33 bytes

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

Demonstração.

1 byte graças a @Jakube.

Começamos analisando a entrada. O formato de entrada é próximo ao Python, mas não é bem assim. Precisamos de vírgulas após cada grupo entre parênteses ou entre colchetes. A vírgula no final de um grupo entre colchetes é desnecessária, mas inofensiva. Para fazer isso, usamos este código:

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.

Isso deixará um extra , no final da string, que envolverá o objeto inteiro em uma tupla, mas isso é inofensivo, porque a tupla será somada e, portanto, terá um valor igual ao seu elemento.

Agora que a string é analisada, devemos encontrar seu valor. Isso é feito usando uma função definida pelo usuário y, que é chamada no objeto analisado. a função é definida da seguinte maneira:

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.

Emacs lisp, 94

O formato parece muito lispy, então pensei que uma simples transformação poderia funcionar:

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

O formato intermediário é semelhante a (por exemplo, na pergunta):

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

Somos ajudados pelo fato de que adição e multiplicação já fazem o que queremos com uma lista de argumentos vazia.

Degolfado e interativo, para você se divertir:

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

Retina , 111 bytes

[\([](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>

Dá saída em unário.

Cada linha deve ir para seu próprio arquivo, mas você pode executar o código como um arquivo com o -ssinalizador. Por exemplo:

> retina -s brackets <input_1
111111111

A explicação vem depois.

Java, 349 caracteres

Uma abordagem recursiva simples. Espera que a string seja o primeiro argumento usado para chamar o programa.

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;}}

Expandido:

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;
    }
}

Perl 5, 108

Feito como intérprete, em vez de reescrever e avaliar. Não é uma ótima exibição, mas é divertido escrever de qualquer maneira.

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]

Sem golfe:

# 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.

Python, 99

Eu tentei uma variedade de métodos, mas o mais curto que consegui foi basicamente apenas uma substituição e avaliação. Fiquei agradavelmente surpreso ao descobrir que podia deixar todos os ,s finais , pois o Python pode analisar [1,2,]e a vírgula final final coloca a coisa toda em uma tupla. A única outra parte não simples seria a ord(c)%31%7de separar os diferentes personagens (que avalia a 2, 3, 1, 0para (, ), [, ]respectivamente)

F=lambda s:eval(''.join(["],1),","reduce(int.__mul__,[","sum([","]),"][ord(c)%31%7]for c in s))[0]

Java, 301

uma abordagem um pouco diferente da resposta de TheNumberOne, embora a minha também seja de natureza recursiva. A entrada é retirada da linha de comando. O método nulo salva alguns bytes ao remover os caracteres que não são mais necessários.

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));}}

expandido:

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));
    }
}

Python, 117 110 109 bytes

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

Um aspecto com o qual estava lutando é que a função basicamente tem dois valores de retorno: o produto / soma e a nova posição na string. Mas preciso de uma função que retorne apenas o resultado, portanto, retornar uma tupla não funciona. Esta versão usa um argumento de "referência" (lista com um elemento), para retornar a posição da função.

Eu tenho uma versão mais curta (103 bytes) que usa uma variável global para a posição. Mas isso só funcionará na primeira chamada. E uma função que só funciona uma vez parece um pouco suspeita. Não tenho certeza se seria aceitável para o código de golfe.

O algoritmo é uma recursão direta. Eu tentei várias variações para a expressão que atualiza o produto / soma. Eu vim com algumas versões que tinham exatamente o mesmo comprimento, mas nenhuma delas mais curta.

Eu meio que esperava que a abordagem que transforma isso em uma expressão avaliada provavelmente vencesse. Mas, como eles dizem: "Repetir é humano, recompensar divino".

Clojure - 66 bytes

Observe que ([] (()) ([] []) [()] [([[] []] [] []) ([] [])])é um formulário válido do Clojure. Tão:

#(letfn[(g[x](apply(if(list? x)+ *)(map g x)))](g(read-string %)))

• Esta é uma função anônima que pega uma string, lê e dá para g .
• A gfunção local aplica-se +ou *ao resultado da invocação de gsubelementos de seus argumentos.
• O caso base da recursão é um pouco sutil: é alcançado quando xem uma sequência vazia; (map g x)retorna nile applyretorna o valor neutro para a operação.

JavaScript (ES6), 116 bytes

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),[[]])