[C] Kalkulator liczb rzeczywistych

Odpowiedz Nowy wątek
2009-12-14 23:35
0

Witam!

Na zaliczenie podstaw programowania dostałem do napisania następujący program:

"Napisać kalkulator liczb rzeczywistych:

  1. wczytywanie do 20 znaków w postaci działań i liczb
  2. zachowanie kolejności działań
  3. obsługa +,-,*,/,^
  4. zgłaszanie błędów"

Chodzi o to, aby kalkulator potrafił policzyć np. coś takiego:

2*4-(2.1+8)^(3-2)/18

zachowując naturalną kolejność działań, tj: nawiasy, potęgowanie, mnożenie/dzielenie, dodawanie/odejmowanie.
Ma być przy tym odporny na błędy typu dzielenie przez zero, zapisy rozpoczynające lub kończące się działaniami, itp.

Na początku trzeba zająć się przygotowaniem łańcucha znaków podanego przez użytkownika. Na dobry początek napisałem coś takiego:

#include <stdio.h>
#include <ctype.h>
#define MAX_DLUGOSC_WYRAZENIA 20
char* analizuj_wyrazenie(void);

int main()
{
  printf("%s\n", analizuj_wyrazenie()); //dla testu funkcji analizuj_wyrazenie
  system("PAUSE");    
  return 0;
}

char* analizuj_wyrazenie(void)
{
      int wyrazenie_poprawne=0;
      int blad_skladni;
      int wczytane_znaki;
      int indeks_tablicy;
      char znak_tymczasowy;
      static char zapis_ifiksowy[MAX_DLUGOSC_WYRAZENIA];

      while(wyrazenie_poprawne!=1)
      {
         blad_skladni=0;
         wczytane_znaki=0;
         indeks_tablicy=0;
         wyrazenie_poprawne=1;

         printf("Wprowadz wyrazenie, ktore chcesz obliczyc:\n");

         while((znak_tymczasowy=getchar())!='\n' && wczytane_znaki<MAX_DLUGOSC_WYRAZENIA)
         {
            if(isdigit(znak_tymczasowy) ||
                   znak_tymczasowy=='+' || znak_tymczasowy=='-' ||
                   znak_tymczasowy=='*' || znak_tymczasowy=='/' ||
                   znak_tymczasowy=='^' || znak_tymczasowy=='.' ||
                   znak_tymczasowy=='(' || znak_tymczasowy==')')
            {
               zapis_ifiksowy[indeks_tablicy]=znak_tymczasowy;
               indeks_tablicy++;
               wczytane_znaki++;
            }
            else
            {
               if(blad_skladni!=1) 
               {
                  printf("!!! Syntax ERROR !!! - blad skladni!\n");
                  blad_skladni=1;
                  wczytane_znaki++;
                  wyrazenie_poprawne=0;
               }
            }
         }
      }
      return zapis_ifiksowy;
}

Wydaje mi się jednak, że nie jest to do końca dobrze, ponieważ jeśli deklaruję tablicę, zawierającą 20 znaków, a zapełnię ją np. 10, to pozostałe miejsce zostanie uzupełnione przypadkowymi znakami.
Podobno lepiej jest to zrobić przez wskaźniki i dynamiczną alokację pamięci. Próbowałem tak zrobić, ale mam z tym ogromne problemy... Czy ktoś może mi w tym pomóc?

Z góry dziękuję za zainteresowanie tematem.

Pozostało 580 znaków

2009-12-15 12:25
0

Strasznie kombinujesz zwykłe czytanie stringa z klawiatury. Wczytaj całego od razu za pomocą scanf() i dopiero potem sprawdzaj poprawność.
Bo tak jak jest, użytkownikowi będą wyskakiwać komunikaty przy każdej głupiej literówce, bez możliwości poprawienia backspace'em.

Obawiam się, że nie będziesz wiedział co dalej. Parę słów do wygóglania: parser arytmetyczny, stos, maszyna stanów.

Pozostało 580 znaków

2009-12-15 14:02
0

Tia, zabawa zacznie się dopiero po wczytaniu stringa. Stojące przed Tobą zadanie nie jest trywialne, jak już wspomniał Azarien. Alternatywnym uniwersalnym sposobem rozwiązania jest zbudowanie w pamięci drzewa składni. Węzły mógłbyś zaimplementować w formie struktur. Jeden typ struktur mógłby reprezentować wyrażenie: zarówno operatory (+, - itd.), jak i wartości (liczby). Powiedzmy pole operator typu char przechowywałoby znak operatora ('+', '-' itd.), a pole value wartość liczbową (int lub double). Gdy pole operator ustawione byłoby na znak 0 (nie '0', tylko 0), to oznaczałoby to, że powinieneś spojrzeć na pole value. Struktury powinny też mieć pole (w formie tablicy) lub pola będące wskaźnikami do argumentów. Np. 2+3 to byłaby struktura reprezentująca operator '+', której jeden argument wskazywałby na strukturę reprezentującą wartość 2, a drugi -- 3

W każdym razie, samo przeglądanie łańcucha znaków możesz zrealizować dwuetapowo. Najpierw analizować tekst leksykalnie i przerobić go na ciąg tokenów. Tokenami mogą być już te docelowe struktury, tyle że jeszcze bez ustawionych argumentów. Na tym etapie możesz zechcieć wprowadzić sobie dodatkowe (pseudo)argumenty: nawiasy otwierające i zamykające.

