[JAVA] Risolvere funzione checkString

[Taylor83]

Salve, a tutti sto uscendo pazzo per la risoluzione di un esercizio...ve lo illustro:
Scrivere la funzione: public static boolean checkString(String s).
Istruzioni per lo svolgimento:
• La funzione prende in input una stringa s e restituisce true se e solo se s è ben formata. Una stringa è ben formata se è costituita da sequenze di 0 o più caratteri (diversi dalle parentesi angolari ‘<’ e ‘>’) racchiusi tra coppie di parentesi angolari. Le sequenze possono essere annidate all’interno di altre sequenze e i caratteri di una stessa sequenza devono essere tutti uguali. Ad esempio la stringa “<aaa<bbb>a<ddd> a><ee>” è ben formata in quanto contiene le quattro sequenze <aaaaa>, <bbb>, <ddd>,<ee>. La stringa “<aaa<bbbb>c<dd>a>” non è ben formata perché contiene le sequenze <aaaca>, <bbbb> e <dd>, la prima delle quali non è formata da caratteri identici. Anche la stringa “<aaa>><ff>a<bbb>a>” non è ben formata perché c’è una parentesi angolare ‘>’ a cui non corrisponde alcuna parentesi angolare ‘<’.
• La stringa vuota e la stringa “< >” sono ben formate.

Ho fatto solamente il check per vedere se la stringa è ben parentesizzata, ma il resto non so come farlo.
Di seguito la mia parte di codice:

public static boolean checkString(String s){
		
	DinamicArrayStack <String> stack = new DinamicArrayStack <String>();
		for (int i=0; i<s.length(); i++){
			String curr = "" + s.charAt(i);
                        String = o; 
			if(curr.equals("<"))
				stack.push(curr);
			if(curr.equals(">")){
				try { 
					o = stack.pop();
				}
				catch(EmptyStackException e){
					return false;
				}
			}
		}
		if(stack.isEmpty())
			return true;
		else 
			return false;
	}

Vi prego aiutatemi...Grazie mille!!!

[WarDuck]

Che corso state seguendo?

Avete fatto automi e grammatiche?

Dovrebbe essere una grammatica context free di questo tipo (non assicuro la correttezza ):

S -> <C>
C -> A..Z | e | S
A -> aA | e | SA
..
Z -> zZ | e | SZ

S start symbol
"e" è l'empty string.

Ad esempio per fare <aa<bb>a>

S
<C>
<A>
<aaA>
<aaSA>
<aa<C>A>
<aa<B>a>
<aa<bb>a>

Da come hai implementato il codice sembra un push down automaton, dagli un'occhiata:

http://en.wikipedia.org/wiki/Pushdown_automaton

[Taylor83]

Questo è il corso di Laboratorio di Algoritmi e Strutture Dati...
Il programma verte sull'implementazione di strutture dati (Stack, Queue, Deque, ArrayList, NodeList, Sequence, Iterator, Tree, BinaryTree, PriorityQueue, Heap, Adaptable Priority Queue, Dizionari, Tabelle Hash, Map, Binary Search Tree, Set, Partition e infine Grafi) in Java...
Quindi l'esercizio deve essere sviluppato utilizzando uno dei TDA sopra citati...

Come puoi vedere nel codice, ho utilizzato uno stack per verificare se le "< >" sono aperte e chiuse correttamente... questo funziona perfettamente, passando in input, nel main, una stringa tipo <<aa><ddss>ss<s>>...return true
Se inserisco, per esempio <sa>a<ds<ds><s> return false.

Adesso dovrei fare sta benedetta verifica dei caratteri all'interno di ogni gruppo di "< >"...come cavolo si fa?

Grazie mille!!!

[WarDuck]

Forse ti basta usare un altro stack per conservarti il carattere corrente.

Ora provo e ti dico.

[Taylor83]

Grazie mille d'avvero WarDuck!!!

[WarDuck]

Ok allora l'idea è questa:

- contare le parentesi: va bene come hai fatto te (ed è quello che si fa di solito), per questo ho usato stack_p.

- assicurarti che le lettere siano uguali all'interno di esse (uso un altro stack, stack_c)

Ti serve un altro stack in grado di ricordarti quale lettera stavi controllando prima di incontrare un'altra parentesi aperta.

In sostanza:

• quando vedi una parentesi aperta imposta aperture = true
• quando vedi una lettera:
  • se aperture è true aggiungila allo stack e metti aperture = false
  • altrimenti controlla se il top dello stack è uguale
• quando vedi una parentesi chiusa devi poppare da tutti e due gli stack

Il codice probabilmente è un po' incasinato, spero che più che altro ti sia chiara l'idea, l'implementazione è una conseguenza:

public static boolean checkString(String input) {
		LinkedList<Character> stack_p = new LinkedList<Character>();
		LinkedList<Character> stack_c = new LinkedList<Character>();
		
		boolean aperture = false;
		
		for (int i=0; i<input.length(); i++) {
			char ch = input.charAt(i);
			
			if (ch=='<') {
				aperture = true;
				stack_p.push(ch);
			}
			else
			if (ch=='>') {
				if (!stack_c.isEmpty())
					stack_c.pop();
				
				try {
					stack_p.pop();
				}
				catch (NoSuchElementException ex) {
					return false;
				}
			}
			else {
				if (aperture) {
					stack_c.push(ch);
					aperture = false;
				}
				else {
					char check = stack_c.pop();
					if (check != ch) return false;
					else stack_c.push(ch);
				}
			}			
		}
		
		if (stack_p.isEmpty() && stack_c.isEmpty())
			return true;
		else
			return false;
	}

Edit: ora vedo se si può usare uno stack solo (in teoria dovrebbe essere possibile)

[Taylor83]

Sei grande...funziona...non so che dirti grazie mille davvero!!!
Sei stato gentilissimo!!!

[WarDuck]

Originariamente inviato da Taylor83

Sei grande...funziona...non so che dirti grazie mille d'avvero!!!
Sei stato gentilissimo!!!

Guarda ti posso dire che si può fare anche con 1 stack solo .

Dai provaci te poi vediamo cosa hai pensato (io l'ho fatto) .

[Taylor83]

Originariamente inviato da WarDuck

Guarda ti posso dire che si può fare anche con 1 stack solo .

Dai provaci te poi vediamo cosa hai pensato (io l'ho fatto) .

Ok dopo ci provo e ancora grazie mille!!!