Odwrotna notacja polska w praktyce

Twardy

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

"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.

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

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

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.

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 :).

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...:)

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

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

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ł.

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?

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