Analyser une langue 1D

Étant donné une chaîne contenant uniquement des 0, des 1, des 2 et des crochets, affichez l'arborescence grammaticale de la chaîne.

A 2nécessite 2 arguments - un à gauche et un à droite

A 1requiert un seul argument - à gauche ou à droite

A 0ne nécessite aucun argument et est le cas de base

Une paire de crochets compte comme un argument et le contenu des crochets est évalué séparément du reste de la chaîne. Les crochets imbriqués sont possibles

Une chaîne d'entrée sera toujours une arborescence complète sans aucun caractère tombant. La chaîne n'aura également qu'une seule solution correcte. Notez que les fonctions sont commutatives et tout arrangement d'arguments pour 2sera acceptable. Vous n'aurez pas à gérer des entrées non conformes à ces exigences.

Le format de grammaire de sortie sera function(arguments)récursivement sous la forme

Cas de test

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 (pré-version), 199

6 octets enregistrés grâce à 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

Explication et version non golfée:

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