„Odwrotna Notacja Polska” (ONP, ang. Reverse Polish Notation, RPN) to po prostu inny sposób zapisywania wyrażeń arytmetycznych czy też algorytmów. Polega ona w dużym skrócie na prostszym zapisie wyrażeń arytmetycznych bez nawiasów z zachowaniem kolejności wykonywania działań.
Ogólny opis problemu
Przykład:
(2+3)*5To samo wyrażenie w ONP:
2 3 + 5 *Algorytm konwersji wyrażeń z Odwrotnej Notacji Polskiej do postaci infiksowej w dużym uproszczeniu polega na wczytywaniu pojedynczych znaków z wejścia. Jeżeli wczytaną daną jest liczba, program powinien odłożyć ją na stos i przejść dalej do momentu natrafienia na działanie arytmetyczne. Wtedy należy ściągnąć ze stosu jego argumenty i wypisać na wyjście podziałanie.
Zwykła konwersja z ONP do postaci infiksowej (używanej na co dzień) nie jest zbytnio skomplikowana. Jeżeli jednak konwertowane wyrażenie będziemy chcieli zapisać z minimalną liczbą nawiasów umożliwiającą zachowanie kolejności wykonywania działań, skala trudności znacząco się podniesie.
Algorytm minimalnej liczby nawiasów przy konwersji z ONP do INF
Problem minimalnej liczby nawiasów nie jest wbrew pozorom tak bardzo skomplikowany jak by się mogło wydawać. Aby go rozwiązać będziemy potrzebowali przede wszystkim jakiejś funkcji, która zwracałaby nam informację o priorytecie danego działania arytmetycznego zgodnie z kolejnością wykonywania działań:
| Działanie arytmetyczne | Priorytet |
+ (dodawanie), - (odejmowanie) | 1 |
* (mnożenie), / (dzielenie) | 2 |
^ (potęgowanie) | 3 |
~ (minus jedno-argumentowy) | 4 |
1, 2, 3, 4, 5, 6, 7, 8, 9, 0 (liczby) | 5 |
Znając już priorytety poszczególnych działań arytmetycznych możemy zastanowić się nad tym w jaki sposób wykorzystać te informacje do zapisania minimalnej liczby nawiasów.
Mając wyrażenie:
ab+cd*/Można go zapisać w postaci drzewa:

Przy minimalnej liczbie nawiasów, po poprawnej konwersji do postaci infiksowej otrzymamy taki wynik:
(a+b)/(c*d)Jak widać w nawias zostało wzięte dodawanie (+) oraz mnożenie (*).
Przy decydowaniu, które wyrażenie ma zostać wzięte w nawias należy kierować się poniższymi regułami:
- gdy priorytet operatora w korzeniu poddrzewa jest większy od priorytetu operatora w lewym potomku to podwyrażenie z lewego potomka bierzemy w nawias,
- gdy priorytet operatora w korzeniu poddrzewa jest większy lub równy od priorytetu operatora z prawego potomka to podwyrażenie znajdujące się w prawym potomku bierzemy w nawias.
Uwaga: powyższe reguły traktują wszystkie operatory binarne (w tym potęgowanie ^) jako lewostronnie łączne. W konwencji matematycznej potęgowanie wiąże w prawo, dlatego dla drzewa odpowiadającego wyrażeniu (a^b)^c algorytm zapisze wynik jako a^b^c. To zapis zgodny z przyjętą tu konwencją, ale inny niż w notacji matematycznej.
Zgodnie z tymi regułami mamy w korzeniu lewego poddrzewa operator dodawania (+), którego priorytet zgodnie z tabelką wyżej wynosi 1, w lewym potomku (lewym dziecku) mamy natomiast cyfrę oznaczoną w tym przykładzie literą „a” czyli priorytet wynosi 5. Tak więc mamy priorytet w korzeniu poddrzewa mniejszy niż priorytet w lewym dziecku, więc nic nie robimy.
Przejdźmy teraz do prawego potomka. Tam również mamy cyfrę (w tym przykładzie zapisaną jako literę) więc analogicznie jak wyżej, nic nie robimy bo 1 jest mniejsze od 5.
Drugi przypadek, w prawym poddrzewie priorytet korzenia wynosi 2 (operator mnożenia (*)) ważne jest jednak to, że zarówno w lewym oraz prawym dziecku mamy cyfrę (w tym przykładzie zapisaną jako literę) czyli priorytet wynosi 5. No i znowu analogicznie 2 jest mniejsze od 5 więc nic nie robimy.
Przechodzimy teraz wyżej. Mamy w korzeniu poddrzewa dzielenie (/) czyli priorytet będzie wynosił 2. Lewy potomek to dodawanie z priorytetem 1. Tak więc priorytet z korzenia jest większy od priorytetu lewego dziecka. Zgodnie z powyższymi punktami (pierwszy punkt) wyrażenie z lewego potomka bierzemy w nawias czyli a+b ma być w nawiasie.
Po prawej stronie mamy dziecko, którego priorytetem jest 2 (dla dzielenia: /), a w korzeniu mamy mnożenie i też mamy priorytet 2. No i znowu zgodnie z drugim puntem, priorytet korzenia jest równy priorytetowi prawego dziecka więc wyrażenie c*d bierzemy w nawias.
Przykład praktyczny
Weźmy takie wyrażenie zapisane w ONP:
a b c * d e - f ^ / +No to idziemy po kolei:
a,borazcidzie na stos z priorytetami 5 (dla każdego, czyli na stosie z priorytetami mamy 3 pozycje po 5),- wczytujemy na wejściu mnożenie (*), mamy priorytet 2 (bo mnożenie), wykonujemy więc następujące operacje:
- ściągamy ze stosu
c(czyli to co jest na górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dlacjest mniejszy lub równy (<=) od 2 (dla mnożenia priorytet to 2). W tym przypadku mamy fałsz czyli nic nie robimy, - ściągamy ze stosu element
b(element, który jest na samej górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dla b jest mniejszy (<) od 2 (dla mnożenia priorytet to 2). W tym przypadku mamy fałsz czyli nic nie robimy.
- ściągamy ze stosu
- na stos wrzucamy
b*c([drugi pobrany element] + [działanie arytmetyczne, które wczytaliśmy] + [pierwszy pobrany element]), natomiast na stos priorytetów wędruje 2 – ze względu na mnożenie, dorazeidzie na stos z priorytetami 5,- wczytujemy na wejściu minus (-), mamy priorytet 1 (bo odejmowanie), wykonujemy więc następujące operacje:
- ściągamy ze stosu
e(czyli to co jest na górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dlaejest mniejszy lub równy (<=) od 1 (dla odejmowania priorytet to 1). No i analogicznie jak wyżej mamy fałsz więc nic nie robimy, - ściągamy ze stosu element
d(element, który jest na samej górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dladjest mniejszy (<) od 1 (dla odejmowania priorytet to 1). Znowu analogicznie mamy fałsz czyli po prostu nic nie robimy.
- ściągamy ze stosu
- na stos wrzucamy
d-e([drugi pobrany element] + [działanie arytmetyczne, które wczytaliśmy] + [pierwszy pobrany element]), natomiast na stos priorytetów wędruje 1 – ze względu na odejmowanie, - na stos idzie
fz priorytetem 5, - wczytujemy na wejściu potęgowanie (^), mamy priorytet 3 (bo potęgowanie), wykonujemy więc następujące operacje:
- ściągamy ze stosu f (czyli to co jest na górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dla
fjest mniejszy lub równy (<=) od 3 (dla potęgowania priorytet to 3). No i analogicznie jak wyżej mamy fałsz więc nic nie robimy, - ściągamy ze stosu
d-e(czyli to co jest na górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dlad-ejest mniejszy (<) od 3. I tutaj uwaga: mamy coś takiego 1<3 czyli „prawdę”! Bierzemy więc w nawiasd-e:(d-e).
- ściągamy ze stosu f (czyli to co jest na górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dla
- na stos wrzucamy
(d-e)^f([drugi pobrany element] + [działanie arytmetyczne, które wczytaliśmy] + [pierwszy pobrany element]), natomiast na stos priorytetów wędruje 3 – ze względu na potęgowanie, - wczytujemy na wejściu dzielenie (/), mamy priorytet 2 (bo dzielenie), wykonujemy więc następujące operacje:
- ściągamy ze stosu
(d-e)^f(czyli to co jest na górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dla(d-e)^fjest mniejszy lub równy (<=) od 2 (dla dzielenia priorytet to 2). No i analogicznie jak wyżej mamy fałsz więc nic nie robimy, - ściągamy ze stosu
b*c(czyli to co jest na górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dlab*cjest mniejszy (<) od 2. Mamy 2 < 2 więc fałsz.
- ściągamy ze stosu
- na stos wrzucamy
b*c/(d-e)^f([drugi pobrany element] + [działanie arytmetyczne, które wczytaliśmy] + [pierwszy pobrany element]), natomiast na stos priorytetów wędruje 2 – ze względu na dzielenie, - wczytujemy na wejściu dodawanie (+), mamy priorytet 1 (bo dodawanie), wykonujemy więc następujące operacje:
- ściągamy ze stosu
b*c/(d-e)^f(czyli to co jest na górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dlab*c/(d-e)^fjest mniejszy lub równy (<=) od 1 (dla dodawania priorytet to 1). No i analogicznie jak wyżej mamy fałsz więc nic nie robimy, - ściągamy ze stosu a (czyli to co jest na górze), sprawdzamy czy priorytet na stosie priorytetów (czyli ściągamy tą daną ze stosu) dla
ajest mniejszy (<) od 1. Mamy 5 < 1 więc fałsz.
- ściągamy ze stosu
- na stos wrzucamy
a+b*c/(d-e)^fi kończymy wykonywanie programu.
Nasz wynik przy minimalnej liczbie nawiasów:
a+b*c/(d-e)^fKod
Znając już działanie całego algorytmu możemy zacząć pisać kod źródłowy. Zacznijmy na początku od funkcji zwracającej priorytety.
Kod funkcji pobierzPriorytet() napisanej w Javie, zwracającej priorytet danego znaku:
static int pobierzPriorytet(String znak)
{
if(znak.equals("+") || znak.equals("-"))
return 1;
else if(znak.equals("*") || znak.equals("/"))
return 2;
else if(znak.equals("^"))
return 3;
else if(znak.equals("~")) //minus unarny (np. -4, -5 zmienia znak liczby)
return 4;
else if(znak.charAt(0) >= 'a' && znak.charAt(0) <= 'z') //dla uproszczenia przyjmujemy, że liczby będą reprezentować litery
return 5;
return 0; //jeśli doszło do błędu
}Jak widać nie ma tutaj nic skomplikowanego, po prostu zwracamy odpowiedni priorytet w zależności od podanego jako argument znaku.
Funkcja konwertująca wyrażenia z ONP do INF z minimalną liczbą nawiasów:
static void doINF(String[] wejscie)
{
stackArray stos = new stackArray(wejscie.length);
stackArrayInt stosPriorytetow = new stackArrayInt(wejscie.length);
String tmp = "";
int liczbaOperandow = 0, liczbaOperatorow = 0;
for(int j = 0;j<wejscie.length;j++)
{
if(!wejscie[j].equals("(") && !wejscie[j].equals(")"))
if(wejscie[j].charAt(0) >= 'a' && wejscie[j].charAt(0) <= 'z')
{
stos.push(wejscie[j]);//element jest operandem
stosPriorytetow.push(pobierzPriorytet(wejscie[j]));
liczbaOperandow++;
}
else
{
tmp = "";
if(!wejscie[j].equals("~"))
{
liczbaOperatorow++;
if(stosPriorytetow.top() <= pobierzPriorytet(wejscie[j]))
tmp = "(" + stos.pop() + ")";
else
tmp = stos.pop();
stosPriorytetow.pop();
if(stosPriorytetow.top() < pobierzPriorytet(wejscie[j]))
tmp = "(" + stos.pop() + ")" + wejscie[j] + tmp;
else
tmp = stos.pop() + wejscie[j] + tmp;
stosPriorytetow.pop();
}
else
{
if(stosPriorytetow.top() < pobierzPriorytet(wejscie[j]))
tmp = wejscie[j] + "(" + stos.pop() + ")";
else
tmp = wejscie[j] + stos.pop();
stosPriorytetow.pop();
}
stos.push(tmp);
stosPriorytetow.push(pobierzPriorytet(wejscie[j]));
}
}
if(liczbaOperandow - 1 == liczbaOperatorow)
System.out.println("<INF>" + stos.pop());
else
System.out.println("Podałeś błędne dane!");
}Funkcja main:
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String dane = "";
dane = s.nextLine();
String tab[] = new String[256];
for(int x = 0;x<dane.length();x++)
tab[x] = Character.toString(dane.charAt(x));
int l = 0;
for(int j = 0;j<tab.length;j++)
if(tab[j] != null)
l++;
String wejscie[] = new String[l]; //musimy mieć tablicę dokładnie takiej samej długości jak wprowadzony string
for(int j = 0;j<l;j++)
wejscie[j] = tab[j];
doINF(wejscie); //konwersja
}Do tego dorobić trzeba jeszcze stos, co szczegółowo opisałem w artykule „Abstrakcyjne struktury danych: Stos„.
Jeżeli ktoś miałby z tym problem to poniżej publikuję cały kod:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String dane = "";
dane = s.nextLine();
String tab[] = new String[256];
for(int x = 0;x<dane.length();x++)
tab[x] = Character.toString(dane.charAt(x));
int l = 0;
for(int j = 0;j<tab.length;j++)
if(tab[j] != null)
l++;
String wejscie[] = new String[l]; //musimy mieć tablicę dokładnie takiej samej długości jak wprowadzony string
for(int j = 0;j<l;j++)
wejscie[j] = tab[j];
doINF(wejscie); //konwersja
}
static int pobierzPriorytet(String znak)
{
if(znak.equals("+") || znak.equals("-"))
return 1;
else if(znak.equals("*") || znak.equals("/"))
return 2;
else if(znak.equals("^"))
return 3;
else if(znak.equals("~")) //minus unarny (np. -4, -5 zmienia znak liczby)
return 4;
else if(znak.charAt(0) >= 'a' && znak.charAt(0) <= 'z') //dla uproszczenia przyjmujemy, że liczby będą reprezentować litery
return 5;
return 0; //jeśli doszło do błędu
}
static void doINF(String[] wejscie)
{
stackArray stos = new stackArray(wejscie.length);
stackArrayInt stosPriorytetow = new stackArrayInt(wejscie.length);
String tmp = "";
int liczbaOperandow = 0, liczbaOperatorow = 0;
for(int j = 0;j<wejscie.length;j++)
{
if(!wejscie[j].equals("(") && !wejscie[j].equals(")"))
if(wejscie[j].charAt(0) >= 'a' && wejscie[j].charAt(0) <= 'z')
{
stos.push(wejscie[j]);//element jest operandem
stosPriorytetow.push(pobierzPriorytet(wejscie[j]));
liczbaOperandow++;
}
else
{
tmp = "";
if(!wejscie[j].equals("~"))
{
liczbaOperatorow++;
if(stosPriorytetow.top() <= pobierzPriorytet(wejscie[j]))
tmp = "(" + stos.pop() + ")";
else
tmp = stos.pop();
stosPriorytetow.pop();
if(stosPriorytetow.top() < pobierzPriorytet(wejscie[j]))
tmp = "(" + stos.pop() + ")" + wejscie[j] + tmp;
else
tmp = stos.pop() + wejscie[j] + tmp;
stosPriorytetow.pop();
}
else
{
if(stosPriorytetow.top() < pobierzPriorytet(wejscie[j]))
tmp = wejscie[j] + "(" + stos.pop() + ")";
else
tmp = wejscie[j] + stos.pop();
stosPriorytetow.pop();
}
stos.push(tmp);
stosPriorytetow.push(pobierzPriorytet(wejscie[j]));
}
}
if(liczbaOperandow - 1 == liczbaOperatorow)
System.out.println("<INF>" + stos.pop());
else
System.out.println("Błędne dane...");
}
}
class stackArray
{
private int maxSize;
private String[] Elem;
private int top;
public stackArray(int size)
{
maxSize = size;
Elem = new String[maxSize];
top = maxSize;
}
public void push(String x)
{
if(!isFull())
Elem[--top] = x;
}
public String pop()
{
if(isEmpty())
return "";
else
return Elem[top++];
}
public String top()
{
if ( isEmpty() )
return "";
else
return Elem[top];
}
public boolean isEmpty()
{
return (top == maxSize);
}
public boolean isFull()
{
return (top == 0);
}
}
class stackArrayInt
{
private int maxSize;
private int[] Elem;
private int top;
public stackArrayInt(int size)
{
maxSize = size;
Elem = new int[maxSize];
top = maxSize;
}
public void push(int x)
{
if(!isFull())
Elem[--top] = x;
}
public int pop()
{
if(isEmpty())
return 0;
else
return Elem[top++];
}
public int top()
{
if ( isEmpty() )
return 0;
else
return Elem[top];
}
public boolean isEmpty()
{
return (top == maxSize);
}
public boolean isFull()
{
return (top == 0);
}
}Konwersja w drugą stronę: z postaci infiksowej do ONP
Skoro umiemy już wracać z ONP do zapisu klasycznego, domknijmy temat konwersją w drugą stronę. Służy do tego algorytm stacji rozrządowej (ang. shunting-yard) Dijkstry, oparty na stosie operatorów. Czytamy wyrażenie od lewej i:
- liczbę przepisujemy od razu na wyjście,
- operator zdejmuje ze stosu operatory o priorytecie równym lub wyższym (one trafiają na wyjście), po czym sam wchodzi na stos,
- nawias otwierający zawsze wchodzi na stos, a zamykający zdejmuje wszystko aż do niego (nawiasy znikają),
- na końcu opróżniamy stos na wyjście.
Prześledźmy to na wyrażeniu 2 + 3 * (7 - 4):
| Wejście | Stos | Wyjście (ONP) |
|---|---|---|
| 2 | 2 | |
| + | + | 2 |
| 3 | + | 2 3 |
| * | + * | 2 3 |
| ( | + * ( | 2 3 |
| 7 | + * ( | 2 3 7 |
| – | + * ( – | 2 3 7 |
| 4 | + * ( – | 2 3 7 4 |
| ) | + * | 2 3 7 4 – |
| koniec | 2 3 7 4 – * + |
Wynik: 2 3 7 4 - * +. Nawiasy zniknęły, a kolejność działań przetrwała w samym układzie symboli.
Obliczanie wartości wyrażenia ONP
Największa zaleta ONP: wartość liczy się jednym przejściem, znów ze stosem, tym razem liczb. Liczba wchodzi na stos, a operator zdejmuje DWIE liczby, wykonuje działanie i odkłada wynik:
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static double obliczOnp(String wyrazenie) {
Deque<Double> stos = new ArrayDeque<>();
for (String symbol : wyrazenie.split(" ")) {
switch (symbol) {
case "+": case "-": case "*": case "/":
double b = stos.pop(); // UWAGA: b przed a
double a = stos.pop(); // (kolejnosc wazna dla - i /)
if (symbol.equals("+")) stos.push(a + b);
if (symbol.equals("-")) stos.push(a - b);
if (symbol.equals("*")) stos.push(a * b);
if (symbol.equals("/")) stos.push(a / b);
break;
default:
stos.push(Double.parseDouble(symbol));
}
}
return stos.pop();
}
public static void main(String[] args) {
System.out.println(obliczOnp("2 3 7 4 - * +")); // 11.0, czyli 2 + 3 * (7 - 4)
}
}To dokładnie dlatego ONP pokochały kompilatory i kalkulatory (słynna seria HP): maszyna nie musi rozumieć priorytetów ani nawiasów, wystarczy jej stos i jedno przejście po symbolach.
Python:
def oblicz_onp(wyrazenie):
stos = []
for symbol in wyrazenie.split():
if symbol in "+-*/":
b = stos.pop() # UWAGA: b przed a
a = stos.pop()
if symbol == "+": stos.append(a + b)
if symbol == "-": stos.append(a - b)
if symbol == "*": stos.append(a * b)
if symbol == "/": stos.append(a / b)
else:
stos.append(float(symbol))
return stos.pop()
print(oblicz_onp("2 3 7 4 - * +")) # 11.0C#:
using System;
using System.Collections.Generic;
using System.Globalization;
class Program
{
static double ObliczOnp(string wyrazenie)
{
var stos = new Stack<double>();
foreach (string symbol in wyrazenie.Split(' '))
{
if (symbol is "+" or "-" or "*" or "/")
{
double b = stos.Pop(); // b przed a
double a = stos.Pop();
stos.Push(symbol switch
{
"+" => a + b,
"-" => a - b,
"*" => a * b,
_ => a / b,
});
}
else
{
stos.Push(double.Parse(symbol, CultureInfo.InvariantCulture));
}
}
return stos.Pop();
}
static void Main() => Console.WriteLine(ObliczOnp("2 3 7 4 - * +")); // 11
}


// brak komentarzy — bądź pierwszy