Evaluating Parentheses and Brackets as Integers

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.

• Asking on behalf of the Python submission for clarification: Program only, or are functions/return value okay? – Sp3000 Jun 6 '15 at 4:59
• 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. – Reto Koradi Jun 6 '15 at 5:38

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

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

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. • Funyy how lisp is used to do something with brackets here. – Syd Kerckhove Jun 6 '15 at 22:04 • @SydKerckhove You comment just make me think of an appropriate Clojure answer. Thanks alot! – coredump Jun 7 '15 at 5:24 Pyth, 3534 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.  • @Jakube Right, the unary summation has no effect. – isaacg Jun 5 '15 at 7:10 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))) )  • I should have read more closely - the Common Lisp solution takes exactly the same approach! – Toby Speight Jun 5 '15 at 13:49 • 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). – coredump Jun 7 '15 at 7:50 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. 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; } }  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.


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]

• 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. :) – Reto Koradi Jun 6 '15 at 4:33

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


Python, 117110 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."

• Functions now explicitly allowed :) – Calvin's Hobbies Jun 6 '15 at 5:57
• @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? – Reto Koradi Jun 6 '15 at 6:36
• @Retro I'd say yes, it is wrong. The function should work any number of times without reinterpreting it. – Calvin's Hobbies Jun 6 '15 at 7:21

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.

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