Programowanie w języku C/C++ » Artykuły

Odwrotna notacja polska w praktyce

  • 2011-11-16 10:57
  • 10 komentarzy
  • 4941 odsłon
  • Oceń ten tekst jako pierwszy
Nawiązując do artykułu o Odwrotna_notacja_polska chciałbym przedstawić jak można wykorzystać ją w praktyce, na przykładzie języka C++. Nie będę się ponownie rozwodził jak się to wykonuje, bo zostało to już opisane. Cała esencja polega na tym, że nie musimy wyrażenia arytmetycznego przerabiać najpierw na RPN a później obliczać. Wszystko możemy wykonać za jednym zamachem. Przykładowo mamy równanie:

2*2+2

W programie wykorzystujemy dwa stosy - jeden na liczby (najlepiej zmiennoprzecinkowe), drugi na znaki arytmetyczne. I teraz od lewej bierzemy dwójkę na stos z liczbami, dalej znak mnożenia na stos ze znakami arytmetycznymi, znowu dwa na stos i dalej znak plus. Na stosie ze znakami jest mnożenie, czyli wyższy priorytet od dodawania. Tak więc zdejmujemy mnożenie, wykonujemy na liczbach ze stosu i znowu wynik odkładamy ponownie.
Dalej dwa znowu na stos i koniec. Więc zdejmujemy kolejno wszystkie znaki a że mamy tylko jeden (dodawanie), to sumujemy wynik mnożenia odłożony na stosie z ostatnia dwójką.
Nie rozwlekałem się dokładniej nad tym zadaniem, gdyż opis i stosowaną terminologie można zobaczyć we wspomnianym artykule.

typedef double typ_danej;
 
typ_danej oblicz(string &s) {
 
 
 typ_danej liczba (0);
 
 char stos_char[count_char];
 char last_;
 int pos_stos_char (0);
 
 typ_danej stos_liczba[count_char * 2];
 int pos_stos_liczba (0);
 
 while (s.length()>0) {
 
   if (isdigit(s[0])) {
 
     liczba = atof(s.c_str());
 
     while (isdigit(s[0]) || s[0]=='.') s.erase(0,1);  
 
     stos_liczba[pos_stos_liczba] = liczba;
     pos_stos_liczba++;
 
   } else {
 
     if (s[0]!=')') {
       if (pos_stos_char>0) {
         last_ = stos_char[pos_stos_char - 1];                   
       } else last_ = '#';
       } else last_ = ')';    
 
     while(priorytet(s[0],last_)==0) {
 
       if (przelicz(last_,&stos_liczba[pos_stos_liczba],pos_stos_liczba)==1) {
         DivideByZero = true;
         return 0;
       }                                         
       pos_stos_char--;
 
       if (pos_stos_char>0) {
         last_ = stos_char[pos_stos_char - 1];                   
       } else last_ = '#';                               
     }                                                  
 
     if (last_!=')') {
       stos_char[pos_stos_char] = s[0];
       pos_stos_char++;
     } else {
 
      while (stos_char[pos_stos_char-1]!='(') {
 
        if (przelicz(stos_char[pos_stos_char-1], &stos_liczba[pos_stos_liczba],pos_stos_liczba)==1) {
          DivideByZero = true;
          return 0;
        }                                                                                             
        pos_stos_char--; 
 
      }
      pos_stos_char--;
     }       
 
     s.erase(0,1);      
 
   }             
 }
 
 
 while (pos_stos_char>0) {
 
   if (przelicz(stos_char[pos_stos_char-1], &stos_liczba[pos_stos_liczba],pos_stos_liczba)==1) {
     DivideByZero = true;
     return 0;
   }                                                                                                
   pos_stos_char--;
 
 }
 
 return stos_liczba[pos_stos_liczba-1];
}


Argumentem funkcji jak widać jest dana typu string, w której opisane jest równanie. Są oczywiście odnośniki do innych funkcji, które można przeanalizować ściągając całość (link niżej).
Jest to dość prosty kalkulator, gdyż operuje na następnych znakach arytmetycznych: + - * / (potęga, która też może być pierwiastkowaniem - np. pierwiastek trzeciego stopnia z 27 zapiszemy: 27(1/3), czyli 27 do potęgi jednej trzeciej) oraz nawiasy.
W załączniku dodałem kompletny kod źródłowy, gdzie dodatkowo jest funkcja do weryfikacji równania, wraz z kodem wynikowym w postaci pliku wykonywalnego. Oparte jest to na konsoli a sam program pisałem pod kompilator Dev-C++. Kod można ściągnąć stąd.

