Algorytmy i struktury danych - wykład 4. strona: 1
Listy, stosy i kolejki
W tym wykładzie zostaną przedstawione struktury danych, naleŜące do
tzw. abstrakcyjnych struktur danych - ADT (ang. Abstract Data Type),
które są wykorzystywane prawie w kaŜdej aplikacji. W projektowaniu
programu definicja ADT wymaga specyfikacji zbiorów danych i działań na
tych zbiorach.
Listy, podobnie jak tablice uŜywane są jako struktury bazodanowe do
przechowywania kartotek osobowych, danych finansowych, katalogów i
tym podobnych danych, które odpowiadają rzeczywistym obiektom. Ich
charakterystyczną cechą jest ułatwienie dostępu do danych, czyli operacji
wstawiania, usuwania i wyszukiwania.
Stosy i kolejki częściej uŜywane są jako narzędzia programisty.
Stanowią raczej pomoc konceptualną przy rozwiązywaniu róŜnych
problemów i są tworzone na czas wykonania pewnego zadania i po jego
wykonaniu są niepotrzebne. W przypadku tych struktur dostęp do
elementów jest ograniczony. Tylko jeden element moŜe zostać pobrany
lub usunięty w danej chwili. Definicja tych struktur zakłada, Ŝe dostęp do
pozostałych elementów jest niemoŜliwy.
ADT: LISTA
Jest to skończony ciąg elementów ustalonego typu ElementType
a
1
, a
2
, . . . , a
n
, ,
n >= 0
przy czym ElementType moŜe być np. typem struktury, int, string itp.
Terminologia:
•
n – długość listy
•
a
1
– pierwszy element listy, a
n
– ostatni
•
a
i
poprzedza a
i+1
,
•
a
i
jest na pozycji i-tej
Algorytmy i struktury danych - wykład 4. strona: 2
Przykładowy zestaw operacji struktury LISTA
1.
END(L) - zwraca pozycję następną po ostatnim elemencie listy
„pierwsze wolne miejsce")
2.
FIRST(L) - zwraca pierwszą pozycję w L, wynik równy END(L) gdy
L pusta
3.
MAKENULL(L) - powoduje Ŝe L staje się listą pustą (lub utworzenie
nowej pustej listy)
4.
INSERT(x, p, L) - wstawia element x typu ElemType na pozycję p
w liście L, przesuwając elementy z pozycji p i wyŜszych o jedną
pozycję dalej (czyli lista się wydłuŜa)
przed: a
1
, a
2
, ..., a
p-1
,
a
p
, ..., a
n
po: a
1
, a
2
, ..., a
p-1
,
x
, a
p
, ..., a
n
je
ś
li p=END(L) to wynik:
a
1
, a
2
, ..., a
p-1
, a
p
, ..., a
n
,
x
jeśli w liście L nie istnieje pozycja p to wynik niezdefiniowany
5.
LOCATE(x, L) - oblicza pozycję ‘x’ w liście L jeśli x więcej niŜ raz w
liście L to zwraca pierwszą pozycję, jeśli x nie ma w liście to zwraca
END(L)
6.
RETRIEVE(p, L) - zwraca element na pozycji p w liście rezultat
niezdefiniowany jeśli nie ma pozycji p w liście
7.
DELETE(p, L) - usuwa element na pozycji p (czyli lista się skraca)
przed: a
1
, a
2
, ..., a
p-1
,
a
p
,
a
p+1
, ..., a
n
po: a
1
, a
1
, ..., a
p-1
,
a
p+1
, ..., a
n
wynik niezdefiniowany jeśli w L nie ma pozycji p
8.
NEXT(p, L), PREVIOUS(p, L) - podają pozycję następną i
poprzednią do p, niezdefiniowane gdy nie ma pozycji p w L,
NEXT niezdefiniowane gdy p=END(L), PREVIOUS niezdefiniowane
gdy p=1
9.
PRINTLIST(L) - drukuj w kolejności występowania na liście
Mając zrealizowaną strukturę listy jak wyŜej moŜemy zrealizować na
przykład następujące zadanie: usunąć wszystkie powtarzające się
elementy z listy L.
Algorytmy i struktury danych - wykład 4. strona: 3
lista L ; // L jest list
ą
noDups() // usuwa duplikaty z listy L
{ p,q typu pozycja // p – b
ę
dzie 'aktualn
ą
' pozycj
ą
// q b
ę
dzie szuka
ć
takich samych elementów
p = L.FIRST();
while ( p != L.END() )
{ q = L.NEXT (p)
while ( q
!=
L.END() )
if (L.Retrieve(p) == L.RETRIEVE(q))
then L.DELETE(q);
else q = L.NEXT(q);
p = L.NEXT(p);
}
} // noDups()
Implementacja abstrakcyjnych struktury danych w ustalonym języku
opisu algorytmów (w szczególności moŜe to być konkretny język
programowania) polega na deklaracji typów danych, zmiennych tych
typów oraz deklaracji metod, których działanie spełnia warunki definicji
struktury.
Zalety wyraźnego rozdzielenia definicji abstrakcyjnej od realizacyjnej
to, łatwiejsza modyfikowalność programu – zmieniamy tylko szczegóły
implementacyjne w jednym miejscu programu, postać operacji i sposób
ich wykorzystania są bez zmian.
Tablicowa implementacja listy w Javie.
maxSize -1
a
0
a
1
a
2
last
0
wolne
Algorytmy i struktury danych - wykład 4. strona: 4
class listArray
{ private int maxSize; // rozmiar tablicy zawieraj
ą
cej liste
private long[] list; // tablica zawieraj
ą
ca liste
private int last; // liczba elementów listy
//----------------------------------------------------------
public listArray(int Size) // konstruktor
{ // MakeList(L)
maxSize = Size;
list = new long[maxSize]; // tworzymy list
ę
pust
ą
last = 0; // na razie brak elementów
}
//----------------------------------------------------------
public int End(){ // zwraca pozycje za ostatnim elementem
return last;
} // end()
//----------------------------------------------------------
public int First() // zwraca pierwsza pozycj
ę
na li
ś
cie
{
return 0;
}
//----------------------------------------------------------
public int Locate(long searchElem)
{ // szukanie okre
ś
lonej warto
ś
ci
int j;
for(j=0; j<last; j++) // dla ka
Ŝ
dego elementu...
if(list[j] == searchElem) // czy znaleziono?
return j; // tak, zwraca pozycje
return last; // nie, zwraca pozycje za
} // end Locate() // ostatnim elementem
//----------------------------------------------------------
public void Insert(long x, int p) // wstawienie x do listy
// na pozycj
ę
p
{
if (last >= maxSize) error ("lista pelna");
else
if ( (p > last) || ( p < 0) )
error ("pozycja nie istnieje");
else
{
for(int q =last; q > p; q--)
list[q] = list[q-1];
list[p] = x;
last++;
}
} //end Insert()
//----------------------------------------------------------
public void Delete(int p) // usuni
ę
cie elementu listy
{
if (last == 0) error("lista pusta");
else
if ( (p >= last) || ( p < 0) )
error ("pozycja nie istnieje");
else
{
Algorytmy i struktury danych - wykład 4. strona: 5
for(int q = p; q < last; q++) // przesuwamy pozostałe
// elementy
list[q] = list[q+1];
last--; // zmniejszamy licznik
// elementów
}
} // koniec delete()
//----------------------------------------------------------
public void printList() // wypisuje zawarto
ść
listy
{
if (last == 0) error("lista pusta");
else{
for(int j=0; j<last; j++) // dla ka
Ŝ
dego elementu...
System.out.print(list[j] + ", "); // ...wypisujemy
// jego warto
ść
System.out.println("");
}
}
//----------------------------------------------------------
public void error(String ms) // wypisuje informacje o bł
ę
dzie
{
System.out.println(ms); // ...wypisujemy
}
//----------------------------------------------------------
public long Retrieve(int p) // zwraca element z pozycji p
{
if ( (p >= last) || ( p < 0) )
{ error ("pozycja nie istnieje");
return -1; //
}
else
return list[p];
}
//----------------------------------------------------------
public int Next(int p) // zwraca nast
ę
pn
ą
pozycj
ę
po p
{
if ( (p > last-1) || ( p < 0) )
{ error ("pozycja nie istnieje");
return -1;
}
else
return p+1;
}
//----------------------------------------------------------
public int Previous(int p) // zwraca pozycj
ę
poprzedni
ą
dla p
{
if ( (p > last) || ( p < 1) )
{ error ("pozycja nie istnieje");
return -1;
}
else
return p-1;
} // koniec Previous()
} // koniec klasy listArray
Algorytmy i struktury danych - wykład 4. strona: 6
Dodajmy na koniec, Ŝe złoŜoność operacji Insert(), Delete(), Locate() oraz
PrintList() jest liniowo zaleŜna od liczby elementów listy, czyli T(n)=O(n).
NS 4.04.09
ADT: STOS
czasami nazywany kolejką LIFO (last in first out).
Jest to lista z wyróŜnionym jednym końcem, nazywanym wierzchołkiem,
na którym wykonywane są operacje:
1.
Top() -odczytuje element na stosie
2.
Pop() - usuwa element ze stosu i zwraca go
3.
Push(x) - wstawia element x na stos
oraz na ogół
4.
Create() - twórzy pusty stos
5.
isEmpty() - sprawdza czy stos jest pusty
Realizacja stosu za pomocą tablicy w Javie
class StackType{
private int maxSize; // rozmiar tablicy zawieraj
ą
cej stos
private long[] stackArray; // tablica zawieraj
ą
ca stos
private int top; // indeks szczytu stosu
//-------------------------------------------------------------
maxSize -1
a
b
c
top
0
wolne
Algorytmy i struktury danych - wykład 4. strona: 7
public StackType(int size) { // konstruktor - Create()
maxSize = size; // ustawiamy rozmiar tablicy
stackArray = new long[maxSize]; // tworzymy tablic
ę
top = -1; // na razie brak elementów
}
//-------------------------------------------------------------
public void push(long x) { / odkłada element na szczyt stosu
if(isFull()) System.out.println("stos jest pelny");
else stackArray[++top] = x; // zwi
ę
kszamy top,
// odkładamy element
}
//-------------------------------------------------------------
public long pop(){ // pobiera element ze szczytu stosu
if(isEmpty())
{ System.out.println("stos jest pusty");
return -1;
}
else return stackArray[top--]; // pobieramy element,
// zmniejszamy top
}
//-------------------------------------------------------------
public long top(){ // podgl
ą
da warto
ść
na szczycie stosu
if ( isEmpty() )
{ System.out.println("stos jest pusty");
return –1;
}
else
return stackArray[top];
}
//------------------------------------------------------------
public boolean isEmpty(){ // zwraca true, je
Ŝ
eli stos pusty
return (top == -1);
}
//-------------------------------------------------------------
public boolean isFull(){ // zwraca true, je
Ŝ
eli stos pełny
return (top == maxSize-1);
}
//------------------------------------------------------------
} // koniec klasy Stack
Algorytmy i struktury danych - wykład 4. strona: 8
Wykorzystanie stosu do odwracania słowa.
PoniŜszy program przedstawia wykorzystanie stosu do odwracania
kolejności znaków. Znaki najpierw są pobierane z wejścia i odkładane na
stosie. Następnie są zdejmowane ze stosu i wypisywane na wyjściu.
// Plik: reverse.java
import java.io.*; // operacje wej
ś
cia-wyj
ś
cia
class Stack
{
private int maxSize;
private char[] stackArray;
private int top;
//-------------------------------------------------------------
public Stack(int max) // konstruktor
{
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
//-------------------------------------------------------------
public void push(char j) // odkłada element na stos
{
stackArray[++top] = j;
}
//-------------------------------------------------------------
public char pop() // zdejmuje element ze stosu
{
return stackArray[top--];
}
//-------------------------------------------------------------
public char top() // podgl
ą
da element na szczycie stosu
{
return stackArray[top];
}
//-------------------------------------------------------------
public boolean isEmpty() // zwraca true je
Ŝ
eli stos pusty
{
return (top == -1);
}
//-------------------------------------------------------------
} // koniec klasy Stack
class Reverser
{
private String input; // napis wej
ś
ciowy
private String output; // napis wyj
ś
ciowy
//-------------------------------------------------------------
public Reverser(String in) // konstruktor
{ input = in; }
//-------------------------------------------------------------
public String doRev() // odwraca napis
Algorytmy i struktury danych - wykład 4. strona: 9
{
int stackSize = input.length(); // pobiera długo
ść
napisu
Stack theStack = new Stack(stackSize); // tworzy stos o
// takiej pojemno
ś
ci
for(int j=0; j<input.length(); j++)
{
char ch = input.charAt(j); // pobiera kolejny znak z
// wej
ś
cia...
theStack.push(ch); // ...i odkłada na stosie
}
output = "";
while( ! theStack.isEmpty() )
{
char ch = theStack.pop(); // zdejmuje znak ze stosu...
output = output + ch; // ...i doł
ą
cza do napisu
// wyj
ś
ciowego
}
return output;
} // koniec doRev()
//-------------------------------------------------------------
} // koniec klasy Reverser
class ReverseApp
{
public static void main(String[] args) throws IOException
{
String input, output;
while(true)
{
System.out.print("Wprowad
ź
napis: ");
input = getString(); // wczytujemy napis z
// klawiatury
if( input.equals("") ) // koniec, je
Ŝ
eli sam [Enter]
break;
// tworzymy obiekt
// odwracaj
ą
cy słowa
Reverser theReverser = new Reverser(input);
output = theReverser.doRev(); // u
Ŝ
ywamy go
System.out.println("Odwrócony: " + output);
} // koniec while
} // koniec main()
//-------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//-------------------------------------------------------------
} // koniec klasy ReverseApp
Algorytmy i struktury danych - wykład 4. strona: 10
ADT : KOLEJKA
czyli kolejka FIFO (first in first out).
Jest to lista, w której operacja wstawiania nowego elementu odbywa
się na jednym z góry ustalonym końcu (koniec kolejki - rear), przy czym
rear oznacza pierwszą wolną komórkę, do której będzie wstawiony nowy
element, a odczytywanie i usuwanie odbywa się na drugim końcu
(początek kolejki – front, który wskazuje pierwszy element w kolejce).
Operacje:
1.
Create() - twórzy pustą kolejkę
2.
isEmpty() - sprawdza czy kolejka pusta
3.
enQueue(x)- wstawia nowy element x
4.
Front()- odczytuje pierwszy element w kolejce
5.
deQueue() - usuwa pierwszy element w kolejce i go zwraca
Efektywna realizacja tablicowa kolejki (tablica cykliczna):
Najprostszą i nieefektywną realizacją kolejki w tablicy jest przyjęcie,
Ŝe początek kolejki front będzie zawsze równy 0, a rear będzie indeksem
do pierwszego wolnego elementu tablicy.
W tej reprezentacji operacja usuwania elementu z kolejki wymaga
kaŜdorazowo przesuwania elementów kolejki w górę.
W przypadku gdy front będzie się zwiększać o jeden podczas
operacji usuwania elementu, powstaje problem, braku miejsca przy
maxSize -1
a
b
c
rear
0
wolne
front
Algorytmy i struktury danych - wykład 4. strona: 11
wstawianiu elementu na koniec kolejki, podczas gdy będzie wolne miejsce
na początku kolejki.
PoniŜej przedstawiono kolejkę po usunięciu trzech elementów i
wstawieniu pięciu.
Najlepszym rozwiązaniem jest reprezentacja kolejki w tablicy
cyklicznej. Wstawianie i usuwanie zwiększają pozycje końca i początku o 1
modulo rozmiar tablicy.
PoniewaŜ za pomocą tylko indeksu końca i początku kolejki nie da się
odróŜnić kolejki pustej od kolejki zajmującej całą tablicę, więc nie
dopuszczamy do wypełnienia całej tablicy (operacja enQUEUE).
maxSize -1
d
e
f
g
front
0
h
wolne
rear
0
1
maxSize
-1
rear
kolejka
front
Algorytmy i struktury danych - wykład 4. strona: 12
DZ 27.03.09
class queueArray
{
private int maxSize;
private long[] queArray;
private int front; //front = indeks pocz
ą
tku
private int rear; //rear = indeks nast
ę
pny za ko
ń
cem
// czyli pierwszy wolny
//-------------------------------------------------------------
private int Addone (int i) //pomocnicza
{
return (i+1) % maxSize; // reszta z dzielenia
}
//-------------------------------------------------------------
public queueArray(int size) // konstruktor
{
maxSize = size;
queArray = new long[maxSize];
front = 0;
rear = 0;
}
//-------------------------------------------------------------
public void enQueue(long x) // wstawia element na koniec
// kolejki
{
if (isFull()) error ("queue is full");
else{
queArray[rear] = x;
rear = Addone(rear);
}
}
//-------------------------------------------------------------
public long deQueue() // usuwa element z pocz
ą
tku kolejki
{
if(isEmpty()){
front
front
rear
rear
rear
front
Pusta
Jedno-elemenetowa
Pełna
Algorytmy i struktury danych - wykład 4. strona: 13
error("queue is empty");
return -1;
}
else {
long temp = queArray[front]; // pobieramy element
front = Addone(front);
return temp;
}
}
//-------------------------------------------------------------
public long Front() // podgl
ą
da element na pocz
ą
tku kolejki
{
if(isEmpty()){
error("queue is empty");
return -1;
}
else return queArray[front];
}
//-------------------------------------------------------------
public boolean isEmpty() // zwraca true, je
Ŝ
eli kolejka
// pusta
{
return (rear == front);
}
//-------------------------------------------------------------
public boolean isFull() // zwraca true, je
Ŝ
eli kolejka
// pełna
{
return (Addone(rear) == front);
}
//-------------------------------------------------------------
public void error(String ms) // wypisuje informacje
// o bł
ę
dzie
{
System.out.println(ms); // ...wypisujemy
}
//-------------------------------------------------------------
} // koniec klasy queueArray
ZłoŜoność kaŜdej operacji na stosie lub kolejce:
Θ
(1) – stała.
Algorytmy i struktury danych - wykład 4. strona: 14
ADT: Kolejka priorytetowa
to struktura danych przechowująca zbiór elementów ustalonego typu z
następującymi operacjami:
•
Insert(x, q) – wstawienie elementu ‘x’ do kolejki q
•
Max(q) – odczyt największego elementu w kolejce (element ten jest
zwracany jako wynik operacji, kolejka się nie zmienia)
•
Delete_max (q) – usunięcie największego elementu z kolejki q
oraz operacje utworzenia nowej (pustej) kolejki i sprawdzania czy dana
kolejka jest pusta. W niektórych zastosowaniach pojawia się osobna
operacja tworzenia kolejki zawierającej zadany zbiór elementów.
Analogicznie (w zaleŜności od potrzeb) definiuje się i realizuje kolejkę
priorytetową z zamianą Max na Min.
Zastosowanie m.in. do sortowania, w algorytmach grafowych.
Realizacja kolejki priorytetowej:
najprostsza: za pomocą listy realizowanej w tablicy.
Wariant A: tablica nieuporządkowana.
Atrybuty struktury:
Size – aktualna długość kolejki
maxSize – wielkość tablicy
A[0] ... A[maxSize-1] – tablica zawierająca elementy kolejki
Inicjalizacja – tworzenie pustej kolejki: Size = 0
Wstawianie:
dopisanie elementu na koniec listy i powiększenie Size o 1
Max:
znalezienie elementu największego spośród
A[0], . . . ,A[maxSize-1]
Algorytmy i struktury danych - wykład 4. strona: 15
Delete_Max:
znalezienie połoŜenia (indeksu p) elementu największego, a
następnie przesunięcie elementów o indeksach większych niŜ p o 1
pozycję w dół oraz Size zmniejsza się o 1.
Wariant B: tablica uporządkowana rosnąco.
Zmienne – jak wyŜej.
Max: ostatni element w liście, tj. A[0], ... ,A[maxSize-1]
Delete_Max:
skrócenie listy o ostatni element, tj. Size = Size – 1
Insert(x, q):
znajdź połoŜenie elementu ‘x’ w tablicy algorytmem bisekcji;
wstaw element ‘x’ w to miejsce (z rozsunięciem);
Size = Size +1
Jako ćwiczenie oceń, które operacje w poszczególnych wariantach
realizacji kolejki priorytetowej są wykonywane szybko a które wolniej ?
Kolejki dwustronne (deque)
Kolejka dwustronna pozwala wstawiać i usuwać elementy zarówno z
początku, jak i z końca kolejki.
Posiada, zatem operacje:
•
InsertLeft() – wstaw z lewej strony
•
InsertRight()-wstaw z prawej strony
•
RemoveLeft()- usuń z lewej strony
•
RemoveRight()- usuń z prawej strony
Kolejka dwustronna jest bardziej uniwersalną strukturą danych niŜ stosy i
zwykłe kolejki.
Algorytmy i struktury danych - wykład 4. strona: 16
Zastosowanie stosu
Bardzo interesującym algorytmem, który w istotny sposób korzysta z
właściwości stosu jest algorytm przekształcenia wyraŜenia arytmetycznego
z postaci infiksowej (zwykłej) do postaci ONP.
Przypomnijmy algorytm.
Wejście: input - wyraŜenie w postaci zwykłej
Wyjście: output - wyraŜenie w ONP
Pomocniczo: stos
Infix_To_Onp(){ // przekształca wyraŜenie z input do output
DO {
wez_kolejny_element_z_wejścia;
IF ( element_jest_operandem )
dopisz_element_na_wyjscie ;
ELSE // element jest operatorem lub nawiasem
IF
(
element_jest_operatorem ) {
WHILE ( nie_pusty_stos && prior_operatora_na_stosie >= prior_elementu )
przepisz_operator_ze_stosu_na_wyjscie ;
wstaw_element_na_stos;
}
ELSE
IF ( element = ‘(‘ ) wstaw_element_na_stos;
ELSE
IF ( element = ‘)’ ) // przepisuj ze stosu do output aŜ do '('
WHILE ( na_stosie_operator )
przepisz_operator_ze_stosu_na_wyjscie ;
wyrzuc_ze_stosu_( ; // zapomnij o ')'
WHILE ( ! koniec_danych);
WHILE ( niepusty_stos )
przepisz_operator_ze_stosu_na_wyjscie ;
}
PoniŜej plik: infix.java prezentuje realizację tego algorytmu w Javie.
// infix.java
Algorytmy i struktury danych - wykład 4. strona: 17
// przekształca wyra
Ŝ
enia infiksowe na ONP
//--------------------------------------------------------------
import java.io.*; // operacje wejscia-wyjscia
class StackX // klasa stosu
{
private int maxSize;
private char[] stackArray;
private int top;
//--------------------------------------------------------------
public StackX(int s) // konstruktor
{
maxSize = s;
stackArray = new char[maxSize];
top = -1;
}
//--------------------------------------------------------------
public void push(char ch) // odkłada znak na stosie
{ stackArray[++top] = ch;
displayStack("stos: "); // *diagnostyka*
}
//--------------------------------------------------------------
public char pop() // zdejmuje znak ze stosu
{ char ch = stackArray[top--];
displayStack("stos: "); // *diagnostyka*
return ch;
}
//--------------------------------------------------------------
public char top() // podglada znak na szczycie stosu
{ return stackArray[top]; }
//--------------------------------------------------------------
public boolean isEmpty() // zwraca true, je
Ŝ
eli stos pusty
{ return (top == -1); }
//-------------------------------------------------------------
public int size() // zwraca ilosc elementów na stosie
{ return top+1; }
//--------------------------------------------------------------
public void displayStack(String s)
{
System.out.print(s);
for(int j=0; j<size(); j++)
{
System.out.print(stackArray[j]);
System.out.print(' ');
}
System.out.println("");
}
//--------------------------------------------------------------
} // koniec klasy StackX
class InToONP // przekształca do ONP
{
private StackX theStack;
private String input;
private String output = "";
//--------------------------------------------------------------
public InToONP(String in) // konstruktor
{
input = in;
int stackSize = input.length();
theStack = new StackX(stackSize);
}
//--------------------------------------------------------------
public String doONP() // wykonuje przekształcenie
{
Algorytmy i struktury danych - wykład 4. strona: 18
for(int j=0; j<input.length(); j++) // dla ka
Ŝ
dego znaku...
{
char ch = input.charAt(j); // ...pobieramy go z wejscia
switch(ch)
{
case '+': // + albo -
case '-':
gotOper(ch, 1); // zdejmujemy operatory o priorytecie
// wi
ę
kszym ni
Ŝ
1
break;
case '*': // * albo /
case '/':
gotOper(ch, 2); // zdejmujemy operatory o priorytecie
// wi
ę
kszym ni
Ŝ
2
break;
case '(': // nawias otwierajacy...
theStack.push(ch); // ...odkładamy na stosie
break;
case ')': // nawias zamykajšcy...
gotParen(ch); // zdejmujemy operatory
break;
default: // argument...
output = output + ch; // ...kopiujemy na wyjscie
break;
} // koniec switch
} // koniec for
while( !theStack.isEmpty() ) // zdejmujemy pozostałe na stosie
// operatory...
{
output = output + theStack.pop(); // ...i kopiujemy na wyjscie
}
theStack.displayStack("stos: empty "); // *diagnostyka*
return output; // zwracamy wyra
Ŝ
enie przyrostkowe
} // koniec doONP()
//--------------------------------------------------------------
public void gotOper(char opThis, int prec1)
{ // pobrano operator z wejscia
while( !theStack.isEmpty() )
{
char opTop = theStack.pop();
if( opTop == '(' ) // je
Ŝ
eli to '('
{
theStack.push(opTop); // odkładamy '('
break;
}
else // to operator
{
int prec2; // priorytet zdj
ę
tego operatora
if(opTop=='+' || opTop=='-') // okreslamy priorytet zdj
ę
tego
// operatora
prec2 = 1;
else
prec2 = 2;
if(prec2 < prec1) // je
Ŝ
eli priorytet zdj
ę
tego mniejszy...
{ // ...ni
Ŝ
wczytanego z wejscia
theStack.push(opTop); // odkładamy na stosie zdj
ę
ty operator
break;
}
else // priorytet zdj
ę
tego operatora...
output = output + opTop; // ...nie mniejszy ni
Ŝ
wczytanego
} // koniec else (to operator)
} // koniec while
theStack.push(opThis); // odkładamy nowy operator na stosie
Algorytmy i struktury danych - wykład 4. strona: 19
} // koniec gotOper()
//--------------------------------------------------------------
public void gotParen(char ch)
{ // wczytano nawias zamykajacy
while( !theStack.isEmpty() )
{
char chx = theStack.pop(); // chx - symbol na wierzcholku stosu
if( chx == '(' ) // je
Ŝ
eli zdj
ę
to '('...
break; // ...koniec p
ę
tli
else // je
Ŝ
eli to operator...
output = output + chx; // ...kopiujemy go na wyjscie
} // koniec while
} // koniec gotParen()
//--------------------------------------------------------------
} // end class Infix_To_ONP
class InfixApp
{
public static void main(String[] args) throws IOException
{
String input, output;
while(true)
{
System.out.print("Wprowadz wyrazenie: ");
System.out.flush();
input = getString(); // wczytujemy napis z klawiatury
if( input.equals("") ) // koniec je
Ŝ
eli sam [Enter]
break;
// tworzymy obiekt tłumaczacy
InToONP theONP = new InToONP(input);
output = theONP.doONP(); // wykonujemy tłumaczenie
System.out.println("ONP: " + output + '\n');
} // koniec while
} // koniec main()
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
} // koniec klasy InfixApp