[JAVA] Utilizzo di Stack e gestione errore overflow

[xplorer87]

ciao ragazzi, mi sto cimentando con un pochettino di java e dopo un po' di mesi di inattivita' ho riaperto il buon eclipse... ma veniamo al dunque: sto scrivendo un programmino da runnare da console che opera su uno stack di oggetti, i quali ho definito io in un'apposita classe tramite una coppia (stringa, intero). ho quindi scritto una classe con un metodo che prende in ingresso una stringa in input, che ricorsivamente pusha/poppa elementi nello stack.

il codice di per se e' corretto, sia sintatticamente che semanticamente (ho verificato con successo per svariati input fino a una decina di caratteri), ma ottengo uno java.lang.StackOverflowError per input di dimensioni superiori, "come se" la jvm non ce la facesse ad eseguire tutta quella mole di calcoli (maledetta ricorsione!). c'e' un modo per ovviare a cio', magari runnando il mio codice "stand alone" (ma in java si puo'?), anziche' da dentro eclipse o facendo qualche altra cosa? ciao e grazie ^^

[LeleFT]

Ci sono alcune cose da dire:

1) Il fatto che il tuo codice sia corretto semanticamente è tutto da vedere e visto che non abbiamo a disposizione il codice incriminato non lo possiamo dire. Quindi, come minimo, dovresti postare un po' di codice.

2) Java è nato molto prima di Eclipse, quindi tutti i programmi si possono avviare senza avere Eclipse installato (sarebbe gravissimo il contrario, come si farebbe a distribuire un proprio programma?). A tal proposito, è sufficiente andare al prompt, posizionarsi nella directory giusta (questo dipende dalla clausola package) e avviare il comando java nomeclasse (o java nomepackage.nomeclasse a seconda appunto della clausola package usata).

3) Una eccezione di quel tipo mi fa pensare ad una ricorsione molto pesante. Il fatto che il problema si proponga con stringhe di soli 11 caratteri mi autorizza a pensare che forse la ricorsione si può migliorare.


Ciao.

[xplorer87]

ciao lele, grazie per la risposta. dunque, per standalone intendevo un modo per creare un eseguibile doppiocliccabile (un po' come il build and run di alcune IDE per C++). comunque anche provando da prompt come da te detto, in effetti le cose non cambiano. sul codice, in effetti hai ragione, non l'avevo fatto perche' e' un bello denso, ma se ci sara' qualcuno volenteroso di darmi una mano, ogni aiuto sara' bene accetto. premetto che tutto gira magnificamente se la mia stringToCheck e' di 11 caratteri o meno, se e' piu' lunga, ottengo lo stackoverflow.

e comunque, *sicuramente* la ricorsione e' pesantissima e migliorabile, pero' ho notato con alcune prove, che per particolari input in cui devo solo aggiungere elementi allo stack senza toglierne, posso ottenere un funzionamento corretto anche per input molto piu' lunghi (100 e piu' caratteri). dovro' proprio cambiare algoritmo?

public boolean check(int scanIndex)
	{
		productionSet = givenGrammar.getProductionSet();
		startSymbol = givenGrammar.getStartSymbol();
		
		if(sententialFormStack.isEmpty())
		{
			
			for (i = scanIndex; i < productionSet.size(); i++)
			{
				currentLeftSide = productionSet.elementAt(i).getLeftSide();
				currentRightSide = productionSet.elementAt(i).getRightSide();				
				
				if (currentLeftSide.equals(startSymbol) && currentRightSide.length() <= stringToCheck.length())
				{
					if(currentLeftSide.equals(stringToCheck))
					{
						return true;
					}
				
					sententialFormStack.push(new Ancestor(startSymbol, i));
					return check(0);
				}
			}
	
			return false;
		}
 
			
		else
		{
			currentSententialForm = sententialFormStack.peek().getSententialForm();
			currentScanIndex = sententialFormStack.peek().getProductionIndexUsedToUnfold();
			
			
			for(i = scanIndex; i < productionSet.size(); i++)
			{
				currentLeftSide = productionSet.elementAt(i).getLeftSide();
				currentRightSide = productionSet.elementAt(i).getRightSide();
				
			
				totalLength = currentSententialForm.length() + currentRightSide.length() - currentLeftSide.length();
					
				if(currentSententialForm.contains(currentLeftSide) && totalLength <= stringToCheck.length())
				{
					newSententialForm = currentSententialForm.replaceFirst(currentLeftSide, currentRightSide);
					
					
					if(newSententialForm.equals(stringToCheck))
					{
						return true;
					}
					
					sententialFormStack.peek().setProductionIndexUsedToUnfold(i);
					sententialFormStack.push(new Ancestor(newSententialForm, -1));
					
					return check(0);
				}
			}
			
			
			if(currentSententialForm.equals(startSymbol))
			{
 
				return false;
			}
			
			sententialFormStack.removeElementAt(sententialFormStack.size()-1);
			currentScanIndex = sententialFormStack.peek().getProductionIndexUsedToUnfold();
			sententialFormStack.peek().setProductionIndexUsedToUnfold(-1);
 
			return check(currentScanIndex+1);
			
		}
	}

[Andrea1979]

ai miei tempi con tutto quel codice si faceva la classe Stack per intero non solo un metodo... sarei curioso di vedere il resto

[nether]

io non ho capito niente di cosa dovrebbe fare la classe...
in particolare non mi e' chiaro perche' non puoi usare la classe Stack

[xplorer87]

dunque, il codice che ho postato (ditemi pure se devo postare il resto) e' il metodo di una classe che serve a fare il parsing di stringhe per grammatiche di tipo 1. in altre parole, il metodo check controlla se la stringa data (stringToParse) sia riconosciuta o meno dal linguaggio generato da quella grammatica.

comunque, non mi sembra di aver mai detto di non poter usare la classe stack

[Andrea1979]

e che grammatica deve realizzare?

[xplorer87]

non deve realizzarla, ma deve controllare se una stringa (data) gli appartiene. anche la grammatica e' data.

[Andrea1979]

appunto, che grammatica? posta le regole

[xplorer87]

la grammatica la scelgo io di volta in volta, il parser deve funzionare per ogni grammatica di tipo uno (ma non S-extended).

per esempio possiamo usare quella che riconosce tutte le stringhe a^n*b^n*c^n, dove * e' la concatenazione. S e' l'assioma.

S -> aSBC
S -> aBC
CB -> BC
aB -> ab
bB -> bb
bC -> bc
cC -> cc

curiosita', a cosa ti serve saperlo?


ah, un'ultima cosa: ho letto un po' in giro che e' possibile aumentare la dimensione di heap/stack che eclipse assegna di default ai programmi java che runna... ho provato a eseguire da console comandi del tipo java -xss1024k classe.Main per aumentare un po' la dimensione dello stack, ma non e' successo nulla di rilevante. sbaglio qualcosa?