| << Chapter < Page | Chapter >> Page > |
Si costruisca un valutatore di espressioni in notazione postfissa con operatori disomma e moltiplicazione su numeri interi.
Nella soluzione che segue la stringa da analizzareèscritta in testa al codice. Si fa uso del metodo
equals() della classe
String e
del metodo
parseInt() della classe
Integer . Si noti inoltre il matching di
espressione regolare supportato dalla classe
String . In questo caso l'espressione regolare rappresenta una qualsiasi sequenza di cifre.
import java.util.*;
StringTokenizer st = new StringTokenizer("3 12 21 ++ 10*", " +*", true);
Stack pila = new Stack();
String tocco;
int op1=0, op2=0;
while (st.hasMoreTokens()) {
tocco=st.nextToken();
if (tocco.equals("+")) {
if (!pila.isEmpty()) op2 = Integer.parseInt((String)pila.pop());
if (!pila.isEmpty()) {
op1 = Integer.parseInt((String)pila.pop());
pila.push(Integer.toString(op1+op2));
}
}
else if (tocco.equals("*")) {
if (!pila.isEmpty()) op2 = Integer.parseInt((String)pila.pop());
if (!pila.isEmpty()) {
op1 = Integer.parseInt((String)pila.pop());
pila.push(Integer.toString(op1*op2));
}
}
else if (tocco.matches("\\d+")) { // token as a sequence of digits
pila.push(tocco);
println(tocco);
}
}
println(pila);
Un ambito di impiego molto importante della struttura dati a
stackèla grafica interattiva. In particolare, le
trasformazioni geometriche che si effettuano in
OpenGL avvengono per
moltiplicazione matrice-vettore , e
le matrici sono memorizzate sullo
stack delle trasformazioni . Ciòconsente di costruire modelli gerarchici di oggetti nello
spazio. Nel momento in cui si fa
pushMatrix() la cima della pila contiene la matrice di trasformazione
geometrica che si sta applicando ad un particolare oggetto,o in altri termini lo stato corrente del sistema. Le
trasformazioni applicate successivamente alla
pushMatrix() vengono "dimenticate" nel momento
in cui si fa una
popMatrix() , in questo modo
ripristinando lo stato precedente a queste ultimetrasformazioni.
Un semplice esempio di modello gerarchicoèun
braccio meccanico costituito da tre parallelepipedi: unabase, un omero, e un avanbraccio. La collocazione dell'omeroèfissa rispetto alla base, e di questa deve seguirne gli
spostamenti. Allo stesso modo, l'avanbraccioèvincolato
geometricamente all'omero. Il codice seguente disegna ilbraccio meccanico cheèspostabile nel suo complesso
mediante il mouse. Grazie all'uso dello stack, l'omero puòruotare indipendentemente dalla base restando ad essa
vincolato. L'avanbraccio puòruotare indipendentemente
dall'omero restando a questo vincolato.
int LAVANB = 70;
int LOMERO = 80;
int LBASE = 30;
float OMEROT = PI/3;
float AVANROT = PI/5;
void setup(){
size(200, 200, P3D);
}
void avanbraccio(){
pushMatrix();
translate(0, LAVANB/2, 0);
box(20, LAVANB, 20);
popMatrix();
}
void omero(){
pushMatrix();
translate(0, LOMERO/2, 0);
box(20, LOMERO, 20);
popMatrix();
}
void draw(){
background(0);
translate(mouseX,mouseY);
rotateY(PI/6);
box(LBASE);
translate(0, LBASE, 0);
rotateX(OMEROT);
omero();
translate(0, LOMERO, 0);
rotateX(AVANROT);
avanbraccio();
}
La struttura dati chiamata coda ( queue ) organizza una politica di accesso alle informazioni analoga aquella applicata idealmente quando si fa la fila presso uno sportello. Il primo cliente ad essere servitoèil primo che sièpresentato alla coda dello sportello. Una coda (e in realtàanche una pila) puòessere realizzata mediante una lista concatenata, consentendo in questo modo di non porrelimiti alla lunghezza della coda stessa. L'accesso alla lista che supporta la coda avviene mediante un puntatore di testa euno di coda.
Si puòrealizzare una coda mediante concatenazione di nodi e
preparazione di due punti di accesso. Questo garantisce chel'accesso in inserimento ed in estrazione sia efficiente e a
tempo costante. Nella realizzazione qui riportata la classe
Node èatta a realizzare nodi con cargo di tipo
Object generico. La presenza del metodo
toString() garantiràche il nodoèstampabile.
Queue q;
Integer uno = new Integer(1);
Integer due = new Integer(2);
Integer tre = new Integer(3);
void setup() {
q = new Queue();
q.add(uno);
q.add(due);
q.add(tre);
println(q.remove());
println(q.remove());
println(q.remove());
}
class Queue {
int length;
Node first, last;
Queue() {
length = 0;
first = null;
last = null;
}
boolean isEmpty() {
return first == null;
}
void add (Object obj) {
Node node = new Node(obj, null);
if (last != null) {
last.next = node;
}
last = node;
if (first == null) {
first = last;
}
length +=1;
}
Object remove () {
Node result = first;
if (first != null) {
first = first.next;
}
else {
last = null;
}
length -= 1;
return result;
}
}
class Node {
Object cargo;
Node next;
Node() {
cargo = null;
next = null;
}
Node (Object cargo, Node next) {
this.cargo = cargo;
this.next = next;
}
String toString() { //rende l'oggetto di classe Node stampabile
return cargo + " ";
}
} Spesso si preferisce, per ragioni di semplicitàrealizzativa ed
efficienza, realizzare la coda usando un array come struttura disupporto. In questo caso la crescita della codaèlimitata dalla
lunghezza dell'array. Questa realizzazione si chiama
buffer
circolare edèimpiegato, ad esempio, per la realizzazione
di
ritardi variabili nell'elaborazione dei segnali.
Notification Switch
Would you like to follow the 'Programmazione di artefatti interattivi' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|