Odwrotna Notacja Polska

---

Odwrotna notacja polska w skrócie ONP jest algorytmem stosowanym do zapisu wyrażeń arytmetycznych bez użycia nawiasów. Powstał on na podstawie notacji polskiej stworzonej przez polskiego matematyka Jana Łukasiewicza.

Zasada działania

Zasada działania algorytmu jest bardzo prosta i opiera się na strukturze zwanej stosem.

Algorytm

1. Poniższe czynności wykonuj do momentu wyczerpania wszystkich wyrażeń zapisanych w ONP.
2. Jeśli wczytane wyrażenie jest liczbą, to wrzuć ją na stos.
3. Jeśli wyrażenie jest operatorem, to
   1. zdejmij element ze szczytu stosu i zapisz go w zmiennej a
   2. zdejmij kolejny element ze stosu i zapisz go do zmiennej b
   3. wykonaj działanie b operator a i wrzuć wynik na stos (zwróć uwagę, że pierwszą liczbą działania jest liczba zapisana w zmiennej b).

Po wykonaniu algorytmu, na stosie pozostanie jedna liczba będąca wynikiem zastosowania algorytmu odwrotnej notacji polskiej.

Przykład 1

Wyznaczymy wartość wyrażenia zapisanego w ONP:

2 3 5 - 3 * -

Kolejne elementy wyrażenia ONP	Operacja	Zawartość stosu
2	Wrzuć liczbę 2 na stos	2
3	Wrzuć liczbę 3 na stos	2 3
5	Wrzuć liczbę 5 na stos	2 3 5
-	Zdejmij liczbę 5 ze stosu, następnie zdejmij liczbę 3 ze stosu, następnie wynik działania 3 - 5 wrzuć na stos	2 -2
3	Wrzuć liczbę 3 na stos	2 -2 3
*	Zdejmij liczbę 3 ze stosu, następnie zdejmij liczbę -2 ze stosu, następnie wynik działania -2 * 3 wrzuć na stos	2 -6
/	Zdejmij liczbę -6 ze stosu, następnie zdejmij liczbę 2 ze stosu, następnie wynik działania 2 - (-6) wrzuć na stos	8 (wynik)

Powyższe wyrażenie w notacji z nawiasami na postać:

2 - (3 - 5) * 3 

Przykłady

Zapis w notacji z nawiasami	Zapis w ONP	Wynik
4 - 7	4 7 -	-3
4*(2 - 8)	4 2 8 - *	-24
(2 + 4)*(4 - 6)	2 4 + 4 6 - *	-12
5*((3 - 7)*2 - 3*(5 + 1)) - 3	5 3 7 - 2 * 3 5 1 + * - * 3 -	-133

Program

//Odwrotna Notacja Polska
//algorytm.edu.pl
//wykonywane będą cztery działania: dodawanie, odejmowanie, mnożenie oraz dzielenie całkowite
#include<iostream>
#include<string>
#include<stack>
using namespace std;

int dzialanie(int a, int b, char oper)
{
	switch(oper)
	{
		case '+': 
			return a + b;
		case '-': 
			return a - b;
		case '*': 
			return a * b;
		case '/': 
			return a / b;//dzielenie całkowite
	}
	cout<<"Podano nieprawidłowy operator";
	return 0;
}
//sprawdzam, czy podany znak jest cyfrą
bool czy_cyfra(char znak)
{
	return znak >= '0' && znak <= '9';
}
//sprawdzam, czy dany znak jest jednym z czterech operatorów
bool czy_oper(char znak)
{
	return znak == '+' || znak == '-' || znak == '*' || znak == '/';
}

//zamiana podłańcucha na liczbę
int str_to_int(string a, int &poz) 
{
	int liczba = 0;
	while(poz < a.size() && czy_cyfra(a[poz]))
	{
		//schemat Hornera
		liczba = liczba * 10 + a[poz] - '0';
		++poz;
	}
	--poz;
	return liczba;
}

int main()
{
	string ONP;
	
	cout<<"Wprowadź wyrażenie zapisane w ONP: ";
	getline(cin, ONP);
	stack<int> stos;
	int a, b;
	
	//analizujemy wszystkie znaki, aby wyłuskać liczby i operatory
	for(int i = 0;i < ONP.size(); i++)
	{
		if(czy_cyfra(ONP[i])) //jeśli wykryjesz cyfrę, 
			stos.push((str_to_int(ONP, i))); //to zamień ją oraz kolejne na liczbę i wrzuć na stos
		else
			if(czy_oper(ONP[i])) //jeśli wykryjesz operator, to wykonaj odpowiednie działanie
			{
				if(stos.size() < 2) //gdy jest za mało liczb na stosie
				{
					cout<<"Niepoprawne wyrażenie ONP";
					return 0;
				}
				a = stos.top();	//pobierz pierwszą liczbę ze stosu
				stos.pop();	//usuń tę liczbę ze stosu
				b = stos.top();	//pobierz drugą liczbę ze stosu
				stos.pop();	//usuń tę liczbę ze stosu
				stos.push(dzialanie(b, a, ONP[i])); //wrzuć na stos wynik działania liczba b operator liczba a
			}
	}
	//jeśli ostatecznie na stosie będzie mniej lub więcej niż jeden element
	if(stos.size() != 1)
	{
		cout<<"Niepoprawne wyrażenie ONP";
		return 0;
	}
	cout<<"Wynik działania "<<ONP<<" : "<<stos.top();
	return 0;
}

Komentarz do programu

Do wczytania wyrażenia zapisanego w ONP, użyliśmy funkcji getline, która wczytuje cały wiersz, wraz z białymi znakami, do zmiennej typu string. Skorzystaliśmy z gotowego STL'owego stosu stack <int> stos;.