| << Chapter < Page | Chapter >> Page > |
Lo
stack , o pila,èuna struttura dati di
grande importanza. Ad esempio, essaèimplicitamente coinvolta
nell'esecuzione di codice ricorsivo, quale quello del metodo
printBackward . In effetti, a runtime le chiamate
a procedura sono sistemate, insieme ai loro parametri, unasopra all'altra nell'ordine in cui sono
invocate. Nell'esempio, alla terza chiamata ricorsiva di
printBackward ci si trova in cima allo stack una
chiamata su una lista di un solo elemento.
Ad uno stack si accede mediante due sole operazioni, la
push (immissione) di un elemento in cima allo
stack, e la
pop (rimozione) di un elemento dalla
cima dello stack.Una classe
Stack ègiàdisponibile in Java (e in
Processing) dopo aver importato
java.util.* . Essa
funziona su oggetti della classe
Object , cheèla
piùgenerica delle classi Java, nonchésuperclasse di tutte.
La visita in ordine inverso, dalla coda alla testa, degli
elementi di una lista si puòottenere per via ricorsiva,
come giàvisto in
. Alternativamente, si puòusare uno stack
come struttura dati di appoggio.
import java.util.*;
IntList lista;
Stack pila;
void setup() {
pila = new Stack();
lista = new IntList();
lista.addFirst(3);
lista.addFirst(2);
lista.addFirst(1);
lista.printList();
for (Node node = lista.head; node != null; node = node.next) {
pila.push(node);
}
while (!pila.isEmpty()) {
Node node = (Node) pila.pop();
print(node);
}
}
class IntList {
... omissis ...
class Node {
... omissis ... Si puònotare che
isEmpty() della classe
Stack che consente di verificare la condizione di pila vuota,pop() . Questoèun generico
Object in quanto la classe
Stack nonèin grado di conoscere il tipo dei suoi elementi.pila viene usata in luogo del run-time stack.Lo stackèanche la struttura dati che con maggior
naturalezza supporta la valutazione di espressioni. Peressere piùprecisi, data una stringa contenente operandi e
operatori in
notazione
postfissa , una scansione lineare della stringa
accompagnata dall'utilizzazione di uno stack di appoggio puòconsentire una facile valutazione della espressione. E'
necessario inoltre individuare i
token della stringa (operandi o operatori), separati da
delimitatori che tipicamente sono caratteri dispaziatura. C'èuna classe di
java.util ,
chiamata
StringTokenizer , che fa proprio
questo. Ad esempio, la "tokenizzazione" di una espressionein notazione postfissa si puòeseguire con:
import java.util.*;
StringTokenizer st = new StringTokenizer("11 22+33*", " +-*/", true);
while (st.hasMoreTokens())
println(st.nextToken()); dove gli argomenti di
StringTokenizer() , oltre
a comprendere la stringa da analizzare, comprendono la listadei delimitatori e un parametro boolean che indica che i
separatori devono essere considerati anch'essi come token.La valutazione di espressioni su stringheèun esempio semplice di
parsing .
Notification Switch
Would you like to follow the 'Programmazione di artefatti interattivi' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|