Java - Riconoscimento o meno di una stringa

Forum - Java - Riconoscimento o meno di una stringa

zabbixasd (Normal User)
Newbie

Messaggi: 1
Iscritto: 15/01/2013

Postato alle 17:12
Martedì, 15/01/2013

ciao vorrei un aiuto per capire come creare un programma in java che consiste nel riconoscere o meno una stringa.

la stringa è questa:

()[]{
{{}
{[]()
{{{[[[[[((())]]]]]}}}
[]{
[](((((((()))))))){{{{{}}}}}
{{{[[[[[((()))]]]]]}}}

in poche parole bisogna rispettare i criteri canonici dell' Algebra , infatti la cosa importante è che le quadre non contengano delle graffe , e che anche le parentesi tonde non contengono parentesi quadre o graffe.

ESEMPIO:
STRINGA RICONOSCIUTA {}(){}(){}[][][]()
STRINGA NON RICONOSCIUTA ()[

Siamo riusciti a implementare un metodo che controlli se le parentesi si aprono e si chiudono , ma non riusciamo a capire come fare per controllare se dentro le parentesi sono contenute parentesi che non potrebbero essere utilizzate.

Qualche idea ?

Grazie mille ,

Fabio

Il Totem (Admin)
Guru^2

Messaggi: 3635
Iscritto: 24/01/2006

Postato alle 10:27
Giovedì, 17/01/2013

Quello che cercate di riconoscere è una variante del linguaggio di Dyck, che è riconoscibile da automi a pila. In questo caso, se non ricordo male, basta un parser LL(1) per riconoscerlo. Nell'implementarlo, vi basta sapere qual è l'ultimo tipo di parentesi aperta, il che è molto semplice perché basta controllare la cima dello stack.
Una traccia in pseudo codice:

Codice sorgente - presumibilmente VB.NET

function parse()
   // peek() guarda il prossimo carattere in input senza leggerlo
   while (la = peek()) != EOS
      if (la == '(')
         parenteshis()
      elseif (la == '[')
         bracket()
      elseif (la == '{')
         curly()
      else
         error()
      end
   end
end
 
function parenteshis()
    // match consuma il carattere specificato dall'input e lancia un
    // errore nel caso il carattere di input non coincida con quello indicato
    match('(')
    push('(')
    parse()
    pop('(')
    match(')')
end 
 
function bracket()
   // stackTop restituisce il carattere in cima allo stack
   if (stackTop == '(')
      error()
   end
   match('[')
   push('[')
   parse()
   pop('[')
   match(']')
end
 
function curly()
   if (stackTop == '(') or (stackTop == '[')
      error()
   end
   match('{')
   push('{')
   parse()
   pop('{')
   match('}')
end