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

programming-593312_1920

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:

To samo wyrażenie w ONP:

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

, , , , , , ,