20
\$\begingroup\$

Write a program that takes in a string of the four characters ()[] that satisfies these points:

  • Every left parenthesis ( has a matching right parenthesis ).
  • Every left bracket [ has a matching right bracket ].
  • Matching pairs of parentheses and brackets won't overlap. e.g. [(]) is invalid because the matching brackets are not fully contained in the matching parentheses, nor vice-versa.
  • The first and last characters are a matching pair of parentheses or brackets. So ([]([])) and [[]([])] are valid but []([]) is not.

(A grammar for the input format is <input> ::= [<input>*] | (<input>*).)

Each pair of matching parentheses and brackets evaluates to a non-negative integer:

  • The values of pairs inside matching parentheses are all summed. The empty match () has value 0.
  • The values of pairs inside matching brackets are all multiplied. The empty match [] has value 1.

(The sum or product of one number is that same number.)

For example, ([](())([][])[()][([[][]][][])([][])]) can be broken down and evaluated as 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>

Another example:

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

Your program needs to evaluate and print the integer represented by the entire input string. You can assume the input is valid. The shortest code in bytes wins.

Instead of a program, you may write a function that takes in a string and prints or returns the integer.

\$\endgroup\$
  • \$\begingroup\$ Asking on behalf of the Python submission for clarification: Program only, or are functions/return value okay? \$\endgroup\$ – Sp3000 Jun 6 '15 at 4:59
  • \$\begingroup\$ Might be good to edit the question then. In a previous question, I was told that functions are not valid if it says "write a program" in the question. \$\endgroup\$ – Reto Koradi Jun 6 '15 at 5:38

12 Answers 12

11
\$\begingroup\$

CJam, 23

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

With BIG credits to Dennis! Try it online

Explanation:

The program converts the input to a CJam expression then evaluates it.
[…] becomes […1]:* (append 1 and multiply)
(…) becomes […0]:+ (append 0 and add)

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Transliteration saves 4 bytes: q"])(""1]:*0]:+["4/ers~ \$\endgroup\$ – Dennis Jun 5 '15 at 19:05
  • 2
    \$\begingroup\$ @Dennis whaaa! That's insane, you can do that?? \$\endgroup\$ – aditsu Jun 5 '15 at 20:13
  • 3
    \$\begingroup\$ You are asking me? :P \$\endgroup\$ – Dennis Jun 5 '15 at 20:31
  • 4
    \$\begingroup\$ @Dennis How would the creator of CJam know about such feature's existence?? \$\endgroup\$ – Optimizer Jun 5 '15 at 20:50
8
\$\begingroup\$

Common Lisp - 98

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

This requires cl-ppcre library to be loaded in current lisp image.

Explanation

Functions * and + are variadic and return their neutral value when given no arguments. For your examples, the evaluated lisp form are the following ones:

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

and

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

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

C'mon, Lisp - 16 bytes (experimental)

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

Other languages are so terse that I am tempted to make my own golfing language based on Common Lisp, for shorter string manipulations. Currently there is no spec, and the eval function is the following one:

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

Tests:

(cmon-lisp "+((<r*([<r)]<rRE" "([] [] ([] []))")
=> 4
  • there is an implicit argument called s and two stacks, p and q.
  • characters in source code are pushed to p.
  • < : pops from p and pushes to q.
  • r : replaces in s (must be a string) from characters in q to charactes in p; result is stored in s; p and q are emptied.
  • R : read from string s, store result in variable s.
  • E : eval form s, store result in s.
\$\endgroup\$
  • 1
    \$\begingroup\$ Funyy how lisp is used to do something with brackets here. \$\endgroup\$ – Syd Kerckhove Jun 6 '15 at 22:04
  • \$\begingroup\$ @SydKerckhove You comment just make me think of an appropriate Clojure answer. Thanks alot! \$\endgroup\$ – coredump Jun 7 '15 at 5:24
6
\$\begingroup\$

Pyth, 35 34 33 bytes

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

Demonstration.

1 byte thanks to @Jakube.

We start by parsing the input. The input format is close to Python, but not quite. We need commas after each parenthesized or bracketed group. The comma at the end of a bracketed group is unnecessary, but harmless. To accomplish this, we use this code:

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.

This will leave an extra , at the end of the string, which will wrap the whole object in a tuple, but this is harmless, because the tuple will be summed, and so have a value equal to its element.

Now that the string is parsed, we must find its value. This is done using a user defined function, y, which is called on the parsed object. the function is defined as follows:

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.
\$\endgroup\$
  • \$\begingroup\$ @Jakube Right, the unary summation has no effect. \$\endgroup\$ – isaacg Jun 5 '15 at 7:10
3
\$\begingroup\$

Emacs lisp, 94

The format looks very lispy, so I thought a simple transformation might work:

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

