Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Odwrotna Notacja Polska

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Należy obliczyć wartość wyrażenia ONP.

Obliczanie wartości 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 9 / 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 *
9 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 czterech 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++

W języku C++ 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

Python

W języku Pyton musimy posłużyć się wyłapywaniem wyjątków. Wyjątek (ang. exception) jest błędem, który powstał w wyniku wykonania jakiegoś polecenia. Wyjątek możemy przechwycić programowo i wykonać jakiś kod w odpowiedzi na niego. Dokonujemy tego przy pomocy konstrukcji:

try:
    ...
    testowany fragment kodu
    ....
except nazwa_wyjątku:
    ...
    kod wykonywany w odpowiedzi na wyjątek
    ...

Po try: umieszczamy instrukcję lub blok instrukcji, w wyniku wykonania których może pojawić się wyjątek. Jeśli wyjątek się nie pojawi to instrukcje po try: zostaną wykonane normalnie. Jeśli pojawi się wyjątek, to wykonanie instrukcji po try: zostaje przerwane i komputer przechodzi do wykonania instrukcji po except...:. Dzięki temu praca programu nie jest przerywana i może on odpowiednio obsłużyć pojawienie się danego wyjątku.

Aby sprawdzić, czy łańcuch tekstowy zawiera liczbę lub coś innego, wykorzystamy np. funkcję float( ), która zamienia swój argument na liczbę zmiennoprzecinkową lub generuje wyjątek ValueError (błąd wartości), jeśli konwersja się nie powiodła. Wypróbuj poniższy program:

s = input() # odczyt tekstu

try:
    v = int(s) # instrukcja testowa
    is_num = True  # jeśli jest OK
except ValueError: # wyjątek
    is_num = False # jeśli był błąd 

if is_num:
    print("liczba:",v)
else:
    print("nie liczba:",s)

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 = "=", ; znak = kończy wyrażenie ONP
     to zakończ
K03: Jeśli e jest liczbą, ; liczby umieszczamy na stosie
     to idź do kroku K09
K04: v2 S.top() ; pobieramy ze stosu argumenty operacji
     S.pop()
K05: v1 S.top()
     S.pop()
K06: Wykonaj operację na v1 i v2 ; wykonujemy obliczenia zgodnie
     zgodnie z zawartością e.    ; z symbolem operatora
     Wynik umieść w v1
K07: S.push(v1) ; wynik trafia na stos
K08: Idź do kroku K01 ; kontynuujemy przetwarzanie wyrażenia
K09: Przekształć e na liczbę w v1
K10: Idź do kroku K07 ; liczbę umieszczamy na stosie

Przykładowe programy

Uwaga:

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żeń ONP, dlatego należy uważać przy ich wprowadzaniu.

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

program rpn_eval;

const MAX_S = 100; // maksymalny 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  // przetwarzamy wyrażenie ONP
    readln(e);      // element wyrażenia ONP
    if e = '=' then break; // koniec wyrażenia ONP
    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
      v2 := S[p-1]; // dwa argumenty
      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 na stos
      dec(p);       // ze stosu znika jedna liczba
    end;
  until false; // pętla nieskończona

  writeln(S[p-1]:0:6); // wypisujemy wynik
  readln;
end.
C++
// Obliczanie wyrażenia ONP
// Data: 18.08.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

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

using namespace std;

const int MAX_S = 100; // 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

  cout << fixed;

  while(true)      // przetwarzamy wyrażenie ONP
  {
    getline(cin,e);
    if(e == "=") break; // 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 << S[--p] << endl; // wypisujemy wynik
  return 0;
}
Basic
' Obliczanie wyrażenia ONP
' Data: 18.08.2012
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const MAX_S = 100 ' 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 ' przetwarzamy wyrażenie ONP
  Input #1,e ' odczytujemy element wyrażenia ONP
  If e = "=" Then Exit While ' koniec?
  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 znika jedna liczba
  End If
Wend
Close #1
Print Using "&";S(p-1) ' wypisujemy wynik
End
Python (dodatek)
# Obliczanie wyrażenia ONP
# Data: 12.06.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

MAX_S = 100 # rozmiar stosu

S = [0.0] * MAX_S # stos
p = 0; # wskaźnik stosu

while True: # przetwarzamy wyrażenie ONP
    e = input()
    if e == "=": break # koniec wyrażenia?
    try:
        v1 = float(e) # konwertujemy na liczbę
                  # i sprawdzamy,
                  # czy nie było błędu
    except ValueError:
                  # operator
        p -= 1    # pobieramy ze stosu dwa argumenty
        v2 = S[p]
        p -= 1
        v1 = S[p]
        match e[0]: # wykonujemy operacje wg operatora
            case '+': v1 += v2
            case '-': v1 -= v2
            case '*': v1 *= v2
            case '/': v1 /= v2
    S[p] = v1 # wynik na stos
    p += 1
p -= 1
print(S[p]) # wypisujemy wynik ze stosu
Wynik:
3
5
2
*
+
=
13.000000

3
5
+
2
*
=
16.000000

10
10
*
10
*
=
1000.000000

Na początek:  podrozdziału   strony 

Problem

Należy przekształcić symboliczne wyrażenie arytmetyczne na symboliczne wyrażenie ONP.

Przekształcanie wyrażenia w 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'=',   ; sprawdzamy, czy koniec wyrażenia
     to idź do kroku K08
K04: Dopóki S.empty() = false,
     wykonuj kroki 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'(',   ; sprawdzamy, czy mamy nawias otwierający
     to idź do kroku K11
