Odwrotna notacja polska- ONP
Odwrotna notacja polska polega na zapisie beznawiasowej symboliki rachunku (twórca to Polak, Jan Łukasiewicz) .Taki sposób zapisywania wyrażeń pozwala obliczać wyrażenia podczas jednokrotnego przeglądania znaków zapisanego wyrażenia bez potrzeby cofania się.
Na przykład działanie: (2+2)/(3*3)
W ONP ma postać: 2 2 + 3 3 * /
Przy wykorzystaniu odwrotnej notacji polskiej przydaje się struktura danych zorganizowanych w stos. W języku C# stos deklaruje się jak poniżej
Stack stos = new Stack();Należy pamiętać, że daną dostępną na stosie jest zawsze ta co ostania została do stosu wpisana (obowiązuje zasada: ostatnia wchodzi, pierwsza wychodzi). Przy obsłudze zmiennych typu Stack przydają się instrukcje:
- stos.Push(dana)- wrzuca dane na stos
- stos.Peek()- odczytaj daną ze stosu
- stos.Pop()- usuń dana ze stosu
- stos.Count- licznik danych zapisanych na stosie
Algorytm ONP
- Poniższe czynności wykonuj do momentu odczytania wszystkich wyrażeń zapisanych w ONP.
- Jeśli wczytane wyrażenie jest liczbą, to zapisz liczbę na stosie.
- Jeśli wyrażenie jest operatorem działania (+,-, idt.), to
- zdejmij element ze szczytu stosu i zapisz go w zmiennej b (druga z kolejki działań np. mianownik)
- zdejmij kolejny element ze stosu i zapisz go do zmiennej a (pierwsza z kolejki działań, np. licznik)
- wykonaj działanie (a operator b) i wrzuć wynik na stos
Po wykonaniu algorytmu, na stosie pozostanie jedna liczba będąca wynikiem zastosowania algorytmu odwrotnej notacji polskiej. Wystarczy ten wynik odczytać
Schemat algorytmu ONP
Przykładowa aplikacja desktopowa wykorzystująca algorytm ONP
Proponowany układ formatki okna głównego
Działanie aplikacji będzie wymagało zdefiniowania stosu
Wskazówka:
public partial class Form1 : Form
{
Stack stos = new Stack();
Postać funkcji zamieniającej odczytany znak wyrażenia na cyfrę
Wskazówka:
bool cyfra(char z)
{
//funkcja sprawdza czy znak jest cyfrą
//zwróć wynik testu złożonego warunku logicznego
//jak jest spełniony to PRAWDA, jak nie to FAŁSZ
return z >= '0' && z <= '9';
}
Postać funkcji sprawdzającej czy biezacy znak wyrażenia jest operatorem działania matematycznego
Wskazówka:
bool dzialanie(char z)
{
//funkcja sprawdza czy znak jest operatorem
//działania matematcznego
return z == '+' ||//dodawanie
z == '-' ||//odejmowanie
z == '*' ||//mnozenie
z == '/';//dzielenie
}
Postać funkcji czytającej liczby zapisane w wyrażeniu
Wskazówka:
float dajLiczbe(string lancuch,int id)
{
//int j = id;
//zamienia ciąg znaków na liczbę
int liczba = 0;
while(id<lancuch.Length && cyfra(lancuch[id]) && lancuch[id]!=' ')
{
//liczbe okresl na podstawie systemu pozycyjnego schematu Hornera
//odczytaj cyfre z pozycji kodu ASCII
liczba = liczba * 10 + lancuch[id] - '0';
++id;
}
return liczba;
}
Powyższe funkcje wymagane są do prawidłowego działania przedstawionego kody algorytmu odwrotnej notacji polskiej. Algorytm ONP w utworzonej aplikacji wywoływany jest w zdarzeniu Click kontrolki Button
Wskazówka:
private void button1_Click(object sender, EventArgs e)
{
string onp=textBox1.Text;
//czysc poprzednią zawartośc stosu
stos.Clear();
for(int i = 0; i < onp.Length; i++)
{
if (cyfra(onp[i]))
{
float liczba = dajLiczbe(onp, i);
//wrzuc odczytaną liczbę na stos danych
stos.Push(liczba);
//zwieksz krok o długośc znakow odczytanej liczby
i+=liczba.ToString().Length;
}
else
if (dzialanie(onp[i]))
{
if (stos.Count < 2)
{
MessageBox.Show("To nie jest wyrażenie ONP",
"Komunikat",
MessageBoxButtons.OK,
MessageBoxIcon.Error);
return;
}
float b = (float)stos.Peek();
stos.Pop();//usuń pobraną
float a = (float)stos.Peek();
stos.Pop();//usuń pobraną
//wrzuc biezacy wynik obliczeń
stos.Push(oblicz(a, b, onp[i]));
}//koniec if dzialanie
}
MessageBox.Show(((float)stos.Peek()).ToString(),
"Wynik",
MessageBoxButtons.OK,
MessageBoxIcon.Information);
}
Pełny kod programu:
Form1.cs:
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace _24AlgONP
{
public partial class Form1 : Form
{
Stack stos = new Stack();
bool cyfra(char z)
{
//funkcja sprawdza czy znak jest cyfrą
//zwróc wynik testu złożonego warunku logicznego
//jak jest spełniony to PRAWDA, jak nie to FAŁSZ
return z >= '0' && z <= '9';
}
bool dzialanie(char z)
{
//funkcja sprawdza czy znak jest operatorem
//działania matematcznego
return z == '+' ||//dodawanie
z == '-' ||//odejmowanie
z == '*' ||//mnozenie
z == '/';//dzielenie
}
float oblicz(float a,float b,char z)
{
switch (z)
{
case '+':return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
return 0;
}
float dajLiczbe(string lancuch,int id)
{
//int j = id;
//zamienia ciąg znaków na liczbę
int liczba = 0;
while(id<lancuch.Length && cyfra(lancuch[id]) && lancuch[id]!=' ')
{
//liczbe okresl na podstawie systemu pozycyjnego schematu Hornera
//odczytaj cyfre z pozycji kodu ASCII
liczba = liczba * 10 + lancuch[id] - '0';
++id;
}
return liczba;
}
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
string onp=textBox1.Text;
//czysc poprzednią zawartośc stosu
stos.Clear();
for(int i = 0; i < onp.Length; i++)
{
if (cyfra(onp[i]))
{
float liczba = dajLiczbe(onp, i);
//wrzuc odczytaną liczbę na stos danych
stos.Push(liczba);
//zwieksz krok o długośc znakow odczytanej liczby
i+=liczba.ToString().Length;
}
else
if (dzialanie(onp[i]))
{
if (stos.Count < 2)
{
MessageBox.Show("To nie jest wyrażenie ONP",
"Komunikat",
MessageBoxButtons.OK,
MessageBoxIcon.Error);
return;
}
float b = (float)stos.Peek();
stos.Pop();//usuń pobraną
float a = (float)stos.Peek();
stos.Pop();//usuń pobraną
//wrzuc biezacy wynik obliczeń
stos.Push(oblicz(a, b, onp[i]));
}//koniec if dzialanie
}
MessageBox.Show(((float)stos.Peek()).ToString(),
"Wynik",
MessageBoxButtons.OK,
MessageBoxIcon.Information);
}
}
}
