Analizza parentesi nidificate

Question

Obbiettivo

Mimic Haskell's reads :: ReadS ().

In altre parole, analizza le parentesi nidificate. Poiché il tipo di destinazione è ()(il tipo con un possibile valore), "analisi" significa scartare una parentesi nidificata iniziale.

Input valido

"Nidificate tra parentesi" mezzi (), (()), ((())), e così via. Ovvero, iniziali di (s diversi da zero e finali di )s dello stesso numero.

Ma c'è una svolta. Il parser deve sgranocchiare anche spazi bianchi iniziali o intercalati. Quindi, ad esempio, le seguenti stringhe sono valide per essere sgranocchiate:

• ( )
• ()
• ( () )

Nota che gli spazi vuoti finali non devono essere sgranocchiati.

Spazi bianchi

I seguenti caratteri ASCII sono sempre considerati uno spazio bianco:

• \tU + 0009; Tab orizzontale
• \nU + 000A; Line Feed
• \vU + 000B; Tab verticale
• \fU + 000C; Avanzamento modulo
• \rU + 000D; Ritorno in carrozza
• U + 0020; Spazio

Per ciascuno dei seguenti caratteri Unicode, è definito dall'implementazione considerarlo uno spazio bianco:

• U + 0085; Riga successiva
• U + 00A0; Spazio senza interruzioni
• U + 1680; Ogham Space Mark
• U + 2000; En Quad
• U + 2001; Em Quad
• U + 2002; En Space
• U + 2003; Em Space
• U + 2004; Spazio tre per em
• U + 2005; Spazio quattro per em
• U + 2006; Spazio sei per em
• U + 2007; Figura spazio
• U + 2008; Spazio di punteggiatura
• U + 2009; Spazio sottile
• U + 200A; Spazio per capelli
• U + 2028; Separatore di linea
• U + 2029; Separatore di paragrafo
• U + 202F; Spazio ristretto senza interruzioni
• U + 205F; Spazio matematico medio
• U + 3000; Spazio ideografico

Tutti gli altri caratteri non sono mai considerati spazi bianchi.

Errore

Se la stringa non inizia con parentesi nidificate, il parser cadrà in uno stato errato. I modi che indicano un errore includono:

• Fallimento monadico
• Restituzione di un valore errato
• Alzare / Lanciare un errore

Produzione

Quando il parser ha sgranocchiato con successo una parentesi annidata, il parser emetterà la parte non masticata della stringa.

Esempi

Valido esempio

• Quando viene fornito (), l'output è una stringa vuota.
• Quando viene fornito ( ) Hello, l'output è Hello. Notare lo spazio bianco iniziale dell'output.
• quando fornito ((())))), l'output è )).

Esempio errato

