Odwrotna Notacja Polska


Tematy pokrewne   Podrozdziały
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Stosy
Podstawowe pojęcia dotyczące stosów. Realizacja stosu za pomocą tablicy i listy jednokierunkowej
Przeliczanie liczb na zapis w innym systemie pozycyjnym
Odwrotna Notacja Polska
Sortowanie przez wstawianie za pomocą stosów
  Problem 1
Problem 2

Problem nr 1

Obliczyć wartość wyrażenia ONP.



Odwrotną notację polską ONP (ang. RPN – Reverse Polish Notation), zwana często również notacją Postfix, wymyślono w celu zapisywania dowolnych wyrażeń arytmetycznych bez nawiasów. W normalnym zapisie arytmetycznym operatory znajdują się pomiędzy argumentami:

 

2 + 2     6 - 4     3 * 5     12 / 3

 

Operatory posiadają priorytety, czyli "ważność" oraz łączność w prawo lub w lewo. Jeśli w wyrażeniu wystąpią operatory o różnych priorytetach, to najpierw zostaną wykonane te ważniejsze:

 

3 + 5 * 2 = 3 + 10 = 13

 

Jeśli chcemy zmienić kolejność wykonywania działań, musimy używać nawiasów:

 

(3 + 5) * 2 = 8 * 2 = 16

 

W ONP problem ten nie występuje. Operator zawsze występuje po swoich argumentach:

 

2 2 +     6 4 -     3 5 *     12 3 /

 

Dzięki tej prostej zasadzie nawiasy stają się zbędne:

 

3 + 5 * 2 → 3 5 2 * + = 3 10 + = 13

(3 + 5) * 2 → 3 5 + 2 * = 8 2 * = 16

 

Do obliczenia wartości wyrażenia zapisanego w ONP potrzebujemy stosu. Zasada jest następująca:

 

Wyrażenie ONP przeglądamy od strony lewej do prawej. Jeśli napotkamy liczbę, to umieszczamy ją na stosie. Jeśli napotkamy operator, to ze stosu pobieramy dwie ostatnie liczby, wykonujemy na nich działanie zgodne z napotkanym operatorem i wynik umieszczamy z powrotem na stosie. Gdy wyrażenie zostanie przeglądnięte do końca, na szczycie stosu będzie znajdował się jego wynik.

 

Przykład:

 

Wyrażenie ONP Element Operacja Stos
 3  5  2  *  +     ---
 3  5  2  *  +  3  na stos

3
---

 3  5  2  *  +  5  na stos

5
3
---

 3  5  2  *  +  2  na stos

2
5
3
---

 3  5  2  *  +  * 

pobierz 2 i 5
mnóż 5 * 2
wynik na stos

10
3
---

 3  5  2  *  +  + 

pobierz 10 i 3
dodaj 3 + 10
wynik na stos

13
---

 

Notacja ONP jest szeroko wykorzystywana w kompilatorach języków wysokiego poziomu. Istnieją również języki, które do obliczeń stosują jedynie ONP – np. Forth.

Przed przystąpieniem do zaprojektowania algorytmu ONP musimy poczynić pewne ustalenia. Dla prostoty umawiamy się, że używać będziemy tylko czterech operatorów arytmetycznych:

Wyrażenie musi być poprawne – algorytm nie sprawdza jego poprawności.

Każdy element będzie wprowadzany w osobnym wierszu – w ten sposób pozbędziemy się problemu analizowania tekstu pod kątem zawartości w nim liczb i operatorów. W rzeczywistości wyrażenie zawarte w wierszu zostałoby najpierw rozbite na elementy składowe – liczby i operatory – a następnie elementy te zostałyby użyte do obliczenia wartości wyrażenia wg naszego algorytmu.

Liczby muszą mieć postać akceptowaną przez dany język programowania.

Ostatnim elementem wyrażenia jest znak "=". Powoduje on zakończenie obliczeń i wyprowadzenie wyniku ze stosu.

W algorytmie będziemy musieli rozpoznawać, czy wprowadzony element jest liczbą, czy też operatorem lub znakiem "=". W trzech wybranych przez nas językach można to zrobić następująco:

 

