Odwrotna notacja polska – przypomnienie

Odwrotna notacja polska (ONP) jest rodzajem notacji arytmetycznej, w której operator znajduje się za argumentami, czyli w innym miejscu niż w przypadku zapisu infiksowegozapis infiksowyzapisu infiksowego.

Obliczanie wartości wyrażenia zapisanego w odwrotnej notacji polskiej jest dla nas trudniejsze, niż gdy mamy do czynienia z klasyczną notacją arytmetyczną. A jednak dla komputera zapis ten jest o wiele bardziej „zrozumiały”. Algorytm wykorzystywany podczas obliczeń opiera się na strukturze danych zwanej stosem. Każdy nowy wpis jest układany na szczycie stosu – jeżeli chcemy pobrać z niego dane, muszą to być te, które zostały w nim zapisane ostatnio.

Implementacja algorytmu jest prosta: pobieramy kolejne elementy wyrażenia; jeżeli analizowany element jest liczbą, to umieszczamy go na stosie, a jeżeli operatorem – zdejmujemy ze stosu dwa ostatnio ułożone na nim elementy, wykonujemy na nich operację wskazaną przez operatora, a otrzymany wynik umieszczamy na stosie. Gdy zakończymy przetwarzanie elementów, na stosie powinna znajdować się tylko jedna liczba i jest nią wynik wyrażenia.

Przykładowe zadanie maturalne

Zadanie 1

Treść zadania:

Dla przetwarzania przez komputer wygodnym sposobem zapisu wyrażeń arytmetycznych jest tzw. odwrotna notacja polska (ONP). Zapis w ONP wyrażenia W nazywamy postacią ONP i oznaczamy ją ONP(W). W ONP operator (dodawania, odejmowania, mnożenia, dzielenia) umieszczamy za jego argumentami, np. 2 + 5 zapisujemy jako 2 5 +. Dokładniej, postać ONP dla wyrażenia definiujemy rekurencyjnie w następujący sposób:

1. jeżeli W jest liczbą, to jego postać ONP jest równa W;

2. jeżeli W ma postać WIndeks dolny 1₁ op WIndeks dolny 2₂, gdzie op jest operatorem, a WIndeks dolny 1₁ i WIndeks dolny 2₂ wyrażeniami, to

ONP(W) jest równe ONP(WIndeks dolny 1₁) ONP(WIndeks dolny 2₂) op.

Postać ONP wyrażeń, choć dla ludzi mało czytelna, ma własności bardzo przydatne dla analizy komputerowej. W ONP nie są potrzebne nawiasy, a do wyznaczania wartości wyrażenia można zastosować prosty algorytm podany poniżej.

Specyfikacja

Dane:

n — liczba całkowita dodatnia,
X = X[1...n] — wyrażenie w ONP, gdzie X[i] dla 1 ≤ i ≤ n jest liczbą lub znakiem ze zbioru {+, –, *}.

Wynik:

wartość wyrażenia X.

Algorytm:

k ← 1
dla i = 1, 2, ..., n wykonuj
	jeżeli X[i] jest liczbą 
		T[k] ← X[i]
        
	jeżeli X[i] ∈ {+, –, *} 
		b ← T[k – 1]
		a ← T[k – 2]
		k ← k – 2 
        
		jeżeli X[i] = '+'
			T[k] ← a + b
		jeżeli X[i] = '–'
			T[k] ← a – b
		jeżeli X[i] = '*'
			T[k] ← a * b
            
	k ← k + 1
    
zwróć T[1]

Prześledź działanie podanego algorytmu dla wyrażenia X = 9 7 + 3 * 5 4 - 2 * -, czyli dla n = 11 oraz następujących wartości X[1], ..., X[11]:

Uzupełnij poniższą tabelę:

Zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i pojawiło się w zbiorze zadań z informatyki, jako Zadanie 11.2 (wiązka zadań  „Odwrotna notacja polska”) . Cały zbiór można znaleźć na oficjalnej stronie internetowej CKE.

Przykładowe rozwiązanie:

Algorytm do znajdowania wartości wyrażenia zapisanego w ONP jest dość prosty. Aby go zaimplementować, będziemy potrzebować stosu. Stos możemy utworzyć, korzystając ze zwykłej tablicy statycznejtablica statycznatablicy statycznej oraz jednej zmiennej.

Tworząc tablicę statyczną, która posłuży nam jako stos, nadajemy jej większy – niż potrzebny – rozmiar, żeby zabezpieczyć się przed brakiem miejsca na działania. Zmienna będzie przechowywać pierwszy wolny indeks w stosie. Inicjowany stos jest pusty, zatem zmienna ta otrzyma na początku wartość 0.

stos[] = tablica o rozmiarze 30
pierwszyWolnyIndeks = 0

Następnie odczytujemy kolejne elementy wyrażenia. Jeżeli element jest liczbą, umieszczamy go na stosie.

stos[] = tablica o rozmiarze 30
pierwszyWolnyIndeks = 0

dla element z wyrażenia wykonuj:
	jeżeli element jest liczbą wykonaj:
		stos[pierwszyWolnyIndeks] = element
		pierwszyWolnyIndeks += 1

Jeżeli element jest operatorem, zdejmujemy ze stosu dwa elementy, wykonujemy na nich operację, a jej wynik umieszczamy na stosie.

stos[] = tablica o rozmiarze 30
pierwszyWolnyIndeks = 0

dla element z wyrażenia wykonuj:
	jeżeli element jest liczbą wykonaj:
		stos[pierwszyWolnyIndeks] = element
		pierwszyWolnyIndeks += 1
  
	jeżeli element jest operatorem wykonaj:
		wynik = stos[pierwszyWolnyIndeks - 1] operator stos[pierwszyWolnyIndeks - 2]
		stos[pierwszyWolnyIndeks - 2] = wynik
		pierwszyWolnyIndeks -= 1

Po zakończeniu działania jedyny element, jaki pozostanie na stosie, jest wartością wyrażenia.

stos[] = tablica o rozmiarze 30
pierwszyWolnyIndeks = 0

dla element z wyrażenia wykonuj:
	jeżeli element jest liczbą wykonaj:
		stos[pierwszyWolnyIndeks] = element
		pierwszyWolnyIndeks += 1
  
	jeżeli element jest operatorem wykonaj:
		wynik = stos[pierwszyWolnyIndeks - 1] operator stos[pierwszyWolnyIndeks - 2]
		stos[pierwszyWolnyIndeks - 2] = wynik
		pierwszyWolnyIndeks -= 1
    
wypisz stos[0]

Opierając się na tym algorytmie, zaimplementuj program w wybranym języku programowania, a następnie wypełnij tabelkę z zadania.

Schemat oceniania:

Schemat oceniania pochodzi ze zbioru zadań maturalnych z informatyki opracowanych przez CKE. Cały zbiór można znaleźć na oficjalnej stronie internetowej CKE.

Słownik