Odwrotna Notacja Polska (ONP) – rewolucyjne uporządkowanie obliczeń matematycznych➕➖✖️➗

Odwrotna Notacja Polska (ONP) – Jest to sposób zapisu wyrażeń matematycznych, który między innymi eliminuje potrzebę nawiasów do określania kolejności operacji, co sprawia, że jest idealny do użycia w programowaniu i analizie danych. Ta metoda, choć może wydawać się nieintuicyjna na pierwszy rzut oka, oferuje szereg zalet w obliczeniach i implementacji algorytmów.

Odwrotna Notacja Polska – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest Odwrotna Notacja Polska?
• Jak się oblicza Odwrotną Notację Polską?
• Jakie ma zastosowanie Odwrotna Notacja Polska?
• Jak w Javie wygląda implementacja ONP?

Odwrotna Notacja Polska – historia

Odwrotna Notacja Polska (ONP), znana także jako notacja postfiksowa, została wprowadzona przez australijskiego naukowca Charlesa Leonarda Hamblina w latach 50. XX wieku. Metoda ta jest odmianą notacji polskiej, wynalezionej przez polskiego logika Jana Łukasiewicza w 1924 roku, która używa formatu prefiksowego, gdzie operator jest umieszczany przed operandami (np. + 3 4). W przeciwieństwie do tego ONP umieszcza operator po operandach (np. 3 4 +).

Odwrotna Notacja Polska – jak to obliczyć?

Aby obliczyć wyrażenie zapisane w notacji postfiksowej, wykonujesz kroki w kolejności, używając stosu:

• Umieść Operand na Stosie: Każdą liczbę umieszczasz na stosie, gdy ją napotkasz.
• Wykonaj Operację: Gdy napotkasz operator, zdejmujesz ze stosu odpowiednią liczbę operandów (zwykle dwa dla binarnych operatorów jak +, –, *, /), wykonujesz operację, a wynik z powrotem umieszczasz na stosie.
• Wynik Końcowy: Po przetworzeniu całego wyrażenia, na stosie pozostaje jedna wartość — wynik końcowy operacji.

➡ ZOBACZ 👉: Stos (Stack)

Odwrotna Notacja Polska – rozwiązanie

Aby rozwiązać wyrażenie w Odwrotnej Notacji Polskiej (ONP) 2 3 * 4 5 * +, postępujemy zgodnie z regułami obliczania, używając stosu do przechowywania tymczasowych wyników. Oto kroki:

1. Umieść 2 na stosie:
   • Stos: [2]
2. Umieść 3 na stosie:
   • Stos: [2, 3]
3. Napotykasz operator * (mnożenie), więc zdejmujesz dwa ostatnie liczby ze stosu (3 i 2), mnożysz je i wynik umieszczasz z powrotem na stosie:
   • Operacja: 2 * 3 = 6
   • Stos: [6]
4. Umieść 4 na stosie:
   • Stos: [6, 4]
5. Umieść 5 na stosie:
   • Stos: [6, 4, 5]
6. Napotykasz kolejny operator * (mnożenie), więc znowu zdejmujesz dwa ostatnie liczby ze stosu (5 i 4), mnożysz je i wynik umieszczasz z powrotem na stosie:
   • Operacja: 4 * 5 = 20
   • Stos: [6, 20]
7. Napotykasz operator + (dodawanie), więc zdejmujesz dwa ostatnie liczby ze stosu (20 i 6), sumujesz je i wynik umieszczasz z powrotem na stosie:
   • Operacja: 6 + 20 = 26
   • Stos: [26]

Wynik Końcowy

Na stosie pozostaje jedna liczba, 26, która jest wynikiem końcowym wyrażenia 2 3 * 4 5 * +.

To samo działanie zapisane w zwyczajnej notacji, jaką znamy ze szkoły (infiksowej) wygląda następująco: (2*3) + (4*5).

Odwrotna Notacja Polska – przykłady

Oto kilka przykładów zapisu wyrażeń.

Dodawanie i odejmowanie

notacja infiksowa: 3 + 4 − 53 + 4 − 5

