W dzisiejszym wpisie, przedstawię sposoby na wykorzystanie implementacji stosu do zmiany zapisu liczb z dziesiętnych na dwójkowy oraz na sprawdzanie poprawności zapisu nawiasów. Użyję klasę Stack, którą przedstawiłem, w poprzednim poście.
Dla przypomnienia, oto klasa stack:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
function Stack() { this.data = []; this.top = 0; } Stack.prototype.add = function(element){ this.data[this.top++] = element; } Stack.prototype.remove = function(){ return this.data[--this.top]; } Stack.prototype.view = function(){ return this.data[this.top-1]; } Stack.prototype.size = function(){ return this.top; } Stack.prototype.reset = function(){ this.top = 0; this.data.length = 0; } Stack.prototype.isEmpty = function(){ return this.top == 0; } |
Zamiana zapisu liczb z systemu dziesiętnego na dwójkowy
Nie jest żadną tajemnicą, że system binarny, jest w informatyce bardzo ważny. Jest to język, w którym komunikujemy się z komputerem. Na najbardziej bazowym poziomie, jedyne co nasza maszyna rozumie, to 0 lub 1 – napięcie lub jego brak. Dlatego sposób, na tłumaczenie liczb z systemu ludzkiego (dziesiętnego) na komputerowy (binarny) jest bardzo przydatny 🙂
Algorytm na zamianę systemu liczb z dziesiętnego na dwójkowy jest dość prosty. Liczbę dziesiętną dzielimy przez dwa i zapisujemy resztę. Powtarzamy ten proces, dopóki liczba dziesiętna będzie równa zero. Następnie, zapisane reszty czytamy od tyłu. W ten sposób powstaje nam liczba w systemie binarnym!
przykład:
23/2 = 11, reszta 1
11/2 = 5, reszta 1
5/2 = 2 reszta 1
2/2 = 1 reszta 0
1/2 = 0 reszta 1
wynik: 10111
Myślę, że gołym okiem widać już możliwość wykorzystania tutaj stosu! Napiszę skrypt który, będzie wykonywał operację dzielenia z resztą. Reszta trafi na stos, a operacja powtórzy się dopóki wprowadzona liczba będzie równa 0. Na koniec zdejmiemy liczby ze stosu (stos to FIFO, wiec liczby będą ściągane „od końca”) i tak otrzymamy wynik!
Oto funkcja, która robi to o czym piszę powyżej:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
function binTransformator(decNum) { var binStack = new Stack; result = []; while(decNum != 0){ binStack.add(decNum%2); decNum = Math.floor(decNum / 2); } while(!(binStack.isEmpty())){ result.push(binStack.remove()); } return(result.join("")); } |
teraz wystarczy stworzyć zmienną, do której przypiszemy to co zwraca funkcja. Na koniec sprawdzamy w konsoli czy wszystko się zgadza.
|
1 2 |
var binaryResult = binTransformator(34892479); console.log(binaryResult); |
Funkcja ta nie jest idealna. Należało by sprawdzić czy na pewno wartość przekazywana jest liczbą. Ponadto obsługuje, jedynie dodatnie liczby całkowite. Jednak pomimo tych ograniczeń idealnie ilustruje wykorzystanie implementacji stosu, a o to mi tu głównie chodziło. Przejdźmy do drugiego przykładu.
sprawdzanie poprawności zapisu nawiasów
Kolejnym moim przykładem na wykorzystanie implementacji stosu, będzie sprawdzenie poprawności zapisu nawiasów. Chodzi tu o dokładnie o potwierdzenie, czy wszystkie nawiasy zostały zamknięte, tak jak powinny. Można łatwo wyobrazić sobie potrzebę takiej funkcji w kompilatorze języka programowania. Od nawiasów, niedaleko też do parsowania języków markupowych takich jak XML.
Jak się za to zabrać, i w czym pomoże nam tutaj stos? Przyjrzyjmy się zapisom paru nawiasów:
(())()(()(()));
(())(()(()()));
(())()(());
Podane powyżej są poprawne. Dla każdego otwartego znaku ‚(‚ musi znaleźć się zamykający nawias znak ‚)’. Oczywiście nie wystarczy policzyć ilości jednych i drugich, ponieważ, nie zawsze będzie oznaczać to poprawny zapis. Na przykład:
()())(();
To nie jest poprawny zapis pomimo, że liczba otwierających i zamykających nawias znaków zgadza się.
Za każdy otwarty nawias, musimy sprawdzić najbliższy zamykający go znak. Z pomocą przychodzi nam stos. Zerknijmy na rozwiązującą ten problem funkcję:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function checkParenthesis(parString) { var parenStack = new Stack; for(var i=0;i<parString.length;i++){ if(parString[i] === '(') { parenStack.add("otwarty"); } else if(parString[i] === ')'){ if(parenStack.isEmpty()){ return false } else { parenStack.remove(); } } } if(parenStack.isEmpty()){ return true; } else { return false; } } |
Przekazuję funkcji ciąg nawiasów. Następnie przechodzę przez każdy znak. Jeżeli znak jest znakiem otwierającym nawias, dodaje do stosu element. Jeżeli znak jest znakiem zamykającym nawias usuwam element. Musimy też sprawdzić, czy jest co usuwać. Jeżeli funkcja trafi na znak zamykający nawias, a stos jest pusty oznacza to, że mamy znak zamykający nawias, który nie został otwarty. To oznacza, że zapis jest błędny i funkcja zwraca false.
Jeżeli funkcja dojdzie do końca ciągu znaków i stos będzie pusty, oznacza to, że wszystkie nawiasy zostały zamknięte i zwracane jest true. Jeżeli stos nie jest pusty, oznacza to, że jakiś nawias nie został zamknięty. zwracane jest false.
Sprawdźmy jeszcze czy działa poprawnie:
|
1 2 3 4 |
console.log(checkParenthesis("(())()(()(()))")); //zwraca true console.log(checkParenthesis("()())(()") //zwraca false |
Wszystko funkcjonuje jak należy.