Разобрать 1D язык

Если задана строка, содержащая только 0, 1, 2 и скобки, выведите дерево грамматики строки.

А 2требует 2 аргумента - один слева и один справа

А 1требует один аргумент - влево или вправо

A 0не требует никаких аргументов и является базовым случаем

Пара скобок считается одним аргументом, а содержимое скобок вычисляется отдельно от остальной части строки. Возможны вложенные скобки

Входная строка всегда будет полным деревом без выпадающих символов. Строка также будет иметь только одно правильное решение. Обратите внимание, что функции являются коммутативными, и любое расположение аргументов для 2будет приемлемым. Вам не придется обрабатывать ввод, который не соответствует этим требованиям.

Формат выходной грамматики будет в форме function(arguments)рекурсивно

Контрольные примеры

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

Python 3.6 (предварительная версия), 199

Сохранено 6 байтов благодаря 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

Пояснение и версия без гольфа:

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