Quizzino della domenica: parentesi

Immaginate di scrivere un’espressione composta da un certo numero di parentesi aperte e dello stesso numero di parentesi chiuse, e di voler verificare se l’espressione è “ben formata”, nel senso che non ci siano mai più parentesi chiuse che aperte, e quindi siano tutte accoppiabili come “aperta+chiusa”. Un’espressione come ()(()) è per esempio ben fatta; le parentesi in posizione 1 e 2 si possono eliminare come quelle in posizione 4 e 5, lasciando quelle in posizione 3 e 6 che a questo punto si possono eliminare. Un’espressione come ())(()() non lo è: possiamo eliminare le parentesi in posizione 1 e 2, in posizione 5 e 6, e in posizione 7 e 8 ma restano 3 e 4 che sono chiusa+aperta. La domanda è: è sempre possibile prendere un certo numero (eventualmente nessuna) di parentesi dal fondo di un’espressione e trasportarle all’inizio nello stesso ordine per avere un’espressione ben formata? In questo caso potrei spostare cinque parentesi e ottenere (()()()).

[ ((()())(())))))(((() ]
(trovate un aiutino sul mio sito, alla pagina http://xmau.com/quizzini/p542.html; la risposta verrà postata lì il prossimo mercoledì. Problema di James Tanton.)


5 comments

  1. Mi si permetta una battuta…
    Con tutte queste parentesi, è forse che hai deciso di imparare a programmare in LISP?

    • stavo per metterlo come battuta, ma poi ho pensato che anche tra i miei ventun lettori l’avrebbero capita in pochi.

  2. A questo proposito vorrei ricordare un mio collega, informatico e poeta, che scrisse molti anni fa questo breve componimento monovocalico: “visti i MIPS / riscrissi il CICS in Lisp”

  3. Il link alla pagina del quizzino porta al quizzino precedente.

    • ero convinto di averlo cambiato, tanto che i due prossimi che sono già pronti hanno la numerazione corretta… devo essermi dimenticato di salvarlo.