Implementacja algorytmu
Implementacja algorytmu w języku Python
Znamy już algorytm obliczania wartości wyrażenia zapisanego w ONP, możemy więc teraz zaimplementować go w języku programowania. Do implementacji stosu wykorzystamy tablicę. Najpierw jednak zwróćmy uwagę na kilka faktów.
Tablice w języku Python są dynamiczne - nie musimy określać ich rozmiaru. Aby w języku Python umieścić element na końcu tablicy (szczycie stosu), korzystamy z metody append(). Przydatna okaże się również metoda pop(), która zwraca ostatni element tablicy (stosu) i jednocześnie go z niej usuwa.
Zapoznaj się z prezentacją omawiającą kolejne kroki implementacji algorytmu.
Napisz program, który obliczy wartość wyrażenia zapisanego w odwrotnej notacji polskiej.
Przetestuj działanie programu dla wyrażenia: 5 4 + 2 * 5 + 1 -
Specyfikacja problemu:
Dane:
wyrazenie– wyrażenie zapisane w odwrotnej notacji polskiej; ciąg znaków składający się wyłącznie z liczb naturalnych jednocyfrowych, spacji oraz następujących operatorów arytmetycznych:+, -, *, /
Wynik:
obliczona wartość wyrażenia
wyrazenie
Przykładowe wyjście dla podanych danych:
Podsumowanie
Implementacja obliczania wartości wyrażenia zapisanego w odwrotnej notacji polskiej opiera się na strukturze danych zwanej stosem. Strukturę tę możemy sobie wyobrazić jako elementy ułożone jeden na drugim (podobnie jak stos książek). Aby dodać element do stosu, należy umieścić go na górze. Gdy chcemy dostać się do któregokolwiek elementu położonego niżej, trzeba zdjąć po kolei wszystkie elementy znajdujące się nad nim. Innymi słowy, ostatni element dodany do stosu będzie z niego zdjęty jako pierwszy.
Należy pamiętać, że w przypadku odwrotnej notacji polskiej kolejność wykonywania działań zależy wyłącznie od tego, w jakiej kolejności znajdują się operandy i operatory, natomiast bez znaczenia jest priorytet operatorów - z tego powodu w ONP nie stosuje się nawiasów.
Słownik
dynamiczna struktura danych typu LIFO (ang. Last In, First Out); element dodany do stosu jako ostatni jest pierwszym, który może być z niego zdjęty (elementy stosu dodawane są tak samo, jak układa się np. stos książek)