Analizuj język 1D

Biorąc pod uwagę ciąg zawierający tylko 0, 1, 2 i nawiasy, wyprowadzaj drzewo gramatyki łańcucha.

2Wymaga 2 argumenty - jeden po lewej i jeden w prawo

1Wymaga jednego argumentu - do lewej lub prawej

A 0nie wymaga żadnych argumentów i jest podstawowym przypadkiem

Para nawiasów liczy się jako jeden argument, a zawartość nawiasów jest oceniana oddzielnie od reszty ciągu. Możliwe są zagnieżdżone nawiasy

Ciąg wejściowy zawsze będzie kompletnym drzewem bez spadających znaków. Ciąg będzie miał tylko jedno poprawne rozwiązanie. Zauważ, że funkcje są przemienne i każde ustawienie argumentów dla 2jest dopuszczalne. Nie będziesz musiał obsługiwać danych wejściowych, które nie spełniają tych wymagań.

Wyjściowy format gramatyki będzie miał postać function(arguments)rekurencyjną

Przypadki testowe

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 (wersja wstępna), 199

Zaoszczędź 6 bajtów dzięki 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

Wyjaśnienie i wersja bez golfa:

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