# Parse a 1D language

Given a string containing only 0's 1's, 2's and brackets, output the grammar tree of the string.

A 2 requires 2 arguments - one to the left and one to the right

A 1 requires a single argument - to either the left or right

A 0 doesn't require any arguments and is the base case

A pair of brackets counts as one argument and the contents of the brackets are evaluated separately from the rest of the string. Nested brackets are possible

A input string will always be a complete tree with no characters falling off. The string will also only have a single correct solution. Note that the functions are commutative and any arrangement of arguments for 2 will be acceptable. You will not have to handle input that doesn't conform to these requirements.

The output grammar format will be in the form function(arguments) recursively

### Test cases

0 --> 0
01 --> 1(0)
020 --> 2(0,0)
101 --> 1(1(0))
0120 --> 2(1(0),0)
0120210 --> 2(1(0),2(0,1(0)))
01210 --> 2(1(0),1(0))
(020)210 --> 2(2(0,0),1(0))
((020)20)1 --> 1(2(0,2(0,0)))

• Is 10201 valid input? – Neil May 25 '16 at 15:19
• No, it could be 1(2(0,1(0))) or 2(1(0),1(0)) – Blue May 25 '16 at 15:20
• Actually I was thinking it was 1(2(1(0),0)) ;-) – Neil May 25 '16 at 15:34
• I still don't see why 0120210 can't also be parsed as 2[4](2[2](1[1](0[0]), 0[3]), 1[5](0[6])) where the bracketed numbers indicate position in the string. – feersum May 25 '16 at 21:23
• 101 is also ambiguous. – feersum May 25 '16 at 21:42

## Python 3.6 (pre-release), 199

Saved 6 bytes thanks to Morgan Thrapp

import re
def f(s):s=s.strip('()');i,j=[m.start()if m else-1for m in(re.search(c+'(?![^(]*\))',s)for c in'21')];return i>0and f'2({f(s[:i])},{f(s[i+1:])})'or j>=0and f'1({f(s[:j])or f(s[j+1:])})'or s


Explanation & ungolfed version:

import re

def f(s):
s=s.strip('()')
# Search for '2' and '1' outside of brackets
i, j = [m.start() if m else -1
for m in (re.search(c + '(?![^(]*\))', s) for c in '21')]

if i > 0:
# Call f(s[:i]) and f(s[i+1:]), concatenate the results
return f'2({f(s[:i])},{f(s[i+1:])})'
elif j>=0:
# Call f(s[:j]) and f(s[j+1:]), choose the non-empty result
return f'1({f(s[:j]) or f(s[j+1:])})'
else:
return s