Pascal

Wykorzystujemy systemową procedurę val(s,v,c), która posiada trzy parametry:

 

s – łańcuch znakowy zawierający liczbę w postaci cyfr
v – zmienna, w której zostanie umieszczona wartość liczby
c – pozycja błędu

 

Procedura val dokonuje konwersji łańcucha s na wartość liczbową, która zostaje umieszczona w zmiennej v. Jeśli konwersja przebiegła prawidłowo, to w zmiennej c jest umieszczana wartość 0. W przeciwnym razie c zawiera numer pozycji znaku w s, który nie można było zinterpretować jako część zapisu liczby – w takim przypadku zawartość v jest nieokreślona.

 

program test_str_to_double;

var
  x : double;
  s : string;
  c : word;

begin
  readln(s);      // odczytujemy tekst
  val(s,x,c);     // dokonujemy konwersji
  if c = 0 then   // sprawdzamy, czy konwersja się powiodła
    writeln('LICZBA')
  else
    writeln('NIE LICZBA');
end.

 

C++

Tutaj wykorzystuje się najczęściej strumienie. Wykorzystujemy własność strumienia, który przy złej konwersji daje wartość 0. Wypróbuj poniższy program dla strumienia cin:

 

#include <iostream>

using namespace std;

int main()
{
    double x;

    cout << (cin >> x) << endl;
    return 0;
}
 

Program odczytuje ze strumienia cin ciąg znaków i stara się je zamienić na liczbę zmiennoprzecinkową dla zmiennej x. Jeśli konwersja się powiedzie, to operacja (cin >> x) zwróci jakąś wartość różną od zera. Jeśli ciągu znaków nie da się zamienić na liczbę, to operacja zwróci wartość 0 (w programie wpisz wartość poprawną, np. 12.54, a następnie niepoprawną, np. ABC – za pierwszym razem otrzymasz coś różnego od zera, a za drugim zero). Jeśli operacje takie wykonujemy w pętli, to należy wyzerować stan znaczników błędów strumienia za pomocą funkcji cin.clear() – inaczej dostaniemy poprzednią wartość błędu.

Na tym prostym fakcie oprzemy rozpoznawanie, czy wprowadzony łańcuch tekstu reprezentuje liczbę, czy nie. Jako strumień wykorzystamy strumień łańcuchowy. Będzie nam potrzebny plik nagłówkowy sstream, który definiuje klasy strumieni łańcuchowych.

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    double x;
    stringstream ss; // strumień łańcuchowy
    string s;        // łańcuch;

    cin >> s;        // czytamy łańcuch znaków
    ss << s;         // odczytany łańcuch umieszczamy w strumieniu
    if(ss >> x)      // konwertujemy na liczbę i sprawdzamy, czy konwersja była poprawna
      cout << "LICZBA\n";
    else
      cout << "NIE LICZBA\n";
    return 0;
}

Basic

W języku BASIC mamy funkcję Val(s), która dokonuje konwersji łańcucha s na wartość zmiennoprzecinkową, która staje się wynikiem tej funkcji. Jeśli konwersja się nie powiedzie, to funkcja zwraca 0. I tutaj mamy drobny problem, ponieważ 0 jest również zwracane dla tekstu "0". Zatem strategia jest następująca: jeśli wynik Val jest różny od zera, to mamy na pewno do czynienia z liczbą. W przeciwnym razie musimy dodatkowo sprawdzić, czy pierwszym znakiem tekstu jest "0". Jeśli tak, to jest to wciąż liczba. Jeśli nie, łańcuch zawiera operator. Wypróbuj poniższy program:

 

Dim x As Double, s As String

Input s       ' czytamy łańcuch znaków
x = Val(s)    ' dokonujemy konwersji
              ' sprawdzamy wynik konwersji
If x <> 0 OrElse Left(s,1) = "0" Then
	Print "LICZBA"
Else
	Print "NIE LICZBA"
End If

End

 

Algorytm obliczania wartości wyrażenia ONP

Wejście:
S    stos liczb zmiennoprzecinkowych

