13
\$\begingroup\$

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)))
\$\endgroup\$
  • \$\begingroup\$ Is 10201 valid input? \$\endgroup\$ – Neil May 25 '16 at 15:19
  • \$\begingroup\$ No, it could be 1(2(0,1(0))) or 2(1(0),1(0)) \$\endgroup\$ – Blue May 25 '16 at 15:20
  • \$\begingroup\$ Actually I was thinking it was 1(2(1(0),0)) ;-) \$\endgroup\$ – Neil May 25 '16 at 15:34
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – feersum May 25 '16 at 21:23
  • \$\begingroup\$ 101 is also ambiguous. \$\endgroup\$ – feersum May 25 '16 at 21:42
3
\$\begingroup\$

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
\$\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.