Zadanie 1

Odwrotna notacja polskaodwrotna notacja polskaOdwrotna notacja polska (ONP) jest zapisem wyrażeń arytmetycznych łatwo przetwarzanym przez komputer. Zapis w ONP wyrażenia W nazywamy postacią ONP i oznaczamy ją ONP(W). Operator (dodawania, odejmowania, mnożenia, dzielenia) umieszczamy za jego argumentami, np. 2 + 5 zapisujemy jako 2 5 +. 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 11 op WIndeks dolny 22, gdzie op jest operatorem, a WIndeks dolny 11 oraz WIndeks dolny 22 wyrażeniami, to ONP(W) jest równe ONP(WIndeks dolny 11) ONP(WIndeks dolny 22) op.

Przykład:

Zauważmy, że dla W = (1 + 2) + (3 * (5 – 7)) wartość ONP(W) uzyskujemy z połączenia ONP(1 + 2) = 1 2 +, ONP(3 * (5 – 7)) = 357 – * oraz znaku dodawania +.

Przedstawiony algorytm sprawdza, czy podany na wejściu ciąg liczb i operatorów jest poprawnym wyrażeniem w ONP.

Specyfikacja problemu:

Dane:

• n – liczba całkowita dodatnia

• X[1..n] – ciąg elementów o długości n, z których każdy jest liczbą lub znakiem ze zbioru {+, –, *}

Wynik:

• Tak – jeśli X jest poprawnym wyrażeniem w ONP

• Nie – w przeciwnym przypadku

Algorytm:

licznik ← 0
dla i = 1, 2, ..., n wykonuj:
	jeżeli X[i] jest cyfrą wykonaj:
		licznik ← licznik + 1
        
	jeżeli X[i] należy do zbioru {+, –, *} wykonaj:
		jeżeli licznik < 2 wykonaj:
			zwróć "Nie" i zakończ działanie
		w przeciwnym razie wykonaj:
			licznik ← licznik – 1
            
jeżeli licznik != 1 wykonaj:
	zwróć "Nie"
w przeciwnym razie wykonaj:
	zwróć "Tak"

Oceń, które z podanych napisów są wyrażeniami zapisanymi poprawnie w ONP, wpisując słowa TAK lub NIE w trzeciej kolumnie przedstawionej tabeli. W drugiej kolumnie podaj wartości zmiennej licznik po zakończeniu działania algorytmu dla poszczególnych napisów.

Rozwiązanie

Jak wiemy, każde wyrażenie poprawnie zapisane w ONP, po zakończeniu obliczeń pozostawia na stosie tylko jedną wartość. Jest nią wynik działania.

Z każdą kolejną analizowaną liczbą na stosie wzrasta o jeden liczba danych, ponieważ napotkaną liczbę wrzucamy na stos. Jeżeli napotykamy operator, to zdejmujemy dwie liczby ze stosu i wykonujemy na nich operację wskazaną przez operator. Następnie wynik odkładamy z powrotem na stos. W rezultacie liczba elementów na stosie maleje o 1.

Zanim uznamy zapis za poprawny, upewniamy się, że zawsze gdy w wyrażeniu napotykamy operator, na stosie znajdują się co najmniej dwa elementy.

Przeanalizujmy podany w zadaniu algorytm dla ciągów znaków z tabeli.

Pierwszy napis to 1 2 + *. Pierwsze dwa jego znaki są cyframi, a zatem po pierwszych dwóch iteracjach głównej pętli algorytmu zmienna licznik będzie równa 2. Kolejny znak to +. Nie jest on cyfrą, więc zmniejszamy zmienną licznik o 1. Zmienna licznik zawiera obecnie wartość 1.

Gdyby napis kończył się w tym miejscu, byłby on poprawnym wyrażeniem w ONP. Jednakże mamy jeszcze jeden znak, który nie jest cyfrą, więc ponownie zmniejszamy wartość zmiennej licznik o 1. Jednak w 7. linii algorytmu znajduje się instrukcja warunkowa, która w tym przypadku kończy algorytm wcześniej i zwraca wartość Nie.

Przejdźmy do analizy drugiego napisu, czyli 1 2 + 3 4 - 5 * 7 8 + 9. Po pierwszych dwóch iteracjach wartość licznika będzie równa 2. Następnie mamy znak +, więc zmienna licznik będzie wynosić 1. Następnie kolejne dwie cyfry zwiększą ją o 2 – w tym momencie zmienna licznik ma wartość 3. Podążając dalej zgodnie z algorytmem, na końcu otrzymamy zmienną licznik wynoszącą 4. Ponownie po zakończeniu działania algorytmu na stosie zostaje nam inna liczba elementów niż 1, więc to wyrażenie również nie jest poprawne w ONP.

Kolejny napis to 1 2 3 4 5 + + + +. Pięć pierwszych znaków to cyfry, zatem po pięciu pierwszych iteracjach zmienna licznik wynosi 5. Kolejne cztery znaki nie są cyframi, więc po kolejnych czterech iteracjach wartość zmiennej licznik wynosi 1. Jest to już koniec napisu, więc algorytm zakończył swoje działanie i wartość zmiennej licznik wynosi 1. Analizowany napis jest zatem poprawnym wyrażeniem w ONP.

Przejdźmy do kolejnego napisu. Tym razem wygląda następująco: 1 2 3 4 5 + + + + + +. Jest bardzo podobny do poprzedniego, stąd wiemy już, że po pierwszych dziewięciu iteracjach głównej pętli zmienna licznik wynosi 1. W tym przypadku jednak nie jest to jeszcze koniec napisu. Dziesiąty analizowany znak nie jest cyfrą, więc zmienna licznik powinna wynosić 0. Nie dojdzie jednak do tego z powodu instrukcji warunkowej z 7. linii algorytmu. Sprawia ona, że działanie algorytmu kończy się wcześniej. Wiemy też, że wyrażenie nie jest poprawnym wyrażeniem w ONP.

Zostały cztery napisy, w których nie czekają nas już żadne niespodzianki, możemy więc uzupełnić tabelę do końca. Poprawnie wypełniona tabela wygląda następująco:

Schemat oceniania

• 2 pkt – za poprawną odpowiedź we wszystkich wierszach,

• 1 pkt – za poprawną odpowiedź w co najmniej czterech wierszach,

• 0 pkt – za podanie poprawnej odpowiedzi w mniej niż czterech wierszach lub brak odpowiedzi.

Klucz oceniania pochodzi ze zbioru zadań maturalnych z informatyki, opracowanego przez Centralną Komisję Egzaminacyjną. Schemat został ułożony na podstawie podobnych zadań maturalnych. Cały zbiór można znaleźć na oficjalnej stronie internetowej CKE.

Słownik