|
| I dette kapitel skal vi studere to fundamentale datastrukturer: stakke
og køer. |
|
|
1. Stakke
|
| LIFO
| En stak er en såkaldt LIFO datastruktur. LIFO betyder:
"Last In, First Out", og beskriver
den bevægelse som data foretager, når det indsættes, og
når det udtages. Når man udtager et element fra stakken, vil
det være det senest indsatte element. |
|
| At man kalder denne datastruktor: en stak, stammer fra stak-begrebet i
den virkelige verden: |
|
|
|
| Push og pop
| Når vi indsætter et element i containeren, sker det ved at
lægge det ovenpå de elementer, der allerede befinder sig i stakken
- vi kalder denne operation: push (dk.: skubbe). Mens det at fjerne
et element fra containeren, sker ved at vi tager det der ligger øverst
på stakken - vi kalder denne operation: pop (eng.: "pop
off": dk.: stikke af, nærmest et slagord) |
|
|
|
|
| Man kan implementere en stak på flere forskellige måder, og
vi skal i det følgende se på to af disse. Vi vil dog først
lave et generelt Stack-interface,
der beskriver de operationer som en implementation skal have, uanset hvordan
den ellers er realiseret:
|
|
|
|
Stack.java
|
public interface Stack {
public void push( Object obj );
public Object pop();
public Object peek();
public int size();
public boolean empty();
public boolean full();
public void clear();
} |
|
|
|
| Vi genkender her push,
og pop, der er containerens
indsæt- og udtag-metoder. Vi har også medtaget en metode: peek,
der ofte er nyttig. peek-metoden
returnerer det øverste element fra stakken, uden at fjerne
det. Dernæst følger en række simple standard-metoder,
der findes i næsten alle containere. |
|
|
1.1 Implementeret med array
|
|
| Anvender man et array, til at implementere en stak, gøres det på
følgende måde: |
|
|
|
ArrayStack.java
|
public class ArrayStack implements Stack {
private Object[] stack;
private int size;
public ArrayStack() {
this( 10 );
}
public ArrayStack( int length ) {
stack = new Object[ length ];
clear();
}
public void push( Object obj ) {
if ( !full() ) {
stack[size] = obj;
size++;
} else
throw new StackOverflowError();
}
public Object pop() {
if ( !empty() ) {
size--;
return stack[size];
} else
return null;
}
public Object peek() {
if ( !empty() )
return stack[size-1];
else
return null;
}
public int size() {
return size;
}
public boolean empty() {
return size == 0;
}
public boolean full() {
return size == stack.length;
}
public void clear() {
size = 0;
}
} |
|
|
|
| Man skal her særligt lægge mærke til problematikken
omkring array'ets statiske længde. I forbindelse med pop
og peek kan vi blot
returne null, som
en indikation af, at der ikke var noget element at pop'e
fra stakken. Med push
er det straks mere ubekvemt. Det er en mulighed at lade metoden returnere
boolsk om operationen lykkedes. Alternativt kan man bruge en exception som
vi har valgt her. |
| Overflow
| Mere præcist bruger vi et Error,
idet vi kaster et StackOverflowError,
hvis stakken er fuld i forvejen. Valget af StackOverflowError
skyldes primært, at den findes i forvejen. StackOverflowError
kastes normalt kun når stakken i den virtuelle maskine løber
fuld. Man kaldet det generelt et overflow, når man vil lægge
et element på en stak, der allerede er fuld - den flyder over! |
|
|
1.2 Implementeret med liste
|
|
| Idéen med at implementere en stak vha. en liste, er at en liste
aldrig løber fuld. Samtidig fylder den ikke mere, end der er elementer
i stakken, da dens størrelse ændrer sig dynamisk (dog vil hvert
element til gengæld fylde mere end i et array). |
| Adapter
| Når vi implementerer Stack-interfacet,
gør vi det ved at lave en klasse, der anvender en liste som container.
Det betyder, at den fungerer som Adapter (se evt. Adapter
Pattern)
|
|
| Lad os se implementationen af klassen: ListStack:
|
|
|
|
ListStack.java
|
import java.util.LinkedList;
public class ListStack implements Stack {
private LinkedList stack;
public ListStack() {
stack = new LinkedList();
clear();
}
public void push( Object obj ) {
stack.addFirst( obj );
}
public Object pop() {
return stack.removeFirst();
}
public Object peek() {
return stack.getFirst();
}
public int size() {
return stack.size();
}
public boolean empty() {
return stack.isEmpty();
}
public boolean full() {
return false;
}
public void clear() {
stack.clear();
}
} |
|
|
|
| Man bemærker at implementationen er uhyre enkel, idet vi med en
liste undgår de fejl-situationer, som skulle tages i betragtning i
forbindelse med et array. |
|
| Man bemærker, at full-metoden
ikke er specielt relevant for en liste, men at vi implementerer den for
at holde interfacet generelt (og fordi vi skal). |
|
|
2. Køer
|
| FIFO
| En kø er en såkaldt FIFO datastruktur. FIFO
betyder: "First In, First Out", og
beskriver den bevægelse som data foretager, når det indsættes,
og når det udtages. Når man udtager et element fra køen,
vil det altid være det "ældste" element, dvs. det
element, der har befundet sig længst tid i køen - det element
der står forrest! |
|
|
|
|
| I lighed med implementationen af en stak, vil vi også her erklære
et interface, og implementere en kø vha. henholdvis et array og en
liste:
|
|
|
|
Queue.java
|
interface Queue {
public void insert( Object obj );
public Object remove();
public Object peek();
public int size();
public boolean empty();
public boolean full();
public void clear();
} |
|
|
|
| I forbindelse med en kø, kalder vi de to indsæt- og udtag-metoder:
insert og remove. |
|
|
2.1 Implementeret med array
|
|
| At implementere en kø i et array kræver en del omtanke. |
|
| I forbindelse med en kø, vil vi ikke alene have en tæller:
size, der fortæller
hvor mange elementer der er i køen. Vi skal også have to index:
first og last,
der fortæller hvor køen starter, henholdsvis hvor den slutter:
|
|
|
|
| X
| I figuren markerer krydserne elementer i køen.
|
| Begge går mod højre
| En kø vil ikke altid starte ved index 0,
da first vil bevæge
sig mod højre, efterhånden som vi fjerner elementer fra køen.
last vil ligeledes
bevæge sig mod højre, når vi indsætter elementer
i køen. Bemærk, at vi vælger at lade last
udpege den næste ledig plads i køen - ikke det
sidste element i køen, mens first
udpeger det forrest element.
|
|
| Der skal ikke meget fantasi til at forestille sig, at vi får et
problem når køen når ud i enden af array'et. Eftersom
der løbende opstår ledige pladser fra starten af array'et og
fremefter, efterhånden som vi udtager elementer og first
flytter sig mod højre, er løsningen naturligvis at genbruge
disse pladser.
|
| Modulus
| For at kunne gøre dette, må vi flytte last
tilbage til index 0,
når den går ud over kanten af array'et. Det gøres bekvemt
med modulus,
idet vi anvender formlen:
|
|
|
last = (last+1) %
længden
|
|
| På et tidspunkt vil også first
ryge ud over kanten, og da first
på samme måde bevæger sig mod højre, kan vi anvende
den samme formel for begge index:
|
|
|
first
= (first+1) % længden
|
|
| Hvis vi rent visuelt bøjer array'et rund, så det danner en
cirkel, kan vi se hvilken effekt dette får:
|
|
|
|
| Cirkulært array
| Ved at bruge modulus, i forbindelse med inkrementeringen af index, opnår
vi at array'et kommer til virke som et cirkulært array. I figuren
til venstre, har vi markeret det sted hvor de to ender af array'et er sat
sammen, med en stiplet linie.
|
|
| Implementationen af en kø med et array bliver som følger:
|
|
|
|
ArrayQueue.java
|
public class ArrayQueue implements Queue {
private Object[] queue;
private int first, last;
private int size;
public ArrayQueue() {
this( 10 );
}
public ArrayQueue( int length ) {
queue = new Object[ length ];
clear();
}
public void insert( Object obj ) {
if ( !full() ) {
queue[ last ] = obj;
last = (last+1) % queue.length;
size++;
} else
throw new StackOverflowError();
}
public Object remove() {
if ( !empty() ) {
Object res = queue[ first ];
first = (first+1) % queue.length;
size--;
return res;
} else
return null;
}
public Object peek() {
if ( !empty() )
return queue[ first ];
else
return null;
}
public int size() {
return size;
}
public boolean empty() {
return size == 0;
}
public boolean full() {
return size == queue.length;
}
public void clear() {
first = last = 0;
size = 0;
}
} |
|
|
| size
nødvendig
| Bemærk, at det tomme array har både first
og last sat til 0.
For at kunne skelne mellem de to situationer, hvor køen er henholdsvis
tom og fuld anvender vi size,
da first vil være
lig last i begge situationer,
og dette kriterium derfor ikke kan anvendes. |
|
|
2.2 Implementeret med liste
|
|
| Pga. af dynamikken i en hægtet liste, bliver implementation af
en kø meget enkel: |
|
|
|
ListQueue.java
|
import java.util.LinkedList;
public class ListQueue implements Queue {
private LinkedList queue;
public ListQueue() {
queue = new LinkedList();
}
public void insert( Object obj ) {
queue.addLast( obj );
}
public Object remove() {
return queue.removeFirst();
}
public Object peek() {
return queue.getFirst();
}
public int size() {
return queue.size();
}
public boolean empty() {
return queue.isEmpty();
}
public boolean full() {
return false;
}
public void clear() {
queue.clear();
}
} |
|
|
|
| Vi vælger her at indsætte i slutningen af listen og udtage
i starten. Man kunne naturligvis lige så vel have valgt at gøre
det omvendt. |
|
|
3. Eksempler
|
|
|
3.1 Postfix notation
|
|
| (Med mindre andet er nævnt, antages det i det følgende,
at alle operander er på ét ciffer) |
|
| Vi er i almindelighed vant til at skrive regneudtryk som f.eks.: |
|
|
5 + 3 * 8
|
| Mellem
| hvor vi placerer operatorerne mellem operanderne. |
| Præcedens
| Samtidig har vi præcedens-regler, der f.eks. bestemmer at multiplikation
skal udføres før addition; hvorved resultatet af ovenstående
bliver 29, og ikke 64, som man ville få; hvis man evaluerede fra venstre
mod højre uden skelen til præcedens. |
|
| Hvis vi ønskede at resultatet skulle være 64, og dermed,
at 5+3 skulle evalueres først, måtte vi ty til paranteser for
at gennemtvinge en anden evalueringsrækkefølge: |
|
|
( 5 + 3 ) * 8
|
|
| Selvom vi betragter denne notationsform som en selvfølge, er det
ikke en nødvendighed. I virkeligheden findes der en mere enkelt notation,
som eliminerer behovet for såvel præcedens som paranteser -
den kaldes postfix notation. |
| Omvendt polsk notation
| Den notation som vi almindeligvis bruger, kaldes infix notation,
fordi vi placerer operatorerne mellem (in) operanderne. På samme måde
betyder postfix notation, at vi placerer operatorerne efter (port)
operanderne. Der skal ikke meget fantasi til at forestille sig, at der også
findes noget, der hedder prefix notation; hvor operatorerne placerer
før (pre) operanderne. Prefix notation blev opfundet af en polsk
matematiker: J. Lukasiewicz, og pudsigt nok, kalder man derfor også
postfix notation for: omvendt polsk notation - fordi det er
det omvendte af, hvad Lukasiewicz fandt på! |
|
|
3.1.1 Evaluering af postfix
|
|
| Inden vi ser hvordan man kan oversætte et udtryk fra infix notation
til postfix notation, vil vi se hvorfor de er så fordelagtige. Som
nævnt er fordelen ved postfix notation, at man ikke har behov for
præcedensregler og paranteser. |
|
| Udtrykket: ( 5 + 3 ) * 8, skrives på følgende måde
i postfix notation: |
|
|
5 3 + 8 *
|
| Bruger en stak
| Udtryk skrevet i postfix notation evalueres fra venstre mod højre,
vha. en stak. Idéen med stakken er at man push'er
operanderne efterhånden som man møder dem, idet man læser
fra venstre mod højre. Hver gang man møder en operator, pop'er
man de to øverste elementer fra stakken, udfører operationen
på dem, og push'er
resultatet tilbage på stakken. Bemærk, at det første
element man pop'er
skal være højre operand, mens det andet skal stå på
venstre side af operatoren. Denne operand-rækkefølge svarer
til, at man lægger hovedet på skrå mod venstre, når
man ser på elementerne på stakken. Dette skyldes, at man ved
at lægge hovedet på skrå mod venstre, vil se operanderne
i den rækkefølge de stod i den oprindelige postfix notation. |
|
| Lad os evaluere ovenstående udtryk: |
|
| Først har vi udgangspunktet: Udtrykket står klar i postfix
notation, og vi har en tom stak:
|
|
|
|
|
| Vi ser, at de to første elementer i udtrykket er operander, og
push'er dem en efter
en på stakken: |
|
|
|
|
| Dernæst møder vi en operator: +,
som vi lader virke på de to øverste elementer fra stakken.
Vi push'er resultatet:
8, tilbage på stakken: |
|
|
|
|
| Det næste element er en operand: 8,
som vi push'er på
stakken: |
|
|
|
|
| Endelig er der det sidste element i udtrykket: operatoren *,
som vi lader virke på de to øverste elementer fra stakken.
Vi push'er resultatet:
64, tilbage på stakken: |
|
|
|
|
| Vi har nu udtømt udtrykket, og resultatet: 64, kan pop'es
fra stakken. |
|
| Som man kan se, er metoden meget enkel, og den egner sig derfor godt som
algoritme til en computer. |
|
| |
| Øvelse:
| Evaluer udtrykket: |
|
|
5 8 3 / -
|
|
| Vær særlig opmærksom på operandernes rækkefølge,
når du bruger operatorerne: /
og -. |
|
| Resultatet skal give 3. |
|
|
3.1.2 Fra infix til postfix
|
|
| At oversætte fra infix til postfix notation, er ikke så enkelt
som at evaluere postfix notation - det kræver et større "apparat". |
| Tanenbaum
| Jeg lærte selv at konvertere fra infix til postfix notation vha.
Andrew S. Tanenbaums: "Sctructured Computer Organisation, 2nd. ed.",
s. 221-27; hvor han gennemgår en algoritme der stammer fra Dijkstra.
I forbindelse med beskrivelsen af denne algoritme bruger Tanenbaum en illustration
med en jernbane mellem New York og Californien, der går via Texas.
Jeg vil i min gennemgang bruge en mere lokal jernbane, så vi skal
ud og køre med tog fra Silkeborg til Herning, via Ikast:
|
| Jernbane
|
|
|
| Pilene viser de mulige retning vi kan køre i, og man bemærker,
at der er et sporskifte på turen fra Silkeborg mod vest. |
| Infix i Silkeborg
| Man starter med at placere udtrykket i dets infix notation, i Silkeborg.
Man opdeler udtrykket i sine grundelementer: operatorer og operander (i
det følgende betegnet som tokens), således at det første
token står forrest; hvilket også er den naturlige orientering
sådan som tegningen bevidst er lavet. |
|
| Hvis vi f.eks. ønskede at oversætte udtrykket ovenfor, til
postfix notation, ville vi starte med: |
| Starten
|
|
|
| Disse syv vogne skal nu sendes af sted fra Silkeborg, en efter en. Vi
placerer også to "stopklodser" i henholdsvis Silkeborg og
Ikast - markeret med et T,
for Terminator. |
| Køer og stak
| Det er væsentligt at bemærke, at vi vil bruge køer
i henholdsvis Silkeborg og Herning, mens vi vil bruge en stak i Ikast. Det
betyder at vognene i Ikast vil forlade stationen "last in, first out",
når de fortsætter mod Herning. |
|
| For operander gælder der, at de altid kører direkte fra Silkeborg
til Herning. Der vil derfor kun komme operatorer til Ikast. |
|
| Reglerne for hvordan operatorerne flyttes, kan opstilles i en tabel |
| Flytte-regler
|
| |
T |
+ |
- |
* |
/ |
( |
) |
| T |
4 |
1 |
1 |
1 |
1 |
1 |
5 |
| + |
2 |
2 |
2 |
1 |
1 |
1 |
2 |
| - |
2 |
2 |
2 |
1 |
1 |
1 |
2 |
| * |
2 |
2 |
2 |
2 |
2 |
1 |
2 |
| / |
2 |
2 |
2 |
2 |
2 |
1 |
2 |
| ( |
5 |
1 |
1 |
1 |
1 |
1 |
3 |
|
|
| Tabellen bruges på den måde at man ser hvilke to operatorer
der står i Silkeborg og Ikast. Dernæst slår man op i tabellen,
idet Silkeborg er vandret og Ikast er lodret. |
|
| Tallene i tabellen står for følgende handlinger, man dernæst
udfører: |
| Handlinger
|
|
Nr.
|
Handling |
|
1
|
En vogn kører fra Silkeborg til Ikast |
|
2
|
En vogn kører fra Ikast til Herning |
|
3
|
Der forsvinder en vogn i både Ikast og Silkeborg |
|
4
|
Terminer - Resultatet står i Herning |
|
5
|
Fejl |
|
| Postfix i Herning
| Når man når til at udføre handling nr. 4, står
resultatet, i postfix notation, i Herning. |
|
| |
|
| Lad os se hvordan dette forløber i forbindelse med eksemplet ovenfor. |
| Starten, med alle vogne i Silkenorg
|
|
| 1-2: Venstre-parantes til Ikast, og operand direkte
til Herning
|
|
| 3-4: Operator til Ikast (se tabellen), og operand direkte
til Herning
|
|
| 5: Operator fra Ikast til Herning (se tabellen)
|
|
| 6: De to paranteser forsvinder (se tabellen)
|
|
| 7-8: Operator til Ikast (se tabellen), og operand direkte
til Herning
|
|
| 9: Operator fra Ikast til Herning (se tabellen)
|
|
|
| Og dermed har vi udtrykket stående i Herning, i den ønskede
postfix notation. |
|
|
3.1.3 Implementation
|
|
| I forbindelse med implementationen af konvertering af infix til postfix
notation, samt evaluering af postfix notation, er den største udfordring
at håndtere operatorer og operander. De er typemæssigt forskellige,
og et infix/postfix udtryk er derfor en heterogen liste af elementer. Vi
vælger at lave en fælles superklasse til disse, som vi kalder
Token:
|
| Token-klasser
|
|
|
| Vi har i samme åndedrag indført en Terminator-klasse,
til at repræsentere terminatorerne i henholdsvis Silkeborg og Ikast. |
|
| Det eneste vi placerer i Token-klassen
er to fabriks-metoder, der konstruerer en operand/operator alt efter hvad
der syntaktisk er grundlag for: |
|
|
|
Token.java
|
public abstract class Token {
public static Token createToken( char c ) {
switch ( c ) {
case '+':
return new Plus();
case '-':
return new Minus();
case '*':
return new Gange();
case '/':
return new Divider();
case '(':
return new VenstreParantes();
case ')':
return new HojreParantes();
default:
return new Operand( "" + c );
}
}
public static Token createToken( String s ) {
if ( s.length() == 1 )
return createToken( s.charAt(0) );
else
return new Operand( s );
}
} |
|
|
|
| Den sidste af fabriks-metoderne anvendes i forbindelse med evalueringen
af udtryk i postfix notation, da der i den forbindelse kan optræde
operander med mere end et ciffer. |
|
| Dernæst har vi Operand-klassen: |
|
|
|
Operand.java
|
public class Operand extends Token {
private int operand;
public Operand( String s ) {
this( Integer.parseInt( s ) );
}
public Operand( int operand ) {
this.operand = operand;
}
public int getValue() {
return operand;
}
public String toString() {
return "" + operand;
}
} |
|
|
|
| Operator-klasserne
har en fælles abstrakt super-klasse: |
|
| Og Operator-klassen: |
|
|
|
Operator.java
|
public abstract class Operator extends Token {
public Operand evaluate( Operand op1, Operand op2 ) {
return new Operand( evaluateHook( op2.getValue(), op1.getValue() ) );
}
public abstract int evaluateHook( int op1, int op2 );
} |
|
|
| Template Method
| Her anvendes Template
Method for at gøre livet lettere for de mange subklasser.
Template-metoden får fat i de to integers, og laver den nye
instans af Operand,
der skal returneres. |
|
| Bemærk, at evaluate-metoden
bytter om på operanderne. Det gør den, da den første
parameter vil være det øverste element fra stakken (se senere). |
|
| Subklasserne kan laves på samlebånd: |
|
|
|
Plus.java
|
public class Plus extends Operator {
public int evaluateHook( int v1, int v2 ) {
return v1 + v2;
}
public String toString() {
return "+";
}
} |
|
|
|
|
|
Minus.java
|
public class Minus extends Operator {
public int evaluateHook( int v1, int v2 ) {
return v1 - v2;
}
public String toString() {
return "-";
}
} |
|
|
|
|
|
Gange.java
|
public class Gange extends Operator {
public int evaluateHook( int v1, int v2 ) {
return v1 * v2;
}
public String toString() {
return "*";
}
} |
|
|
|
|
|
Divider.java
|
public class Divider extends Operator {
public int evaluateHook( int v1, int v2 ) {
return v1 / v2;
}
public String toString() {
return "/";
}
} |
|
|
|
|
|
VenstreParantes.java
|
public class VenstreParantes extends Operator {
public int evaluateHook( int v1, int v2 ) {
throw new NoSuchMethodError();
}
public String toString() {
return "(";
}
} |
|
|
|
|
|
HojreParantes.java
|
public class HojreParantes extends Operator {
public int evaluateHook( int v1, int v2 ) {
throw new NoSuchMethodError();
}
public String toString() {
return ")";
}
} |
|
|
|
| Det eneste, der er værd at bemærke, er implementationen af
hook-metoden i: VenstreParantes
og HojreParantes,
da disse ikke giver mening i relation til paranteser. Såfremt de skulle
blive kaldt, kaster de en NoSuchMethodError. |
|
| Endelig har vi de to metoder: infixToPostfix
og evaluatePostfix,
og en testanvendelse: |
|
|
|
Main.java
|
import java.text.*;
public class Main {
//<T> + - * / ( )
private static int[][] action = { { 4, 1, 1, 1, 1, 1, 5 }, //<T>
{ 2, 2, 2, 1, 1, 1, 2 }, // +
{ 2, 2, 2, 1, 1, 1, 2 }, // -
{ 2, 2, 2, 2, 2, 1, 2 }, // *
{ 2, 2, 2, 2, 2, 1, 2 }, // /
{ 5, 1, 1, 1, 1, 1, 3 } }; // (
/*
* 1. En vogn går fra Silkeborg til Ikast
* 2. En vogn går fra Ikast til Herning
* 3. Der forsvinder både en vogn i Ikast og Silkeborg
* 4. Terminer - resultatet står i Herning
* 5. Fejl
*/
private static String infixToPostfix( String infix ) {
ListQueue silkeborg = new ListQueue();
ListStack ikast = new ListStack();
ListQueue herning = new ListQueue();
/*
* Gøre vognene klar i Silkeborg
*/
StringCharacterIterator it = new StringCharacterIterator( infix );
it.first();
do {
silkeborg.insert( Token.createToken( it.current() ) );
} while ( it.next() != CharacterIterator.DONE );
silkeborg.insert( new Terminator() );
/*
* Gøre klar i Ikast
*/
ikast.push( new Terminator() );
/*
* Turen går fra Silkeborg til Herning over Ikast
*/
loop:
while ( true ) {
if ( !(silkeborg.peek() instanceof Operand) ) {
switch ( action[ tokenToIndex( (Token) ikast.peek() ) ]
[ tokenToIndex( (Token) silkeborg.peek() ) ] ) {
case 1: // En vogn går fra Silkeborg til Ikast
ikast.push( silkeborg.remove() );
break;
case 2: // En vogn går fra Ikast til Herning
herning.insert( ikast.pop() );
break;
case 3: // Der forsvinder både en vogn i Ikast og Silkeborg
ikast.pop();
silkeborg.remove();
break;
case 4: // Terminer - resultatet står i Herning
break loop;
case 5: // Fejl
System.out.println( "Error" );
break;
}
} else
herning.insert( silkeborg.remove() );
}
StringBuffer sb = new StringBuffer();
while ( !herning.empty() )
sb.append( herning.remove().toString() );
return sb.toString();
}
private static int tokenToIndex( Token token ) {
if ( token instanceof Terminator )
return 0;
else if ( token instanceof Operator ) {
Operator operator = (Operator) token;
if ( operator.equals( '+' ) )
return 1;
else if ( operator.equals( '-' ) )
return 2;
else if ( operator.equals( '*' ) )
return 3;
else if ( operator.equals( '/' ) )
return 4;
else if ( operator.equals( '(' ) )
return 5;
else if ( operator.equals( ')' ) )
return 6;
else
return -1;
} else
return -1;
}
private static int evaluatePostfix( String postfix ) {
ListStack stack = new ListStack();
ListQueue expression = new ListQueue();
/*
* Gøre udtrykket klar
*/
StringCharacterIterator it = new StringCharacterIterator( postfix );
it.first();
do {
expression.insert( Token.createToken( it.current() ) );
} while ( it.next() != CharacterIterator.DONE );
/*
* Evaluer udtryk
*/
while ( !expression.empty() ) {
Token token = (Token) expression.remove();
if ( token instanceof Operator ) {
Operator operator = (Operator) token;
stack.push( operator.evaluate( (Operand) stack.pop(),
(Operand) stack.pop() ) );
} else
stack.push( token );
}
return ((Operand) stack.pop()).getValue();
}
public static void main( String[] argv ) {
String infix = "5-8/3";
String postfix = infixToPostfix( infix );
int result = evaluatePostfix( postfix );
System.out.println( infix + " = " + postfix + " = " + result );
}
} |
|
|
|
|
|
| |
