Laboratorium 6 - Kalkulator RPN

Zakres materiału

Zmienne dynamiczne, wskaźniki, dynamiczne struktury danych. Listy liniowe: budowa, operacje na listach. Stos: implementacja na liście.

Przygotowanie do zajęć

Przed przystąpieniem do zajęć:

• Przygotuj funkcje push(stos, element), pop(stos, element), które odpowiednio pozwalają na umieszczenie na stosie stos i zdjęcie z niego elementu +eleme, który jest liczbą całkowitą, oraz funkcje empty(stos), print(stos), które pozwalają na uzyskanie informacji, czy stos jest pusty oraz wyświetlenie na standardowym wyjściu elementów znajdujących się na nim. Do tego dodaj funkcję inicjuj(stos), która w poprawny sposób zainicjuje pusty stos.

  Stos powinien zostać zrealizowany z wykorzystaniem dynamicznej listy jednokierunkowej. Wszystkie funkcje z wyjątkiem funkcji print, która ma charakter pomocniczy, będą operowały jedynie na początku listy. Opcjonalnie, w zastępstwie funkcji empty można dostarczyć zmodyfikowaną funkcję pop, której zwracana wartość będzie informowała o tym, czy stos jest pusty czy nie.

  Przetestuj funkcjonowanie przygotowanego stosu w serii próbnych wywołań w rodzaju (użyj gdzie trzeba operatora referencji/dereferencji):

    init(stos);
    arg = 7;
    push(stos, arg);
    arg = 14;
    push(stos, arg);
    print(stos);
    arg = 7;
    pop(stos, arg);
    print(stos);
    printf("Zdjeta wartosc:%d\n",arg);
  

• Zaproponuj algorytm działania następującego programu:
  
  Zadaniem programu jest realizacja funkcji czterodziałaniowego kalkulatora operującego w tzw. odwrotnej notacji polskiej RPN (ang. reverse polish notation). W systemie tym pracują niektóre kalkulatory podręczne, np. kalkulatory firmy Hewlett-Packard.

  Program ma działać na liczbach całkowitych, czytając dane wejściowe ze standardowego wejścia. W strumieniu wejściowym będą mogły pojawić się liczby oraz symbole operacji w postaci znaków: +, -, *, i / (dzielenie całkowitoliczbowe). Za każdym razem, gdy na wejściu pojawi się liczba, zostaje ona umieszczona na początku listy argumentów. Gdy pojawi się symbol operacji, zostaje wykonane odpowiednie działanie na dwóch liczbach pobranych z początku listy, z sygnalizacją błędu, gdyby na liście były mniej niż dwie liczby. Wynik działania zostaje umieszczony na początku listy argumentów. Tak używane listy nazywane są stosami albo strukturami LIFO (ang. last-in-first-out, czyli „ostatni wchodzi, pierwszy wychodzi''). Mówimy o umieszczaniu danych na stosie (szczycie stosu) i zdejmowaniu ze stosu.

  Jakkolwiek powyższy schemat daje pełny kalkulator czterodziałaniowy, w omawianym programie powinno znaleźć się jeszcze kilka operacji dla ułatwienia posługiwania się kalkulatorem. Wprowadźmy dodatkowy symbol operacji P, który będzie służył usunięciu ostatnio wprowadzonej liczby i odpowiadał operacji pop, to znaczy usuwaniu argumentu ze szczytu stosu, oraz symbol operacji c (clear), który będzie „czyścił stos'', to znaczy usuwał z niego wszystkie elementy (takie operatory mogą być przydatne dla korekcji błędów popełnionych przy wpisywaniu danych). Kolejnym, dodatkowym operatorem będzie r (reverse) i powinien on spowodować zamianę miejscami dwóch argumentów na szczycie stosu. Dalej, podanie znaku d (duplicate) ma spowodować zduplikowanie argumentu znajdującego się na szczycie stosu. Następnym użytym symbolem będzie p (print) i jeśli pojawi się w strumieniu wejściowym, powinien spowodować wydrukowanie szczytu stosu oraz f (full print), którego pojawienie się spowoduje wydrukowanie zawartości całego stosu argumentów. Ostatni symbol, znak q będzie służył zakończeniu pracy programu.

  Opisaną powyżej funkcjonalność zapewnia standardowy program uniksowy dc, będący kalkulatorem działającym w oparciu o odwrotną notację polską. Przetestuj jego działanie. Więcej szczegółów: man dc.