K09: S.push('(')      ; nawias otwierający umieszczamy na stosie
K10: Idź do kroku K02 ; i kontynuujemy przetwarzanie wyrażenia
K11: Jeśli c')',   ; sprawdzamy, czy mamy nawias zamykający
     to idź do kroku K17
K12: Dopóki S.top() ≠ '(',
     wykonuj kroki 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 kroku K02 ; i kontynuujemy przetwarzanie wyrażenia
K17: Jeśli c ≠ operator, ; sprawdzamy, czy mamy operator
     to idź do kroku K24
K18: Dopóki S.empty() = false,
     wykonuj kroki K19...K21
K19:   Jeśli (p(c) = 3) obrazek (p(c) > p(S.top())), ; sprawdzamy warunek zakończenia pętli
       to idź do kroku K22
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 kroku K02 ; i kontynuujemy przetwarzanie wyrażenia
K24: Pisz c           ; c przesyłamy na wyjście
K25: Idź do kroku K02 ; i kontynuujemy przetwarzanie wyrażenia

Przykładowe programy

Uwaga:

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. Elementy wyrażenia muszą być jednoznakowe i rozdzielone spacjami, jak w przykładach.
Pascal
// Przekształcanie wyrażenia na ONP
// Data: 19.08.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------

program project1;

const S_MAX = 100; // rozmiar stosu

// 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
  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 "(" zawsze na stos
            S[sptr] := '(';
            inc(sptr);
          end;
    ')' : begin // nawias zamykający
            while S[sptr-1] <> '(' do
            begin
              // ze stosu przesyłamy na wyjście
              // wszystkie operatory aż do nawiasu "("
              dec(sptr);
              write(S[sptr],' ');
            end;
            // usuwamy ze stosu nawias otwierający
            dec(sptr);
          end;
    '+', '-', '*', '/', '^' : // operator
          begin
            while sptr > 0 do
            begin
              if(p(c) = 3) or (p(c) > p(S[sptr-1])) then
                break;
              // na wyjście przesyłamy ze stosu
              // wszystkie operatory
              // o wyższych priorytetach
              dec(sptr);
              write(S[sptr],' ');
            end;
            // operator umieszczamy na stosie
            S[sptr] := c;
            inc (sptr);
          end;
    else
      // inaczej znak przesyłamy na wyjście
      write(c,' ');
    end;
  end;
  writeln;
  readln;
  readln;
end.
C++
// Przekształcanie wyrażenia na ONP
// Data: 19.08.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------

#include <iostream>

using namespace std;

const int S_MAX = 100; // rozmiar stosu

// 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 i przerywamy pętlę
      break;
    }

    switch (c) // analizujemy odczytany znak
    {
      case ' ' : break; // spację ignorujemy
      case '(' : S[sptr++] = '(';
                 // nawias "(" zawsze na stos
                 break;
      case ')' : while(S[sptr-1] != '(') // nawias ")"
                 cout << S[--sptr] << ' '; // ze stosu
                 // przesyłamy na wyjście wszystkie
                 // operatory aż do nawiasu "("
                 sptr--; // usuwamy ze stosu
                         // nawias "("
                 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
                   // 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;
}
Basic
' Przekształcanie wyrażenia na ONP
' Data: 19.08.2012
' (C)2020 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
             Print S(sptr);" "; ' na wyjście 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
             Print S(sptr);" "; ' wszystkie 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
Python (dodatek)
# Przekształcanie wyrażenia na ONP
# Data: 14.06.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------------

S_MAX = 100 # rozmiar stosu

# Zwraca priorytet operatora
def p(c):
    match c:
        case '+'|'-': return 1
        case '*'|'/': return 2
        case '^': return 3
        case _: return 0

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

S = [' ']*S_MAX # stos operatorów
sptr = 0 # wskaźnik stosu
e = input().split()
i = 0
while True:
    c = e[i]  # czytamy znak z wejścia
    i += 1
    if c == '=': # koniec wyrażenia?
        while sptr:
            sptr -= 1      # jeśli tak, na wyjście
            print(S[sptr]) # przesyłamy wszystkie
                           # operatory ze stosu
        break # i przerywamy pętlę

    match c: # analizujemy odczytany znak
        case '(':
            S[sptr] = '('
            # nawias "(" zawsze na stos
            sptr += 1
        case ')':
            while S[sptr-1] != '(': # nawias ")"
                sptr -= 1 # ze stosu przesyłamy
                print(S[sptr],end=" ") # na wyjście
                # wszystkie operatory aż do nawiasu "("
            sptr -= 1 # usuwamy ze stosu nawias "("
        case '+'|'-'|'*'|'/'|'^' :
            while sptr:
                if (p(c) == 3) or (p(c) > p(S[sptr-1])): break
                sptr -= 1 # na wyjście przesyłamy ze stosu
                print(S[sptr],end=" ") # operatory o wyższych
                                       # priorytetach
            S[sptr] = c # operator umieszczamy na stosie
            sptr += 1
        case _:
            print(c,end=" ") # inaczej znak przesyłamy
                             # na wyjście
print()
Wynik:
( a + b * c - d ) / e ^ ( f + g ) / h =
a b c * + d - e f g + ^ / h /

Na początek:  podrozdziału   strony 

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 =. Elementy wyrażenia powinny być rozdzielone pojedynczymi spacjami. Na podstawie algorytmu napisz program w wybranym języku programowania.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

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

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.