W etapie drugim analizujesz płaski ciąg tokenów i robisz z niego drzewo składni, co nazywamy analizą składniową. Musisz wziąć pod uwagę priorytet operatorów i nawiasy (nawiasów używasz tylko do wskazania kolejności parsowania i nie wstawiasz ich do drzewa!). Np. wyrażenie 2 + 3*4 zamieniasz na drzewo:

[+]
|-[2]
|-[*]
  |-[3]
  |-[4]

Mając już takie drzewo łatwo obliczyć jego wartość. Robisz funkcję calculate() i startujesz w korzeniu. Jeśli bieżący węzeł jest wartością (liczbą), to zwracasz tę wartość (poznajesz to po tym, że operator == 0). Jeśli bieżący węzeł jest operatorem, to w zależności od typu operatora zwracasz calculate(argument_lewy) + calculate(argument_prawy), calculate(argument_lewy) - calculate(argument_prawy) itd.

W sumie analizę leksykalną i składniową możesz zrobić w jednym rzucie, choć w zwykłej notacji infixowej nie jest to takie proste jak w tej sztucznej odwrotnej notacji polskiej. Poza tym podzielenie analizy na trzy funkcje: analiza leksykalna, analiza składniowa i obliczanie umożliwia stosunkowo łatwe dostosowanie kalkulatora do obliczania innych notacji. Wystarczy tylko zmienić funkcję odpowiedzialną za analizę składniową.

Pozostało 580 znaków

2009-12-15 14:05
0

To czego szukasz to algorytm ONP a dokadniej Odwrotna Notacja Polska (Reverse Polish Notation). Wiecej w google, ale latwiej znajdziesz taka biblioteke pod c++ niz c


Pozostało 580 znaków

2009-12-15 14:10
0

@Piotr Zegar:
Odwrotna Notacja Polska...? Chyba coś Ci się pomyliło. Autor tematu wyraźnie napisał i pokazał, że chodzi o najzwyklejszą, klasyczną notację infiksową. ONP jest chyba najprostszą notacją do implementacji, ale najwyraźniej prowadzący zajęcia z podstaw programowania ZAKAZAŁ jej użycia. I autor tematu musi użyć zapisu wrostkowego. Dobrze o tyle, że jest dla ludzi znacznie bardziej naturalny i powszechniejszy niż ONP.

Pozostało 580 znaków

2009-12-15 15:13
ŁF
0

@bswierczynski: gdzie to masz napisane? ONP jest najprostszym rozwiązaniem tego problemu, ma najwięcej gotowców/przykładów w necie, i wreszcie nigdzie w treści postów autora wątku nie widzę niczego o nieużywaniu ONP. ale może nieuważnie przeczytałem treść wątku.


Pozostało 580 znaków

2009-12-15 15:18
0

@ŁF:
Napisał to @pzielak w swoim poście.

pzielak napisał(a)

Chodzi o to, aby kalkulator potrafił policzyć np. coś takiego:

2*4-(2.1+8)^(3-2)/18

Kalkulator parsujący wyrażenia ONP nie policzy wyrażenia 2*4-(2.1+8)^(3-2)/18. Do tego potrzebny jest kalkulator z parserem notacji infixowej.

Pozostało 580 znaków

2009-12-15 15:19
bogdans_niezalogowan
0

Ja bym się upierał, że fragment

2*4-(2.1+8)^(3-2)/18
zachowując naturalną kolejność działań, tj: nawiasy,
mocno sugeruje, że ONP oraz NP nie są dopuszczalne</quote></quote>

Pozostało 580 znaków

2009-12-15 15:28
0

@bogdans_niezalogowany:
@ŁF:
Sama treść zadania -- tzn. tekst ujęty w cudzysłowach -- chyba nawet nie wyklucza tej ONP. Ale to, co dopisał autor -- że powinien zostać obliczony ten przykładowy ciąg zapisany w notacji infixowej -- już w 100% wyklucza napisanie kalkulatora obsługującego jedynie ONP. Taki parser po prostu nie obsłuży tego przykładowego ciągu.

Pozostaje pytanie, czy ten przykładowy ciąg to tylko komentarz autora tematu? Czy podał go na zajęciach prowadzący? Jeśli podał, to można założyć, że jest to część polecenia przekazana jedynie ustnie. Jeśli jednak prowadzący nic o tym nie mówił, to może i można zastosować ONP... choć może być to źle odebrane przez prowadzącego. Zawsze można go spytać, czy jest taka możliwość.

Tak czy siak, parser ONP jest wyraźnie prostszy, ale parser notacji infixowej jest za to bardziej przydatny i chyba więcej można się na nim nauczyć.

Pozostało 580 znaków

2009-12-15 15:35
bogdans_niezalogowan
0

Zwróciliście uwagę, że w komentarzu jest mowa o zachowaniu naturalnej kolejności działań (między innymi nawiasów). Jak to pogodzić z ONP?

Pozostało 580 znaków

2009-12-15 15:44
0

Komentarza nie da się pogodzić z ONP. Samą treść zadania może się i da. Pytanie, czy komentarz został napisany w oparciu o polecenie ustne wydane przez prowadzącego, czy to autor tematu tak to sobie sam wymyślił. No i pytanie o ambicje autora. Też pisałem kiedyś kalkulator na zajęciach i niektórzy stosowali ONP, a niektórzy nie. Ja zastosowałem notację infixową i chyba nawet bawiłem się w jednoargumentowe operatory (np. jednoargumentowy minus, czy plus [który w zasadzie nic nie robi]).

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0