10 komentarzy

Twardy 2012-01-28 13:13

ooo starocie. Ale wtedy nerwowy człowiek był. Wszedłem bo zauważyłem w logach, że było odwołanie do mojego serwera ze skutkiem 404. Usunąłem jakiś czas temu dział soft bo myślałem, że już nie potrzebny :D. W najbliższym czasie naprawie problem z linkiem.

P.K. Halladin 2008-08-10 21:52

Twardy, polecam wziąć udział w Olimpiadzie Zaciemniania Kodu - masz duże szanse na przyzwoite miejsce. A tak na marginesie:

    cout << 0["yft"] << 1["goe"] << 2["dtu"] << 0[" yt"];
    cout << 0["sft"] << 1["gue"] << 2["dtc"] << 0["koe"];
    cout << endl;

Poza tym jaki jest sens optymalizować algorytm, który operuje na łańcuchach, które mają od kilku do kilkudziesięciu znaków ? Człowieku zyskasz najwyżej nanosekundę (może dwie) - kosmicznie dłużej trwać będzie dwukrotne kliknięcie w celu uruchomienia Twojego programu. W readme.txt trzeba będzie dopisywać aby użytkownik szybko klikał bo inaczej optymalizacje nie będą miały sensu. Optymalizować trzeba gdy jest potrzeba :).

radek_1986 2006-12-04 00:35

Zgadzam się z Heimdallem. Ja próbuje dodać parę funkcji (chciałem dodać arcusy i funkcje hiperboliczne) i to wcale nie jest takie proste... Ale jak ktoś ma może program w którym są te funkcje to proszę o kontakt;)

Pozdrawiam...:)

Heimdall 2006-02-22 16:18

"A to, że chcesz go wykorzystać w taki sposób świadczy tylko o Tobie, więc daruj sobie tego typu komentarze i nikt dla Ciebie nie będzie go przerabiał."

Daruj sobie tego typu teksty, kod powinien być w miarę przystosowany do przeróbek i uniwersalny. Jeżeli mówisz, że jest to kod wyłącznie edukacyjny to po jaką cholerę optymalizujesz go? Przez optymalizację tylko zaciemniłeś istotę ONP.

chmielik 2006-01-21 21:43

Programam ma jednak wady i nie idzie go tak łatwo rozbudować o inne funkcje ktore zaczynaja sie z nazwy na te same litery :(

angel2953 2006-01-10 12:37

Poprawione...Troche się namęczyłem nim skumałem sposób dodawania linków ale działa.

BTW: w podglądzie linki dodane poprzez http://4programmers.net/ są niebieskie czyli tak jakby nie istniały. Należało by to zmienic bo to wprowadza w błąd

Marooned 2006-01-09 23:08

Sugeruję odnaleźć artykuł "odwrotnej notacji polskiej (RPN)" i podmienić link, który widnieje tu w starym zapisie i nigdzie już nie prowadzi.

Twardy 2006-02-10 11:25

Ja nie stworzyłem programu, żeby sobie ściągać, przerabiać i podpisywać się pod nim. Ja pokazałem jak to działa - jest to przykład jak wykorzystać odwrotną notacje polską w praktyce. Czy tak nie brzmi temat? A to, że chcesz go wykorzystać w taki sposób świadczy tylko o Tobie, więc daruj sobie tego typu komentarze i nikt dla Ciebie nie będzie go przerabiał.

Twardy 2005-04-27 13:20

To nie zrozumiales do konca. Program za jednym zamachem zamienia na odwrotna notacje i od razu oblicza - jak sie oczywiscie da, ze wzgledu na pobierane priorytety znakow. Nie robi on calkowitej onp i pozniej ja oblicza, tylko wszystko za jednym razem aby zyskac na czasie. W poRZądku?

PiotrB 2005-04-25 22:44

pobieranie ze stosu wszystkiego i wykonywanie działań o wyższym priorytecie jest w pożądku, ale co to ma wspólnego z odwrotną notacją polską???
może się mylę, ale wydaje mi się, ze odwrotna notacja polska polega na tym, że na stos się wkłada już w odpowieniej koleności