⇒🇵🇱 notacja postfiksowa: 3 4 − 53 + 4 − 5 +

Mnożenie i dzielenie

notacja infiksowa: 3 * 7 * 2 / 3

⇒🇵🇱 notacja postfiksowa: 3 7 * 2 * 3 /

Wyrażenie złożone

notacja infiksowa: (3 + 4) * 5(3 + 4) * 5 / 5 – 25

⇒🇵🇱 notacja postfiksowa: 3 4 + 5 * 3 4 + * 5 * 5 / 25 –

Odwrotna Notacja Polska – zastosowanie

Odwrotna Notacja Polska (ONP), choć wydaje się być abstrakcyjnym pojęciem matematycznym, znajduje szerokie zastosowanie w praktyce i w biznesie, przede wszystkim dzięki swojej efektywności i prostocie implementacji w systemach komputerowych.

Kalkulatory i narzędzia obliczeniowe

Wiele kalkulatorów naukowych wykorzystuje ONP, ponieważ pozwala to na szybsze przetwarzanie skomplikowanych wyrażeń matematycznych bez błędów wynikających z niewłaściwego użycia nawiasów. Przykładem może być popularny kalkulator HP-12C, używany przez inżynierów i finansistów.

Programowanie i rozwój oprogramowania

• Parsowanie Wyrażeń: W programowaniu często potrzebne jest przetwarzanie i ocena wyrażeń wprowadzanych przez użytkownika. Implementacja parserów wykorzystujących ONP jest prostsza i mniej podatna na błędy, co jest szczególnie przydatne w aplikacjach wymagających dynamicznego obliczania wyrażeń matematycznych.
• Kompilatory i Interpretery: ONP jest używana w kompilatorach i interpreterach języków programowania do oceny wyrażeń. Ponieważ operacje są wykonywane zgodnie z kolejnością występowania, bez potrzeby analizowania nawiasów, proces ten jest bardziej wydajny.

Nauka algorytmów

ONP jest także cennym narzędziem dydaktycznym w nauczaniu algorytmiki i struktur danych, szczególnie w kontekście stosów i kolejek, które są fundamentem dla notacji postfiksowej.

Odwrotna Notacja Polska – implementacja

Implementacja Odwrotnej Notacji Polskiej (ONP) w Javie wymaga użycia stosu do przechowywania operandów i efektywnego przetwarzania operatorów. Poniżej znajdziesz przykładowy kod, który przetwarza wyrażenie w notacji postfiksowej i oblicza jego wynik. Przykład koncentruje się na podstawowych operacjach arytmetycznych: dodawaniu, odejmowaniu, mnożeniu i dzieleniu.

class ReversePolishNotation {
    public static int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();
        // Przetwarzanie każdego elementu w ciągu wejściowym rozdzielonego spacjami
        String[] tokens = expression.split(" ");

        for (String token : tokens) {
            // Jeśli element jest liczbą, zapisz go na stosie
            if (token.matches("\\d+")) { // Regex do sprawdzania, czy token jest liczbą
                stack.push(Integer.parseInt(token));
            } else { // Token jest operatorem
                // Operator wymaga pobrania dwóch ostatnich liczb ze stosu
                int num2 = stack.pop();
                int num1 = stack.pop();

                switch(token.charAt(0)) { // Zakładamy, że operator to pojedynczy znak
                    case '+':
                        stack.push(num1 + num2);
                        break;
                    case '-':
                        stack.push(num1 - num2);
                        break;
                    case '*':
                        stack.push(num1 * num2);
                        break;
                    case '/':
                        if (num2 != 0)
                            stack.push(num1 / num2);
                        else
                            throw new UnsupportedOperationException("Division by zero.");
                        break;
                }
            }
        }
        return stack.pop(); // Wynik końcowy znajduje się na szczycie stosu
    }

    public static void main(String[] args) {
        String expression = "2 3 * 4 5 * +"; // operandy należy odzielić od siebie spacją aby były poprawnie odczytane przez program

        int result = evaluatePostfix(expression);
        System.out.println("The result of the expression is: " + result);
    }
}

