Mengurai bahasa 1D

Diberikan string yang hanya berisi 0's 1's, 2's dan kurung, output pohon tata bahasa string.

A 2membutuhkan 2 argumen - satu ke kiri dan satu ke kanan

A 1membutuhkan argumen tunggal - ke kiri atau kanan

A 0tidak memerlukan argumen apa pun dan merupakan kasus dasar

Sepasang tanda kurung dihitung sebagai satu argumen dan isi tanda kurung dievaluasi secara terpisah dari sisa string. Kurung bersarang dimungkinkan

String input akan selalu menjadi pohon lengkap tanpa karakter yang jatuh. String juga hanya akan memiliki satu solusi yang benar. Perhatikan bahwa fungsinya komutatif dan pengaturan argumen apa pun untuk2 akan dapat diterima. Anda tidak harus menangani input yang tidak sesuai dengan persyaratan ini.

Format tata bahasa output akan dalam bentuk function(arguments)secara rekursif

Uji kasus

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 (pra-rilis), 199

Disimpan 6 byte berkat 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

Penjelasan & versi tidak bercakap:

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