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

„Odwrotna Notacja Polska” (ONP, ang. Reverse Polish Notation, RPN) to poprostu 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ń.

Spis treści:

1. Algorytm minimalnej liczby nawiasów przy konwersji z ONP do INF,
2. Przykład praktyczny (pełny opis algorytmu konwersji z ONP do INF),
3. Kod źródłowy.

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.

Strony: 1 2 3 4

Algorytmy, INF, minimalna liczba nawiasów, Minimalna liczba nawiasów przy konwersji z ONP, Odwrotna Notacja Polska, ONP, Programowanie, Reverse Polish notation