Artykuł prezentuje reguły postępowania przy obliczaniu wartości wyrażeń zapisanych w ONP oraz sposób przekształcania wyrażeń na ONP
Reguły stosowane przy przekształcaniu WN na ONP z wykorzystaniem stosu.
- Czytaj z wejścia do element.
- Jeśli element jest liczbą, to Prześlij element na wyjście.
- Jeśli element to '=', to Prześlij na wyjście '='.
- Jeśli element to '(', to Dopisz '(' do stosu.
- Jeśli element to ')', to Dopóki na stosie jest element różny od '(', przesyłaj operator ze stosu na wy. Usuń '(' ze stosu.
- Jeżeli element to operator matematyczny to Dopóki na stosie jest operator o wyższym lub równym priorytecie od elementu,
- przesyłaj operator ze stosu na wyjście, następnie dopisz element do stosu.
Reguły stosowane przy obliczaniu wartości wyrażenia w ONP.
- Czytaj element z wejścia.
- Jeśli element jest liczbą to umieść go na stosie.
- Jeśli element jest operatorem matematycznym, to pobierz ze stosu dwie liczby a i b, wykonaj nad liczbami a i b operację określoną przez element i umieść wynik na stosie.
- Jeśli element jest znakiem '=', to prześlij na wyjście zawartość wierzchołka stosu.
Praktyka
Przekształć poniższe wyrażenia z postaci nawiasowej na ONP oraz z ONP do postaci nawiasowej.
Zbuduj wyrażenie w postaci ONP (z ang. Reverse Polish Notation) dla następujących wyrażeń:
a. a-b*c+d-e*f+g*h
b. 2-(a*3-(4+a*c-b))
c. ((3+4)*5-(3+1))/2
d. ((3-2)^3*(3+3)*3)/2
Zbuduj wyrażenie w postaci infiksowej (z nawiasami) dla następujących wyrażeń w postaci ONP (posfiksowej):
a. x y – x y x - - y - -
b. 1 2 3 4 a / b / - c / - -
c. 5 4 + 5 + 4 5 + *
d. 3 3 3 + * 6 9 3 2 + / - +