Stos jest idealny do tego zadania, ponieważ pozwala łatwo dodać i usunąć elementy w odpowiedniej kolejności. Przechodzimy przez każdy znak w wyrażeniu. Jeżeli znak jest cyfrą, przekształcamy go z char na int (odejmując wartość ‘0’ od kodu znaku) i umieszczamy na stosie. Jeśli napotkamy operator, zdejmujemy dwie ostatnie liczby ze stosu, wykonujemy operację i wynik wrzucamy z powrotem na stos. Obsługiwane operacje to dodawanie (+), odejmowanie (-), mnożenie (*) i dzielenie (/). Dzielenie przez zero jest tu wyraźnie obsłużone jako wyjątek.

Odwrotna Notacja Polska – konwerter

Konwerter z Notacji Infiksowej na Postfiksową

class InfixToPostfix {

    // Metoda zwracająca priorytet operatora
    private static int getPriority(char operator) {
        if (operator == '+' || operator == '-') {
            return 1;
        }
        if (operator == '*' || operator == '/') {
            return 2;
        }
        return 0;
    }

    // Metoda konwertująca wyrażenie infiksowe na postfiksowe
    public static String convertToPostfix(String infix) {
        StringBuilder postfix = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        boolean expectOperand = true;  // Dodane do sprawdzania, czy oczekujemy na operand

        for (int i = 0; i < infix.length(); i++) {
            char c = infix.charAt(i);

            if (Character.isDigit(c)) {
                postfix.append(c);
                if (i + 1 < infix.length() && Character.isDigit(infix.charAt(i + 1))) {
                    continue;
                } else {
                    postfix.append(' ');
                }
                expectOperand = false;  // Po dodaniu liczby oczekujemy operatora
            } else if (c == '(') {
                stack.push(c);
                expectOperand = true;  // Po '(' oczekujemy kolejnego operandu
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop());
                    postfix.append(' ');
                }
                if (stack.isEmpty()) {
                    throw new IllegalArgumentException("Mismatched parentheses in the expression.");
                }
                stack.pop();
                expectOperand = false;  // Po ')' oczekujemy operatora
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                if (expectOperand) {
                    throw new IllegalArgumentException("Missing operand before operator " + c);
                }
                while (!stack.isEmpty() && getPriority(c) <= getPriority(stack.peek())) {
                    postfix.append(stack.pop());
                    postfix.append(' ');
                }
                stack.push(c);
                expectOperand = true;  // Po operatorze oczekujemy kolejnego operandu
            }
        }

        while (!stack.isEmpty()) {
            if (stack.peek() == '(') {
                throw new IllegalArgumentException("Mismatched parentheses in the expression.");
            }
            postfix.append(stack.pop());
            postfix.append(' ');
        }
        if (expectOperand && !postfix.toString().trim().isEmpty()) {
            throw new IllegalArgumentException("Missing operand at the end of expression.");
        }

        return postfix.toString().trim();
    }
}

Metoda pomocnicza getPriority() określa priorytet operatorów matematycznych, co jest kluczowe do zarządzania kolejnością operacji podczas konwersji. Każdy znak w wyrażeniu infiksowym jest przetwarzany w pętli. Cyfry są dodawane bezpośrednio do postfix. Aby obsłużyć liczby wielocyfrowe, kod sprawdza, czy następny znak to również cyfra, zanim doda spację.

Nawiasy Otwierające ‘(’: Są umieszczane na stosie, aby wskazać początek subwyrażenia. Nawiasy Zamykające ‘)’: Powodują opróżnienie stosu z operatorów aż do napotkania nawiasu otwierającego, który jest usuwany. Operatory: Jeśli operator ma niższy lub równy priorytet do operatora na wierzchu stosu, operatory są ściągane ze stosu do wyniku. Następnie bieżący operator jest umieszczany na stosie.