Kolejne elementy wyrażenia odczytujemy ze standardowego wejścia

Wyjście:

Wartość wyrażenia ONP na szczycie stosu S

Elementy pomocnicze:
e  – przechowuje odczytaną informację z wejścia jako łańcuch tekstowy
v1, v2  –  przechowują argumenty operacji
Lista kroków:
K01: Czytaj e ; odczytujemy kolejne elementy wyrażenia ONP
K02: Jeśli e = "=", to zakończ ; znak = kończy wyrażenie ONP
K03: Jeśli e jest liczbą, to idź do K09 ; liczby umieszczamy na stosie
K04: v2 ← S.top()
S.pop()
; pobieramy ze stosu argumenty operacji
K05: v1 ← S.top()
S.pop()
 
K06: Wykonaj operację na v1 i v2 zgodnie z zawartością e.
Wynik umieść w v1
; wykonujemy obliczenia zgodnie ze znakiem operatora
K07: S.push(v1) ; wynik trafia na stos
K08: Idź do K01 ; kontynuujemy przetwarzanie wyrażenia
K09: Przekształć e na liczbę w v1  
K10: Idź do K07 ; liczbę umieszczamy na stosie

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program wczytuje ze standardowego wejścia kolejne elementy wyrażenia ONP i oblicza jego wartość. Wynik jest wypisywany po wprowadzeniu znaku "=". Wtedy program kończy działanie.

Uwaga: stos w programie jest zrealizowany za pomocą tablicy. Na początku należy określić stałą MAX_S tak, aby dane zmieściły się w tablicy – wartość 100 powinna wystarczyć dla większości wyrażeń. Program nie sprawdza poprawności wyrażenia ONP.

 

Lazarus
// Obliczanie wyrażenia ONP
// Data: 18.08.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

program rpn_eval;

const MAX_S = 100;  // definiuje rozmiar stosu

var
  S : array[0..MAX_S-1] of double; // stos
  p : integer;                     // wskaźnik stosu
  e : string;                      // element wyrażenia ONP
  v1,v2 : double;                  // argumenty operacji
  c : word;                        // pozycja błędu przy konwersji

begin

  p := 0;              // inicjujemy stos;

  repeat               // w pętli przetwarzamy wyrażenie ONP

    readln(e);         // odczytujemy element wyrażenia ONP

    if e = '=' then break;

    val(e,v1,c);       // dokonujemy konwersji

    if c = 0 then
    begin              // liczba
      S[p] := v1;      // umieszczamy ją na stosie
      inc(p);          // zwiększamy wskaźnik stosu
    end
    else
    begin              // operator
      v1 := S[p-2];    // pobieramy ze stosu dwa argumenty
      v2 := S[p-1];
      case e of        // wykonujemy operacje wg operatora
        '+' : v1 := v1 + v2;
        '-' : v1 := v1 - v2;
        '*' : v1 := v1 * v2;
        '/' : v1 := v1 / v2;
      end;
      S[p-2] := v1;    // wynik umieszczamy na stosie
      dec(p);          // ze stosu zniknęła jedna liczba
    end;

  until false;

  writeln(S[p-1]:0:6); // wypisujemy wynik ze szczytu stosu

end.
Code::Blocks
// Obliczanie wyrażenia ONP
// Data: 18.08.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>

using namespace std;

const int MAX_S = 100;  // definiuje rozmiar stosu