• Materiały dołączone do zadania zawierają trzy pliki (czytaj1.c, czytaj2.c i czytaj3.c) z propozycjami sposobu realizacji interfejsu użytkownika rozpatrywanego programu, w zakresie rozróżniania wczytywanych argumentów (liczb) od danych nieliczbowych (operatorów). Przeanalizuj i przetestuj zaproponowane schematy postępowania, oceń ich przydatność przy rozwiązywaniu postawionego zadania (odróżnianie klas liczba/operator/pozostałe, umożliwienie wczytywania liczb ze znakiem).

Zadania do wykonania

• Napisać program pozwalający na rozwiązanie postawionego powyżej zadania z zastosowaniem odpowiedniego podziału na moduły. Nie zapomnieć o wprowadzaniu do pliku komentarzy równocześnie z wprowadzaniem do niego kodu programu.
• Uruchomić i przetestować program dla różnych wartości danych wejściowych.
• Wyposażyć plik z kodem źródłowym w dokumentację, która oprócz wprowadzanych wcześniej komentarzy powinna zawierać dane o autorze, dacie utworzenia programu, jego wersji, modyfikacjach itp., krótką charakterystykę programu, specyfikację danych wejściowych i wyjściowych, opis sposobu korzystania z programu.

Zadania dodatkowe (dla chętnych)

• Skonstruować funkcje do obsługi stosu na bazie tablicy jednowymiarowej, zastąpić nimi wcześniej opracowane funkcje (zamiana nie powinna pociągać za sobą konieczności dokonania jakichkolwiek zmian w pozostałej części programu, poza ewentualną wymianą pliku nagłówkowego).
• Wyposażyć kalkulator w dodatkowe funkcje matematyczne.
• Wyposażyć kalkulator w pamięć w postaci drugiego stosu, na którym na żądanie będą zapamiętywane wskazane wyniki, czy też rejestry pamięciowe, jak to ma miejsce w programie dc.

Sprawozdanie

Sprawozdanie powinno zawierać:

• Imię i nazwisko autora, temat ćwiczenia, datę wykonania;
• Kod źródłowy programu;
• Testy programu (opis przebiegu z wynikami) w tym kolejno:
  • Co dany test ma na celu;
  • Metoda testowania - dane wejściowe;
  • Dane wyjściowe zwrócone w teście przez program;
  • Rezultat testu - ocena uzupełniona ewentualnym komentarzem;
• Wnioski końcowe.

Pytania kontrolne

1. Jakie są zalety odwrotnej notacji polskiej w stosunku do tradycyjnego zapisu działań arytmetycznych.
2. Zapisz w postaci RPN następujące działanie: (2+4*5)/(1+7).
3. Jakie operacje i w jakiej kolejności należy wykonać, by odłożyć element na stos, a jakie by go usunąć?
4. W jaki sposób można zaimplementować stos?
5. Wskaż różnice w implementacji stosu na bazie listy i na bazie tablicy.
6. Opisz wykonanie operacji dodania dwóch liczb w kontekście operowania na stosie służącym do przechowywania argumentów.
7. Jakie błędy mogą wystąpić w czasie działania programu?

About this document ...

This document was generated using the LaTeX2HTML translator Version 2008 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -html_version 3.2,latin2,unicode -split 0 -no_navigation PProg_lab_06

The translation was initiated by Robert Muszyński on 2021-02-06