Po przejściu przez wszystkie znaki, wszystkie pozostałe operatory na stosie są ściągane do wynikowego wyrażenia postfiksowego. Sprawdzanie Nawiasów: Rzuca wyjątek IllegalArgumentException, gdy nawiasy są niezbalansowane (np. brakujący ‘(’ lub ‘)’). Sprawdzanie Oczekiwanych Operandów: Rzuca wyjątek, gdy przed operatorem nie ma odpowiedniego operandu lub gdy oczekiwano na operand na końcu wyrażenia.

Konwerter z Notacji Postfiksowej na Infiksową

class PostfixToInfix {
    // Klasa pomocnicza do przechowywania wyrażeń wraz z ich priorytetem operacyjnym
    static class Expression {
        String expr;
        int precedence;

        public Expression(String expr, int precedence) {
            this.expr = expr;
            this.precedence = precedence;
        }
    }

    // Metoda zwracająca priorytet operatora
    private static int precedenceOf(char operator) {
        if (operator == '+' || operator == '-') return 1;
        if (operator == '*' || operator == '/') return 2;
        return -1;
    }

    // Metoda konwertująca wyrażenie postfiksowe na infiksowe
    public static String convertToInfix(String postfix) throws IllegalArgumentException {
        Stack<Expression> stack = new Stack<>();
        String[] tokens = postfix.split("\\s+");

        for (String token : tokens) {
            if (token.matches("\\d+")) { // Sprawdza, czy token jest liczbą
                stack.push(new Expression(token, 3));
            } else if (token.matches("[+\\-*/]")) { // Sprawdza, czy token jest operatorem
                if (stack.size() < 2) { // Sprawdza, czy na stosie są co najmniej dwa elementy
                    throw new IllegalArgumentException("Invalid Expression: Not enough operands for " + token);
                }
                Expression right = stack.pop();
                Expression left = stack.pop();

                int opPrecedence = precedenceOf(token.charAt(0));
                String leftExpr = left.expr;
                if (left.precedence < opPrecedence) {
                    leftExpr = "(" + left.expr + ")";
                }

                String rightExpr = right.expr;
                if (right.precedence < opPrecedence) {
                    rightExpr = "(" + right.expr + ")";
                }

                stack.push(new Expression(leftExpr + " " + token + " " + rightExpr, opPrecedence));
            }
        }

        if (stack.size() != 1) {
            throw new IllegalArgumentException("Invalid Expression: Mismatched operands and operators");
        }
        return stack.pop().expr; // Zwrócenie ostatniego wyrażenia ze stosu jako wynik
    }
}

Metoda convertToInfix() konwertuje wyrażenie postfiksowe na infiksowe. Wyrażenie postfiksowe jest dzielone na tokeny (liczby i operatory), które są przetwarzane jeden po drugim. Wyrażenie postfiksowe jest rozdzielane na tokeny (elementy), które są następnie przetwarzane jeden po drugim.

Dla każdego tokenu sprawdzane jest, czy jest to operand (liczba) czy operator (+, -, *, /). Gdy napotykany jest operator, zdejmowane są dwa ostatnie wyrażenia ze stosu, a następnie łączone zgodnie z priorytetem operacji. Jeśli priorytet operacji jest wyższy niż priorytet wyrażeń, dodawane są nawiasy do tych wyrażeń, aby zachować właściwą kolejność operacji matematycznych. Po przetworzeniu wszystkich tokenów, na stosie powinno zostać tylko jedno wyrażenie, które jest wynikowym wyrażeniem infiksowym.

Jeśli na stosie jest więcej lub mniej niż jedno wyrażenie, rzucony zostaje wyjątek, informujący o błędzie w podanym wyrażeniu postfiksowym.

Odwrotna Notacja Polska – podsumowanie

Odwrotna Notacja Polska oferuje wyjątkową kombinację prostoty, efektywności i szerokiego zakresu zastosowań, czyniąc ją atrakcyjnym rozwiązaniem dla wielu problemów obliczeniowych zarówno w nauce, technologii, jak i biznesie. Jej zdolność do uproszczenia procesów obliczeniowych i minimalizacji potencjalnych błędów sprawia, że jest ceniona w wielu dziedzinach, od edukacji po wysokiej stawki finansowe i techniczne aplikacje.

➡ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja