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

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 sosie 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 sosie 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 sosie 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 d-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

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