Evaluating Parentheses and Brackets as Integers

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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]

Answer 9

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

Answer 10

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

Answer 11

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.

Answer 12

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