int main()
{
  double S[MAX_S];      // stos
  int p = 0;            // wskaźnik stosu
  string e;             // element wyrażenia ONP
  double v1,v2;         // argumenty operacji
  stringstream ss;      // strumień łańcuchowy

  while(true)           // w pętli przetwarzamy wyrażenie ONP
  {
    getline(cin,e);

    if(e == "=") break; // sprawdzamy koniec wyrażenia

    ss.str("");         // usuwamy wszelki tekst ze strumienia
    ss.clear();         // czyścimy błędy konwersji z poprzednich wywołań
    ss << e;            // odczytany element umieszczamy w strumieniu

    if(ss >> v1)        // konwertujemy na liczbę i sprawdzamy, czy nie było błędu
                        // liczba
      S[p++] = v1;      // umieszczamy ją na stosie

    else
    {                   // operator
      v2 = S[--p];      // pobieramy ze stosu dwa argumenty
      v1 = S[--p];
      switch(e[0])      // wykonujemy operacje wg operatora
      {
        case '+' : v1 += v2; break;
        case '-' : v1 -= v2; break;
        case '*' : v1 *= v2; break;
        case '/' : v1 /= v2; break;
      }
      S[p++] = v1;      // wynik umieszczamy na stosie
    }
  }

  cout << fixed << S[--p] << endl; // wypisujemy wynik ze szczytu stosu

  return 0;
}
Free Basic
' Obliczanie wyrażenia ONP
' Data: 18.08.2012
' (C)2012 mgr Jerzy Wałaszek
'------------------------------

Const MAX_S = 100  ' definiuje rozmiar stosu

Dim S(MAX_S-1) As Double ' stos
Dim p As Integer         ' wskaźnik stosu
Dim e As String          ' element wyrażenia ONP
Dim As Double v1,v2      ' argumenty operacji

Open Cons For Input As #1

p = 0                    ' inicjujemy stos

While 1                  ' w pętli przetwarzamy wyrażenie ONP

  Input #1,e             ' odczytujemy element wyrażenia ONP

  If e = "=" Then Exit While

  v1 = Val(e)            ' dokonujemy konwersji

  If v1 <> 0 OrElse Left(e,1) = "0" Then
                         ' liczba
    S(p) = v1            ' umieszczamy ją na stosie
    p += 1               ' zwiększamy wskaźnik stosu

  Else
                         ' operator
    v1 = S(p-2)          ' pobieramy ze stosu dwa argumenty
    v2 = S(p-1)
    Select Case e        ' wykonujemy operacje wg operatora
      Case "+" : v1 = v1 + v2
      Case "-" : v1 = v1 - v2
      Case "*" : v1 = v1 * v2
      Case "/" : v1 = v1 / v2
    End Select
    S(p-2) = v1          ' wynik umieszczamy na stosie
    p -= 1               ' ze stosu zniknęła jedna liczba

  End If

Wend

Close #1

Print Using "&";S(p-1) ' wypisujemy wynik ze szczytu stosu

End
Wynik
3
5
2
*
+
=
13.000000

3
5
+
2
*
=
16.000000

10
10
*
10
*
=
1000.000000

 

Problem nr 2

Przekształcić symboliczne wyrażenie arytmetyczne na symboliczne wyrażenie ONP.



W wyrażeniu symbolicznym zamiast wartości liczbowych występują symbole:  (a + b) * c

Gdy obliczaliśmy wartość wyrażenia ONP, stos był używany do przechowywania wyników częściowych obliczeń – czyli był to stos liczbowy. Przy konwersji wyrażenia arytmetycznego na postać ONP również wykorzystujemy stos, jednakże tutaj będzie on przechowywał nie liczby, a operatory. Zasady są następujące:

 

Każdy operator posiada swój priorytet oraz łączność prawostronną lub lewostronną. Operator potęgowania ^ ma najwyższy priorytet i łączność prawostronną. Pozostałe operatory arytmetyczne (+ - * /) mają łączność lewostronną.

Wyrażenie arytmetyczne odczytujemy od strony lewej do prawej.

Jeśli dojdziemy do końca wyrażenia, to ze stosu operatorów pobieramy operatory i przenosimy je kolejno na wyjście aż do wyczyszczenia stosu. Algorytm kończymy.
Jeśli odczytanym elementem jest symbol zmiennej, to przenosimy go na wyjście.
Jeśli odczytanym elementem jest nawias otwierający, to umieszczamy go na stosie.
Jeśli odczytanym elementem jest nawias zamykający, to ze stosu przesyłamy na wyjście wszystkie operatory, aż do napotkania nawiasu otwierającego, który usuwamy ze stosu.
Jeśli odczytanym elementem jest operator, to:

   dopóki na stosie jest jakiś operator i:
      odczytany operator ma łączność lewostronną oraz priorytet niższy lub równy operatorowi na stosie
      lub odczytany operator ma łączność prawostronną i priorytet niższy od operatora na stosie,
      to pobieramy ze stosu operator i przesyłamy go na wyjście

