Matura z informatyki - rozwiązania zadań  

Algorytmy

Odwrotna notacja polska

Obliczanie wartości

ONP pozwala na konstrukcję bardzo prostego algorytmu obliczania wartości wyrażenia. Polega on na tym, że jeśli w w wyrażeniu czytanym od lewej pojawia się operand (liczba), to wkładany jest on na stos, natomiast jeśli pojawia się operator, to ze stosu zdejmowane są jego argumenty, a na stos trafia wynik działania. Ostateczny wynik jest odczytywany ze stosu.

Przykładowo dla wyrażenia ‘2 3 4 + *’, zmiany zawartości stosu wyglądają następująco:

2 <= 2
2 3 <= 3
2 3 4 <= 4
2 7 <= + (3 + 4)
14 <= * (2 * 7)

Wynik: 14

Poniżej przykładowy kod, który oblicza wartość wyrażenia zapisanego w ONP:

#include <iostream>

using namespace std;
const int ROZMIAR = 100; 

int main()
{
  int stos[ROZMIAR], wskaznik = 0, i, x, y;
  string w; 
  
  cout << "Podaj wyrazenie zapisane w postaci ONP (np. 48+=)\n";	
  cin >> w;
	
  for (i = 0; i < w.size(); i++)       
  {
    if(w[i] == '=') 
	 break; 

    else if(isdigit(w[i])) 
     stos[wskaznik++] = w[i]-'0';  

    else
    {                  
      y = stos[--wskaznik];      
      x = stos[--wskaznik];
      switch(w[i])    
      {
        case '+' : x += y; 
		 break;
        case '-' : x -= y; 
		 break;
        case '*' : x *= y; 
		 break;
        case '/' : x /= y; 
		 break;
      }
      stos[wskaznik++] = x;   
    }
  }
  cout << stos[--wskaznik] << endl;
  return 0;
} 
© 2017 MaturaInformatyka.pl || Kontakt: admin(malpa)maturainformatyka.pl

Search