The intermediate format looks something like (for the example in the question):

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

We're helped by the fact that addition and multiplication already do what we want with an empty argument list.

Degolfed, and interactive, for you playing pleasure:

(defun paren_eval()
  (interactive "*")
  (format-replace-strings '(("(" . "(+")
                            ("[" . "(*")
                            ("]" . ")")))
  (eval (read (buffer-string)))
)
\$\endgroup\$
  • \$\begingroup\$ I should have read more closely - the Common Lisp solution takes exactly the same approach! \$\endgroup\$ – Toby Speight Jun 5 '15 at 13:49
  • 1
    \$\begingroup\$ We need more Emacs Lisp answers!. Btw, I did not count but you could golf it a little more by using a lambda, taking a string as a parameter and removing interactive (instead of buffer-string, use read-from-string). \$\endgroup\$ – coredump Jun 7 '15 at 7:50
2
\$\begingroup\$

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>

Gives output in unary.

Each line should go to its own file but you can run the code as one file with the -s flag. E.g.:

> retina -s brackets <input_1
111111111

Explanation comes later.

\$\endgroup\$
2
\$\begingroup\$

Java, 349 characters

A simple recursive approach. Expects the string to be the first argument used to call the 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;}}

Expanded:

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;
    }
}
\$\endgroup\$
2
\$\begingroup\$

Perl 5, 108

Done as an interpreter rather than rewrite-and-eval. Not a great showing, but fun to write anyway.

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]

Un-golfed:

# 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.
\$\endgroup\$
2
\$\begingroup\$

Python, 99

I tried a variety of methods but the shortest I could get was basically just a replacement and eval. I was pleasantly surprised to find that I could leave all the trailing ,s, as Python can parse [1,2,] and the final trailing comma just puts the whole thing in a tuple. The only other non-straightforward part would be the ord(c)%31%7 to seperate out the different characters (it evaluates to 2,3,1,0 for (,),[,] respectively)

F=lambda s:eval(''.join(["],1),","reduce(int.__mul__,[","sum([","]),"][ord(c)%31%7]for c in s))[0]
\$\endgroup\$
  • 1
    \$\begingroup\$ This does not work as a program, does it? The question asks for a program, so I don't think providing a function meets the requirements. At least that's what people told me last time I submitted a function when it said "program" in the question. :) \$\endgroup\$ – Reto Koradi Jun 6 '15 at 4:33
1
\$\begingroup\$

Java, 301

a bit of a different approach than TheNumberOne's answer, although mine is also recursive in nature. Input is taken from the command line. The void method saves a few bytes when removing the characters that are no longer needed.

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

expanded:

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));
    }
}
\$\endgroup\$
1
\$\begingroup\$

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

One aspect I was struggling with is that the function basically has two return values: the product/sum, and the new position in the string. But I need a function that returns only the result, so returning a tuple does not work. This version uses a "reference" argument (list with one element), to pass the position back from the function.

I have a shorter version (103 bytes) that uses a global variable for the position. But that will only work on the first call. And a function that only works once seems a bit fishy. Not sure if it would be acceptable for code golf.

The algorithm is straightforward recursion. I tried a number of variations for the expression that updates the product/sum. I came up with a few versions that were exactly the same length, but none of them shorter.

I sort of expected that the approach that turns this into an expression that gets evaluated would probably win. But as they say: "To iterate is human, to recurse divine."

\$\endgroup\$
  • \$\begingroup\$ Functions now explicitly allowed :) \$\endgroup\$ – Calvin's Hobbies Jun 6 '15 at 5:57
  • \$\begingroup\$ @Calvin'sHobbies Got a rules question that I was generally wondering about, but that might come into play here: If a solution is implemented as a function, does this imply that the function can be called more than once in a single run? For example, if it used a global variable that is only initialized correctly on the first call, would that be... wrong? \$\endgroup\$ – Reto Koradi Jun 6 '15 at 6:36
  • \$\begingroup\$ @Retro I'd say yes, it is wrong. The function should work any number of times without reinterpreting it. \$\endgroup\$ – Calvin's Hobbies Jun 6 '15 at 7:21
1
\$\begingroup\$

Clojure - 66 bytes

Notice that ([] (()) ([] []) [()] [([[] []] [] []) ([] [])]) is a valid Clojure form. So:

#(letfn[(g[x](apply(if(list? x)+ *)(map g x)))](g(read-string %)))
  • This is an anonymous function taking a string, reading it and giving to g.
  • The local g function apply + or * to the result of the invocation of g on sub-elements of its arguments.
  • The base case of the recursion is a little subtle: it is reached when x in an empty sequence; (map g x) returns nil, and apply returns the neutral value for the operation.
\$\endgroup\$
0
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.