Po tej operacji odczytany operator umieszczamy na stosie.
Kontynuujemy od początku z następnym elementem.

 

Przykład:

 

Wyrażenie Element Operacja Stos Wyjście
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =  start   ---  
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   (

na stos

 ( 
---

 
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   a

na wyjście

(
---

 a
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   +

na stos

 + 
(
---

a
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   b

na wyjście

+
(
---

a  b
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   *

na stos

 * 
+
(
---

a b
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   c

na wyjście

*
+
(
---

a b  c
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   -

ze stosu na wyjście
na stos

-
+
(
---

a b c *
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   d

na wyjście

-
+
(
---

a b c *  d
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   )

ze stosu na wyjście
ze stosu na wyjście
usuń ze stosu

---

a b c * d - +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   /

na stos

 / 
---

a b c * d - +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   (

na stos

 ( 
/
---

a b c * d - +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   e

na wyjście

(
/
---

a b c * d - +  e
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   +

na stos

 + 
(
/
---

a b c * d - + e
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   f

na wyjście

+
(
/
---

a b c * d - + e  f
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )   )

ze stosu na wyjście
usuń ze stosu

/
---

a b c * d - + e f +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  koniec

ze stosu na wyjście

---

a b c * d - + e f + /

 

Przed zaprojektowaniem algorytmu ustalamy co następuje:

Symbole są zbudowane z pojedynczych liter. Chodzi tutaj o uproszczenie analizy wyrażenia. Gdy napotkamy literę, to traktujemy ją jako symbol.
W wyrażeniu dozwolone są tylko operacje +, -, *, / i ^ (potęgowanie).
Wyrażenie wejściowe musi być poprawne – algorytm nie sprawdza tego.
Operacje posiadają priorytety zgodne z zasadami arytmetyki – najwyższy priorytet ma potęgowania, później mnożenie i dzielenie, a na końcu dodawanie i odejmowanie.
Wyrażenie kończy się znakiem "=".

 

Algorytm przekształcania wyrażenia na postać ONP

Wejście:

symboliczne wyrażenie arytmetyczne

Wyjście:

wyrażenie ONP

Zmienne i funkcje pomocnicze:
S  – stos operatorów
c  –  znak odczytany z wejścia
p(c)  –  funkcja zwracająca priorytet:
(    = 0
+ - = 1 - łączność lewostronna
* /  = 2 - łączność lewostronna
^    = 3 - łączność prawostronna
Lista kroków:
K01: Utwórz pusty stos S  
K02: Czytaj c ; odczytujemy znak z wejścia
K03: Jeśli c ≠ '=', to idź do K08 ; sprawdzamy, czy koniec wyrażenia
K04: Dopóki S.empty() = false, wykonuj K05...K06  
K05:     Pisz S.top() ; na wyjście przesyłamy operatory ze stosu
K06:     S.pop() ; przesłany operator usuwamy ze stosu
K07: Zakończ  
K08: Jeśli c ≠ '(', to idź do K11 ; sprawdzamy, czy mamy nawias otwierający
K09: S.push('(') ; nawias otwierający umieszczamy na stosie
K10: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia
K11: Jeśli c ≠ ')', to idź do K17 ; sprawdzamy, czy mamy nawias zamykający
K12: Dopóki S.top() ≠ '(', wykonuj K13...K14  
K13:     Pisz S.top() ; ze stosu przesyłamy na wyjście operatory
K14:     S.pop() ; aż do napotkania nawiasu otwierającego
K15: S.pop() ; usuwamy ze stosu nawias otwierający
K16: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia
K17: Jeśli c ≠ operator, to idź do K24 ; sprawdzamy, czy mamy operator
K18: Dopóki S.empty() = false, wykonuj K19...K21  
K19:     Jeśli (p(c) = 3) (p(c) > p(S.top())), to idź do K22 ; sprawdzamy warunek zakończenia pątli
K20:     Pisz S.top() ; na wyjście przesyłamy ze stosu operatory
K21:     S.pop() ; o wyższych priorytetach
K22: S.push(c) ; operator umieszczamy na stosie
K23: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia
K24: Pisz c ; c przesyłamy na wyjście
K25: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program wczytuje ze standardowego wejścia wyrażenie arytmetyczne. Na wyjściu zostaje wypisane to samo wyrażenie w postaci ONP.

 

Lazarus
// Przekształcanie wyrażenia na ONP
// Data: 19.08.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

program project1;

const S_MAX = 100; // rozmiar stosu operatorów

// Zwraca priorytet operatora
//---------------------------

function p(c : char) : integer;
begin
  case c of
   '('     : p := 0;
   '+','-' : p := 1;
   '*','/' : p := 2;
   '^'     : p := 3;
   end;
end;

//------------------------------------
// Tutaj rozpoczyna się program główny
//------------------------------------

var
  S : array[0..S_MAX-1] of char;     // stos operatorów
  sptr : integer;                    // wskaźnik stosu
  c : char;                          // kolejny znak wyrażenia

begin
  sptr := 0;                         // inicjujemy stos

  while true do
  begin

    read(c);                         // czytamy znak z wejścia

    if c = '=' then                  // koniec wyrażenia?
    begin
      while sptr > 0 do
      begin
        dec(sptr);                   // jeśli tak, na wyjście przesyłamy
        write(S[sptr],' ');          // całą zawartość stosu
      end;
      break;                         // i przerywamy pętlę
    end;

    case c of                        // analizujemy odczytany znak

    ' ' : ;                          // spację ignorujemy
    '(' : begin                      // nawias otwierający zawsze na stos
            S[sptr] := '(';
            inc(sptr);
          end;
    ')' : begin                      // nawias zamykający
            while S[sptr-1] <> '(' do
            begin
              dec(sptr);             // ze stosu przesyłamy na wyjście
              write(S[sptr],' ');    // wszystkie operatory aż do nawiasu otw.
            end;
            dec(sptr);               // usuwamy ze stosu nawias otwierający
          end;
    '+','-','*','/','^' :            // operator
          begin
            while sptr > 0 do
            begin
              if (p(c) = 3) or (p(c) > p(S[sptr - 1])) then break;
              dec(sptr);             // na wyjście przesyłamy ze stosu wszystkie
              write(S[sptr],' ');    // operatory o wyższych priorytetach
            end;
            S[sptr] := c;            // operator umieszczamy na stosie
            inc(sptr);
          end;
    else
      write(c,' ');                  // inaczej znak przesyłamy na wyjście
    end;
  end;

  writeln;
end.
Code::Blocks
// Przekształcanie wyrażenia na ONP
// Data: 19.08.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

const int S_MAX = 100; // rozmiar stosu operatorów

// Zwraca priorytet operatora
//---------------------------

int p(char c)
{
  switch(c)
  {
    case '+'     : ;
    case '-'     : return 1;
    case '*'     : ;
    case '/'     : return 2;
    case '^'     : return 3;
  }
  return 0;
}

//------------------------------------
// Tutaj rozpoczyna się program główny
//------------------------------------

int main()
{
  char S[S_MAX];                             // stos operatorów
  int sptr = 0;                              // wskaźnik stosu
  char c;                                    // kolejny znak wyrażenia

  while(true)
  {
    cin >> c;                                // czytamy znak z wejścia

    if(c == '=')                             // koniec wyrażenia?
    {
      while(sptr) cout << S[--sptr] << ' ';  // jeśli tak, na wyjście przesyłamy
                                             // wszystkie operatory ze stosu
      break;                                 // i przerywamy pętlę
    }

    switch(c)                                // analizujemy odczytany znak
    {
      case ' ' : break;                      // spację ignorujemy
      case '(' : S[sptr++] = '(';            // nawias otwierający zawsze na stos
                 break;
      case ')' : while(S[sptr-1] != '(')     // nawias zamykający
                 cout << S[--sptr] << ' ';   // ze stosu przesyłamy na wyjście
                                             // wszystkie operatory aż do nawiasu otw.
                 sptr--;                     // usuwamy ze stosu nawias otwierający
                 break;
      case '+' : ;                           // operator
      case '-' : ;
      case '*' : ;
      case '/' : ;
      case '^' : while(sptr)
                 {
                   if((p(c) == 3) || (p(c) > p(S[sptr - 1]))) break;
                   cout << S[--sptr] << ' '; // na wyjście przesyłamy ze stosu wszystkie
                 }                           // operatory o wyższych priorytetach
                 S[sptr++] = c;              // operator umieszczamy na stosie
                 break;
      default:   cout << c << ' ';           // inaczej znak przesyłamy na wyjście
                 break;
    }
  }

  cout << endl;

  return 0;
}
Free Basic
' Przekształcanie wyrażenia na ONP
' Data: 19.08.2012
' (C)2012 mgr Jerzy Wałaszek
'------------------------------

Const S_MAX = 100 ' rozmiar stosu operatorów

' Zwraca priorytet operatora
'---------------------------
Function p(c As String) As Integer
  Select Case c
         Case "("
           p = 0
         Case "+","-"
           p = 1
         Case "*","/"
           p = 2
         Case "^"
           p = 3
  End Select
End Function

Dim S(S_MAX) As String * 1          ' stos operatorów
Dim sptr As Integer                 ' wskaźnik stosu
Dim c As String * 1                 ' kolejny znak wyrażenia
Dim t As String                     ' przechowuje wczytany wiersz
Dim i As Integer                    ' indeks

Open Cons For Input As #1

sptr = 0                            ' inicjujemy stos

Line Input #1,t                     ' odczytujemy tekst
i = 1                               ' indeks na pierwszy znak tekstu

Close #1

While 1

  c = Mid(t,i,1)                    ' czytamy znak
  i += 1                            ' przesuwamy się na następną pozycję

  If c = "=" then                   ' koniec wyrażenia?
    while sptr > 0
      sptr -= 1                     ' jeśli tak, na wyjście przesyłamy
      Print S(sptr);" ";            ' całą zawartość stosu
    Wend
    Exit While                      ' i przerywamy pętlę
  End If

  Select Case c                     ' analizujemy odczytany znak
         Case " "                   ' spację ignorujemy
         Case "("                   ' nawias otwierający zawsze na stos
           S(sptr) = "("
           sptr += 1
         Case ")"                   ' nawias zamykający
           While S(sptr-1) <> "("
             sptr -= 1              ' ze stosu przesyłamy na wyjście
             Print S(sptr);" ";     ' wszystkie operatory aż do nawiasu otw.
           Wend
           sptr -= 1                ' usuwamy ze stosu nawias otwierający
         Case "+","-","*","/","^"   ' operator
           While (sptr > 0)
           	 If (p(c) = 3) OrElse (p(c) > p(S(sptr - 1))) Then Exit While
             sptr -= 1              ' na wyjście przesyłamy ze stosu wszystkie
             Print S(sptr);" ";     ' operatory o wyższych priorytetach
           Wend
           S(sptr) = c              ' operator umieszczamy na stosie
           sptr += 1
    Case Else
         Print c;" ";               ' inaczej znak przesyłamy na wyjście
  End Select
Wend

Print

End
Wynik
(a + b * c - d) / e ^ (f + g) / h =
a b c * d - + e f g + ^ h / /

 

Zadania

  1. Opracuj algorytm prostego kalkulatora ONP. Kalkulator powinien umożliwiać wprowadzanie liczb, operatorów działań arytmetycznych, wyświetlać wynik po wprowadzeniu znaku = oraz czyścić stos.
  2. Opracuj algorytm, który oblicza wartość dowolnego wyrażenia arytmetycznego zbudowanego z jednocyfrowych liczb, operatorów + - * / ^ oraz nawiasów ( ). Wyrażenie kończy się znakiem =. Na podstawie algorytmu napisz program w wybranym języku programowania.

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe