Informacje o nowych artykułach oraz akcjach edukacyjnych prosto na Twojej skrzynce e-mail!

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:

(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

Spodobało się?

Jeśli tak, to zarejestruj się do newslettera aby otrzymywać informacje nowych artykułach oraz akcjach edukacyjnych. Gwarantuję 100% satysfakcji i żadnego spamowania!

, , , , , , ,

Dodaj komentarz

Odpowiedz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *

Pin It on Pinterest