• Stringa vuota
• ((()
• (()())
• (H)
• Hello, world!

Soluzione ungolfed

C

Restituisce un puntatore nullo per un errore.

#include <stdbool.h>
#include <stdlib.h>

char *readMaybeUnit(char *str) {
    bool p = false;
    unsigned c = 0;
    while (*str != '\0') {
        switch (*str) {
        case '(':
            p = true;
            ++c;
            // FALLTHRU
        case '\t': case '\n': case '\v': case '\f': case '\r': case ' ':
            break;
        default:
            goto parseRightParentheses;
        }
        ++str;
    }
    parseRightParentheses: while (*str != '\0') {
        switch (*str) {
        case ')':
            if (1 >= c) {
                if (1 == c)
                    ++str;
                c = 0;
                goto returnReadMaybeUnit;
            }
            --c;
            // FALLTHRU
        case '\t': case '\n': case '\v': case '\f': case '\r': case ' ':
            break;
        default:
            goto returnReadMaybeUnit;
        }
        ++str;
    }
    returnReadMaybeUnit: return p && 0 == c ? str : NULL;
}

Answer 1

Retina 0.8.2 , 32 31 byte

^(\s*\()+(?<-1>\s*\))+(?(1)$.)

Provalo online! Il collegamento include casi di test. Restituisce la stringa originale in caso di errore. Considera i caratteri di controllo forniti come spazi bianchi, più eventuali caratteri Unicode (come lo spazio) nel gruppo Separator, più U + 0085. Se si desidera solo lo spazio bianco minimo, è possibile ottenere il prefisso e`. Spiegazione:

^(\s*\()+

Trova alcune parentesi aperte all'inizio della stringa.

(?<-1>\s*\))+

Abbina alcune parentesi strette.

(?(1)$.)

Verificare che lo stesso numero di parentesi aperte e chiuse corrispondesse.

Elimina le parentesi corrispondenti.

Soluzione alternativa, anche 31 byte:

r`^(?<-1>\s*\()+(\s*\))+(.*)
$2

Provalo online! Il collegamento include casi di test. Se si desidera solo lo spazio bianco minimo, è possibile ottenere il prefisso e. Spiegazione:

r`

Inizia ad abbinare alla fine della stringa e lavora all'indietro (come farebbe uno sguardo dietro).

(.*)

Abbina il maggior numero di risultati possibile.

(\s*\))+

Abbina alcune parentesi strette.

^(?<-1>\s*\()+

Trova la corrispondenza delle parentesi aperte all'inizio della stringa. Il numero di parentesi chiuse deve essere almeno pari al numero di parentesi aperte affinché il gruppo di bilanciamento abbia esito positivo, ma non può essere maggiore perché (.*)garantisce che il minor numero possibile di parentesi chiuse corrisponda.

$2

Conserva tutto tranne le parentesi abbinate.

Precedente soluzione a 32 byte che restituisce la stringa vuota in caso di errore:

1!`(?<=^(?<-1>\s*\()+(\s*\))+).*

Provalo online! Il collegamento include casi di test. Se si desidera solo lo spazio bianco minimo, è possibile ottenere il prefisso e. Spiegazione:

1!`

Emette la parte corrispondente della prima corrispondenza.

(?<=^(?<-1>\s*\()+(\s*\))+)

Assicurati che la partita inizi dopo parentesi equilibrate. Nota che questo è un lookbehind, quindi la corrispondenza viene elaborata da destra a sinistra: le )s vengono abbinate per prime, quindi a (può essere abbinata ciascuna ). Non possono esserci troppe )s perché il lookbehind sarebbe stato identificato prima, il che significa che questa non è più la prima corrispondenza.

.*

Abbina il resto della stringa. Questo conta effettivamente come parte della corrispondenza e quindi diventa l'output risultante.

Answer 2

Haskell , 83 76 byte

c?(a:b)|elem a" \t\n\r\v\r"=c?b|a==c=[b]
_?_=[]
f x='('?x>>=(:)<*>f>>=(')'?)

Provalo online!

Poiché questa domanda per imitare l'analisi di Haskell, ho pensato che sarebbe stato bello provare utilizzando l'analisi monadica in Haskell. Il risultato in realtà è davvero breve. Uso []come monade perché è molto più breve di Maybeo Either.

---

Cos'è l'analisi monadica?

In parole povere l'analisi monadica è un tipo di analisi in cui un parserèuna funzione da una stringa a un tipo opzionale di una stringa rimanente e alcuni dati

type Parser a = String -> Option (a, String)

Qui il nostro Optiontipo è un elenco e stiamo solo convalidando piuttosto che produrre dati, quindi il nostro parser ha il seguente aspetto:

type Parser a = String -> [ String ]

Dove il nostro parser prende una stringa e restituisce tutti i possibili suffissi di analisi valide. La stringa vuota rappresenta un errore di analisi perché nessun suffisso significa che non è stata trovata alcuna analisi valida.

Questo modo di strutturare le cose rende semplicissimo combinare i parser. Ad esempio, se abbiamo un parser pche analizza la regex \s*(e un parser qche analizza la regex, \s*)allora possiamo creare un parser che analizza l'espressione \s*(\s*)usando la freccia Kleisli

(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)

Significa che il risultato è p >=> q. Possiamo anche fare altri combinatori.

---

Quindi ecco come lo uso nella mia risposta.

La prima cosa che facciamo è implementare ?, che prende un carattere crestituisce un parser la regex \s*c(dove cè il carattere). Essenzialmente questo consuma un prefisso composto da qualsiasi quantità di spazio bianco seguito da un singolo carattere. Questo è sempre (e solo richiesto e ).

Con questo implementiamo fqual è il parser richiesto dalla sfida. In realtà non abbiamo la freccia di Kleisli in Prelude, ma la scriverò come se lo avessimo fatto per chiarezza e poi mostrerò come rimuovere le frecce di Kleisli.

f = ('('?) >=> (:)<*>f >=> (')'?)

Quindi abbiamo prima tre parser, deve iniziare con uno spazio bianco seguito da un (poi un parser gobbledygook e poi deve finire con uno spazio bianco seguito da a ).

Il gobbledygook (:)<*>fpuò essere espresso più chiaramente come

\ x -> x : f x

Vale a dire che corrisponde a tutto ciò che fa il fparser, ma corrisponde anche alla stringa vuota.

Quindi il nostro fparser corrisponde a:

Parentesi che racchiudono, la stringa vuota o un'altra f.

Ora per rimuovere le nostre frecce Kleisli usiamo >>=che ha la firma di tipo simile:

(>>=) :: m a -> (a -> m b) -> m b

Quindi prendiamo un argomento da f, lo passiamo al primo parser e cambiamo tutti i nostri (>=>)s in (>>=)s.

Answer 3

Python 2, 143 124 byte

Alcuni tentativi senza usare espressioni regolari (probabilmente possono essere molto più brevi con idee migliori). Ho testato solo alcuni esempi, quindi potrebbero esserci bug da qualche parte.

def f(s,c=0,p='('):a=s[:1];return[f(s[1:],c+"()".find(a)%-3+1,[p,')'][a>p])if(a in(p,')'))|a.isspace()else 0,s][`c`+p=="0)"]

Restituisce 0in caso di errore.

Provalo online!

Python 3, 127 byte

def f(s,c=0,p='('):a=s[:1];return[f(s[1:],c+"()".find(a)%-3+1,[p,')'][a>p])if(a in(p,')'))|a.isspace()else 0,s][(c,p)==(0,')')]

Restituisce 0in caso di errore.

Provalo online!

---

Pitone 2 (non ricorsivo), 173 170 166 153 byte

def p(s):c=i=a=0;t="""
while i<len(s):
 if~-s[i].isspace():
	if%r!=s[i]:break
	c+=%s
 i+=1""";exec t%('(','1')+t%(')',"-1\n\tif c==0:a=s[i+1:]");return a

Restituisce 0in caso di errore.

Provalo online!

Potremmo salvare altri 2 byte se restituissimo la stringa originale in caso di errore, ma poi immettiamo '()'e ''diamo lo stesso output ''.

• -4 byte, grazie a @ovs!

Answer 4

Perl 5 , (-p) 22 byte

s/^(\s*\((?1)?\s*\))//

Provalo online!

Utilizzo di regex ricorsivo. Il più corto \s*\((?0)?\s*\)non ha funzionato perché mancava l'ancora di partenza.

Il caso di errore è dato dal risultato dell'operazione di sostituzione:

• 1 - successo
• "" - fallito