:~$ newsletter --subscribe
cat ~/artykuly/algorytmy/minimalna-liczba-nawiasow-przy-przeksztalcaniu-wyrazen-z-odwrotnej-notacji-polskiej-onp.md

Minimalna liczba nawiasów przy przekształcaniu wyrażeń z „Odwrotnej Notacji Polskiej” (ONP)

„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)*5

To 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 arytmetycznePriorytet
+ (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:

ONP-Drzewo-priroytetow

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:

  1. a, b oraz c idzie na stos z priorytetami 5 (dla każdego, czyli na stosie z priorytetami mamy 3 pozycje po 5),
  2. wczytujemy na wejściu mnożenie (*), mamy priorytet 2 (bo mnożenie), wykonujemy więc następujące operacje:
    1. ś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) dla c jest mniejszy lub równy (<=) od 2 (dla mnożenia priorytet to 2). W tym przypadku mamy fałsz czyli nic nie robimy,
    2. ś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.
  3. 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,
  4. d oraz e idzie na stos z priorytetami 5,
  5. wczytujemy na wejściu minus (-), mamy priorytet 1 (bo odejmowanie), wykonujemy więc następujące operacje:
    1. ś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) dla e jest 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,
    2. ś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) dla d jest mniejszy (<) od 1 (dla odejmowania priorytet to 1). Znowu analogicznie mamy fałsz czyli po prostu nic nie robimy.
  6. 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,
  7. na stos idzie f z priorytetem 5,
  8. wczytujemy na wejściu potęgowanie (^), mamy priorytet 3 (bo potęgowanie), wykonujemy więc następujące operacje:
    1. ś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 f jest 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,
    2. ś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) dla d-e jest mniejszy (<) od 3. I tutaj uwaga: mamy coś takiego 1<3 czyli „prawdę”! Bierzemy więc w nawias d-e: (d-e).
  9. 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,
  10. wczytujemy na wejściu dzielenie (/), mamy priorytet 2 (bo dzielenie), wykonujemy więc następujące operacje:
    1. ś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)^f jest 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,
    2. ś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) dla b*c jest mniejszy (<) od 2. Mamy 2 < 2 więc fałsz.
  11. 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,
  12. wczytujemy na wejściu dodawanie (+), mamy priorytet 1 (bo dodawanie), wykonujemy więc następujące operacje:
    1. ś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) dla b*c/(d-e)^f jest 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,
    2. ś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 a jest mniejszy (<) od 1. Mamy 5 < 1 więc fałsz.
  13. na stos wrzucamy a+b*c/(d-e)^f i kończymy wykonywanie programu.

Nasz wynik przy minimalnej liczbie nawiasów:

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

Kod

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:

java
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:

java
    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:

java
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:

java
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:

  1. liczbę przepisujemy od razu na wyjście,
  2. operator zdejmuje ze stosu operatory o priorytecie równym lub wyższym (one trafiają na wyjście), po czym sam wchodzi na stos,
  3. nawias otwierający zawsze wchodzi na stos, a zamykający zdejmuje wszystko aż do niego (nawiasy znikają),
  4. na końcu opróżniamy stos na wyjście.

Prześledźmy to na wyrażeniu 2 + 3 * (7 - 4):

WejścieStosWyjście (ONP)
22
++2
3+2 3
*+ *2 3
(+ * (2 3
7+ * (2 3 7
–+ * ( –2 3 7
4+ * ( –2 3 7 4
)+ *2 3 7 4 –
koniec2 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:

java
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:

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

C#:

csharp
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
}
udostępnij: ·
Łukasz Dudziński
Łukasz Dudziński · założyciel i autor
Pasjonat informatyki, a zwłaszcza programowania. Zwariowany maniak na tle nowych technologii oraz komputerów. W wolnych chwilach bloger... więcej-o-mnie →
ls ~/artykuly/powiazane --limit 3
komentarze --count 0
rss dla komentarzy →

// brak komentarzy — bądź pierwszy

dodaj-komentarz

Komentarze są moderowane. Podane dane przetwarzamy wyłącznie w celu publikacji komentarza (polityka prywatności).