Questo è il primo di una serie di posts utili agli studenti dell'Università degli studi di Salerno che studiano Informatica o Informatica Applicata e devono sostenere l'esame di Strutture Dati (SD) o di Laboratorio di Algoritmi e Strutture Dati (LASD) con il professor Salvatore La Torre.
Nel seguito di questo articolo, e in quelli successivi, ci saranno i miei esercizi svolti durante il corso; esercizi che rappresentano un requisito essenziale per superare l'esame. Ho deciso di postare il mio lavoro per mantenerne una copia online, e in modo che chiunque possa consultarlo a piacimento; Invito i miei colleghi studenti a desistere dalla tentazione di presentarvi all'esame con i miei esercizi, (che per quanto io possa essere sicuro che siano corretti potrebbero comunque contenere errori) ma al massimo di usarli per confrontarli con i vostri.
Di seguito elenco gli esercizi sulla prima parte del corso, aggiornati al 16/03/2011
Le Eccezioni
Le eccezioni sono tutte uguali quindi ne scrivo una soltanto:
public class EmptyStackException extends RuntimeException
{
private static final String DEFAULTMSG= "Stack Vuoto!";
public EmptyStackException()
{
this(DEFAULTMSG);
}
public EmptyStackException(String err)
{
super(err);
}
}
Esercizi sullo Stack
public interface Stack <E>
{
/**
* Controlla se lo stack è vuoto.
* @return true se lo stack è vuoto, false altrimenti
*/
public boolean isEmpty();
/**
* Ottiene il valore in cima allo stack.
* @return l'elemento al top dello stack
* @throws EmptyStackException se invocato su uno stack vuoto
*/
public E top() throws EmptyStackException;
/**
* Elimina un elemento dalla cima dello stack.
* @return l'elemento cancellato
* @throws EmptyStackException se invocato su uno stack vuoto
*/
public E pop() throws EmptyStackException;
/**
* Inserisce un elemento in cima allo stack.
* @param e l'elemento da inserire
*/
public void push(E o) throws FullStackException;
/**
* Da la dimensione dello stack.
* @return un int da 0 alla dimensione massima dello stack
*/
public int size();
}
Completare l’implementazione della classe generica ArrayStack
public class ArrayStack<E> implements Stack<E>
{
private E stack[];
private int size;
private int capacity;
public static final int CAPACITY = 1024;
public ArrayStack()
{
this(CAPACITY);
}
public ArrayStack(int cap)
{
capacity = cap;
stack = (E[])new Object[capacity];
size = 0;
}
public boolean isEmpty()
{
return (size == 0);
}
public E top() throws EmptyStackException
{
if (isEmpty())
throw new EmptyStackException("Stack Vuoto!");
else
return stack[size-1];
}
public E pop() throws EmptyStackException
{
if (isEmpty())
throw new EmptyStackException("Stack Vuoto!");
else
{
E o = stack[size-1];
stack[size-1] = null;
size--;
return o;
}
}
public void push(E o) throws FullStackException
{
if (size == capacity)
//throw new FullStackException("Stack Pieno!");
{
capacity = capacity*2;
E nuovoStack[] = (E[])new Object[capacity];
for(int i=0; i<size; i++)
{
nuovoStack[i]=stack[i];
}
stack = null;
stack = nuovoStack;
nuovoStack = null;
}
stack[size] = o;
size++;
}
public int size() {
return size;
}
public String toString()
{
String response = "ArrayStack Elements:[ ";
for (int i = 0; i<size; i++)
{
response += (stack[i]+" ");
}
response+= "] size:"+size()+" capacity: "+capacity;
return response;
}
}
Scrivere un metodo Java che usa uno stack per calcolare il reverse di una stringa
Es. Il reverse di “laboratorio” è “oirotarobal”
import java.util.*;
public class StringReverse
{
/**
* uso uno stack per invertire una stringa
*/
public static void main(String[] args)
{
ArrayStack<String> s = new ArrayStack<String>(5);
Scanner in = new Scanner(System.in);
System.out.print("Inserisci una riga: ");
String riga = in.nextLine();
String rigaInvertita ="";
for (int i=0; i< riga.length(); i++)
{
s.push(riga.charAt(i)+"");
}
while(!s.isEmpty())
{
rigaInvertita += s.pop();
}
System.out.println("La riga invertita è: "+rigaInvertita);
}
}
Scrivere un metodo che riceve in input una stringa contenente parentesi tonde e restituisce true se le parentesi sono ben accoppiate e false altrimenti.
Esempio: x((abc)()) è un’espressione ben parentesizzata (as(df)))( nonèun’espressionebenparentesizzata
Modificare la funzione in modo che funzioni con stringhe contenenti sia parentesi tonde che parentesi quadre
Esempio: x[(abc)()]([]) è un’espressione ben parentesizzata (as(df)]( non è un’espressione ben parentesizzata
import java.util.*;
public class ControlloParentesiTonde
{
public static void main(String[] args)
{
ArrayStack<String> s = new ArrayStack<String>(5);
Scanner in = new Scanner(System.in);
System.out.println("Verifica Annidamento Parentesi Tonde, Quadre e Graffe\n" +
"-----------------------------------------------------");
System.out.print("Scrivi l'espressione: ");
String riga = in.nextLine();
boolean correct = true;
for (int i=0; i< riga.length(); i++)
{
try
{
if (riga.charAt(i)=='(' || riga.charAt(i)=='[' || riga.charAt(i)=='{')
s.push(riga.charAt(i)+"");
if (riga.charAt(i)==')')
{
if (s.top().equals("("))
s.pop();
}
if (riga.charAt(i)==']')
{
if (s.top().equals("["))
s.pop();
}
if (riga.charAt(i)=='}')
{
if (s.top().equals("{"))
s.pop();
}
}
catch(EmptyStackException e)
{
correct = false;
break;
}
}
if (correct && s.isEmpty())
System.out.println("Allineamento parentesi corretto");
else
System.out.println("Allineamento parentesi ERRATO");
}
}
Post
grande!!
RispondiElimina