Parser wyrażeń arytmetycznych dla dowolnej liczby zmiennych dla C++ i liczb rzeczywistych (double, long double).
Inaczej: ewaluator wyrażeń matematycznych, parser wzoru funkcji, parser matematyczny, analizator, parser wyrażeń matematycznych.
Jest to biblioteka DLL do obliczania wartości z pobieranych w postaci teksu wyrażeń matematycznych w czasie wykonywania programu. Zawiera w sobie analizator składniowy. Parser ten jest w postaci bardzo wygodnej w implementacji klasy. Można go wygodnie stosować przy tworzeniu własnych programów, pobierających od użytkownika funkcje - wyrażenia arytmetyczne o dowolnej liczbie zmiennych i późniejszym bardzo szybkim wyznaczaniu ich wartości bez każdorazowego przetwarzania podanego ciągu znaków.
Pełna funkcjonalność: sprawdzanie gramatyki wyrażenia, szczegółowe informacje o wszelkich możliwych błędach w wyrażeniu lub obliczaniu wyrażenia, ze wskazaniem na konkretny atom i niesamowita szybkość działania!
* DEFINICJE:
- atom (token, leksem) - atom leksykalny, jednostka leksykalna / składniowa (znak alfabetu lub ciąg takich znaków, cyfra lub liczba, znak działania algebraicznego) - pojedynczy element wyrażenia
np. +, -, (, 135, !, sin, średnik
Typy atomów:
- stała - operand, np. PI, E
- liczba - operand, np. 134.56, 10011b
- zmienna - operand, np. X, Y (o ile takie nazwy: X,Y podano przy tworzeniu obiektu)
- operatory: '_', '+', '-', '*', '/', '^', '!', '(', ')', ';'
- funkcja jednoargumentowa, np. sin(x), sort(x), ln(x), abs(x)
- funkcja dwuargumentowa, np. log(x;y), mod(x;y)
- funkcja trójargumentowa, np. pmod(b;n;m)
- funkcja czteroargumentowa, np. rangew(x;a;b;y)
Postacie zapisów operacji na argumentach:
- funkcja prefix(owa) gdy nazwa funkcji występuje przed jej argumentami, np.: sin(45), ew. -7, +5
- funkcja postfix(owa) nazwa funkcji występuje za jej agrumentami, np.: 25!
- funkcja infix(owa) nazwa funkcji występuje między jej agrumentami, np.: 1+2, 3*6, 8/4
- operand symbol terminalny (końcowy), z którego bezpośrednio jest obliczana wartość. Są nimi: stała, liczba, zmienna.
- stały operand stała lub liczba (lub obliczone stałe wyrażenie)
- operator funkcja w postaci infiksowej lub postfiksowej oraz symbole pomocnicze: '(', ')' , ';'
* ZAŁOŻENIA, WYMAGANIA:
- funkcja prefix:
- nazwa zaczyna się literą; może składać się tylko ze znaków alfanumerycznych;
- po nazwie musi być zaraz nawias otwierający '(', czyli nie może być np. spacja przed nawiasem;
- nazwa może pokrywać się z nazwą liczby lub zmiennej (np. AFFh-liczba, AFFh()-funkcja; X-zmienna, X()-funkcja)
- długość nazwy minimum 2 znaki
- argumenty funkcji wielo argumentowych oddzielamy średnikiem ';', np. pmod(a;b;c); nie przecinkiem, gdyż przecinek i kropka mają te same znaczenie w różnych krajach
- liczba: ciąg alfanumeryczny, po którym występuje znak nie-alfanumeryczny (spacja + - / itp.) lub kończy się wyrażenie
- nie może zawierać spacji.
- jeśli na końcu nie ma b lub o lub h (czyli jest to liczba dziesiętna), to w ŚRODKU może być '.' lub ',' (nie na początku!), tzn. "przecinek" w liczbie dziesiętnej można zapisać przecinkiem lub kropką (ze względu na różne koncepcje zapisu w różnych krajach)
- jeśli na końcu jest b, to musi być ciąg tylko złożony z cyfr {0,1} (zapis binarny)
- jeśli na końcu o, to musi być tylko złożony z cyfr {0..7} (zapis ósemkowy)
- jeśli na końcu h, to musi być tylko złożony z cyfr {0..9} oraz {a..f} lub {A..F} (zapis szesnastkowy)
(-na końcu rad oznacza radiany czyli 1rad = 1*180/PI jeszcze nie zaimplementowane
Przykłady:
-Poprawne zapisy:
"f01h"; " 002.0015 "; "00.000"; "45h"; "00101b"
-Błędne zapisy:
".12"; "12.6k"; "1."; "100201b"; "1A h"; "h"; "b"; "o"
- zmienna: ciąg alfanumeryczny zaczynający się literą, o nieograniczonej długości;
reprezentuje przez swoją nazwę jakąś wartość zmiennej zadeklarowanej w programie;
-nie mogą się rozpoczynać od b, o, h
-nie mogą być zmienne o nazwach np. AFFh, AfBh czyli nazwa nie może kończyć się na 'h', bo jest konflikt z zapisem liczb hex
np. x, ZmiennaY, z1
- stała: ciąg alfanumeryczny zaczynający się literą o nieograniczonej długości; może posiadać znak '_' (podkreślenie), np. M_PI, NN
* Założenia:
- nazwy funkcji infiksowych i postfixowych: pojedynczy znak nie-alfanumeryczny, np. !, +, /
* MOŻLIWOŚCI / WŁASNOŚCI:
- może być 0 zmiennych w wyrażeniu
- maksymalną długość wyrażenia ustalono na 8192 znaki
- w wyrażeniu atomy mogą być oddzielone nieograniczoną liczbą spacji
- nazwy stałych można przykryć nazwami zmiennych wtedy będą obliczane wartości zmiennych
- wartości obliczane są w arytmetyce liczb typu double
- maks. liczba cyfr po przecinku w liczbie dec: 39 (razem 41 cyfr 0,...)
- Możliwe zapisy: "b3hhhh"
* ETAPY PRZETWARZANIA WYRAŻENIA:
A. Sprawdzanie - tylko podczas tworzeniu obiektu:
- czy podano wszystkie nazwy zmiennych oraz ich adresy
- czy nazwy są odpowiednie
- I. Składni: poprawność zapisu liczb, zmiennych, funkcji; tzw. analiza leksykalna
- II. Gramatyki, tzw. analiza składniowa
- III. Przekształcenie do postaci ONP
B. Obliczanie wartości przy każdym wywołaniu WartoscWyrazenia();
* Dokładniej:
1. czy liczba zmiennych jest ? 0
2. czy:
- adresy zmiennych nie wskazują na null
- nazwy zmiennych nie są długości zerowej
- nazwa zmiennej nie zaczyna się od cyfry
- nazwa zmiennej zawiera tylko alfanumeryczne znaki
- nazwa zmiennej nie kończy się znakiem 'h'
3. czy długość wyrażenia nie jest zerowa
4. poprawność nawiasów
oczywiście można by to pominąć, bo ta niepoprawność zostałaby wykryta przy sprawdzaniu gramatyki, ale jeżeli wyrażenie jest niepoprawne z powodu nawiasów, to szybciej to zostanie wykryte - a jest to chyba jeden z częstszych błędów w wyrażeniu;
Rodzaje błędów "nawiasowych":
- nie równa liczba nawiasów '(' i ')';
- wystąpienie po sobie dwóch nawiasów w taki sposób: '()' lub ')('
5. sprawdzenie SYNTAKSY (składni), I-główna metoda, tzn.:
sprawdzanie czy podane wyrażenie składa się tylko z dozwolonych atomów;
przy okazji zapisuje odczytane atomy do własnej formy, tzn. do struktury TasmaNormal[].typ/.nr - po to aby później nie 'odszyfrowywać' znowu, przy dalszej obróbce, atomów zapisanych w wyrażeniu w postaci tekstowej ale mieć je już we własnej strukturze (formie)
6. sprawdzane GRAMATYKI wyrażenia; II-główna metoda; działa na danych z TasmaNormal[]; <Unit_Gram.cpp>
7. Tłumaczenie TasmaNormal do TasmaONP <Unit_ONP.cpp>; III-główna metoda
8. Optymalizacja wyrażenia, czyli obliczanie stałych wyrażeń:
- etap 1. np. x*4+3*2 daje x*4 + 6, ale x*4+2+3 nie da x*4+5, bo jest obliczanie od lewa do prawa: ((x*4)+2)+3
- etap 2. np. x*4+3+2 daje x*4+(3+2) czyli x*4+5; to samo dla mnożenia
Niezaimplementowane:
- etap 3. np. 6*x*y*2 dawało by 12*x*y
- etap 3a. np. 6*x*y/2 dawało by 3*x*y
- etap 4. np. (x*2+3)*4 dawało by x*8+12
itd.
9. Obliczenie wartości z sparsowanego (skompilowanego) wyrażenia; IV-główna metoda; wielokrotnie wywoływana (przy zmieniających się wartościach zmiennych)
* PUBLICZNE METODY I POLA OBIEKTU I DOSTĘPNE DANE:
- ObliczanieWyrazenia(int _LZmiennych, const char **_NazwaZmiennej, const typliczb **_AdresZmiennej, const char *_Wyrazenie, bool bOptymalizuj); //KONSTRUKTOR 2: wywołuje Parsuj()
- void Parsuj(int _LZmiennych, const char **_NazwaZmiennej, const typliczb **_AdresZmiennej, const char *_Wyrazenie, bool bOptymalizuj);
- char LWyrazenie[MaxDlWyr]; //zawiera skopiowane do własnej tablicy wyrażenie podane w konstruktorze
- char *GSB; [GdzieSyntaxBłąd] - wskazuje gdzie w wyrażeniu znaleziono błąd syntaktyczny
- int DlGram; - jak długa (liczba atomów) jest poprawna gramatycznie część wyrażenia;
- double WartoscWyrazenia(void); - oblicza wartość wyrażenia na podstawie (AdresZmiennej) aktualnych wartości zmiennych
- const char *OpisBledu, //wsk. na stały string (tzn., którego nie można zmieniać)
*OstOpisBleduW; //poprzedni ops błędu obliczania wartości
* SPRAWDZANE GRAMATYKI WYRAŻENIA Z TAŚMY
- Niedopuszczalne wyrażenia:
7!! Powinno być (7!)!
2^3^4 bo = (2^3)^4 czy = 2^(3^4)
- Dopuszczalne wyrażenia: 2!^5!; sin(3)!*7
* GRAMATYKA:
Można zbudować wiele różnych gramatyk, które będą budowały ten sam zbiór wyrażeń arytmetycznych
Może ona wyglądać np. tak:
Wyrazenie -> Skladnik
-> -Skladnik
-> +Skladnik
-> Wyrazenie +|- Skladnik ;daje 5+4+3-2+3-7-4...
Skladnik -> Czynnik;
-> Skladnik *|/ Czynnik ;daje 5*6*7/8*9/3/2...
-> Czynnik ^ Czynnik ;tu nie można: 5^6^3^... (bo =(5^6)^3 czy =5^(6^3) )
-> Czynnik !
Czynnik -> Stala
-> Liczba (dodatnia)
-> Zmienna
-> ( Wyrazenie )
-> FunPrefix1arg( Wyrazenie )
-> FunPrefix2arg( Wyrazenie ; Wyrazenie )
-> FunPrefix3arg( Wyrazenie ; Wyrazenie ; Wyrazenie )
-> FunPrefix4arg( Wyrazenie ; Wyrazenie ; Wyrazenie; Wyrażenie )
Jednak dla mojego sposobu rozbioru wyrażeń musiałem użyć innej gramatyki, tzw. lewostronnie rekursywnej;
Mój sposób polega na czytaniu / sprawdzaniu od lewej kolejnych części wyrażenia.
Obecna postać gramatyki:
Nadwyrażenie -> Wyrażenie
-> -Wyrażenie; daje np. 7 jednoargumentowe funkcje:- +
-> +Wyrażenie; daje np. +5
Wyrazenie -> Skladnik
-> Skladnik +|- Wyrażenie ; daje 5+4+3-2+3-7-4...; 5+-6; ale nie da: -5+3
Skladnik -> Nadczynnik;
-> Nadczynnik *|/ Skladnik ; daje 5*6*7/8*9/3/2...; 4^5*6/3^7
(-> Liczba Zmienna) czyli Liczba*Zmienna; daje: 2x, (abhx, 237ox tylko liczby dec)
Nadczynnik -> Sczynnik
-> Sczynnik ^ Nadczynnik
Sczynnik -> Czynnik
-> Czynnik !
Czynnik -> Stala
-> Liczba (dodatnia)
-> Zmienna
-> ( Nadwyrażenie )
-> FunPrefix1arg( Nadwyrażenie )
-> FunPrefix2arg( Nadwyrażenie ; Nadwyrażenie )
-> FunPrefix3arg( Nadwyrażenie ; Nadwyrażenie ; Nadwyrażenie )
-> FunPrefix4arg( Nadwyrażenie ; Nadwyrażenie ; Nadwyrażenie ; Nadwyrażenie )
* ALGORYTM TRANSLACJI DO ONP
Oparty jest na następującym założeniu co do priorytetów działań i nawiasów:
Pierwszeństwo obliczania operatorów od najniższego:
1: -, +
2: *, /
3: ^
4: !
5: - unarny (najwyższe pierwszeństwo)
Operatory o takim samym pierwszeństwie obliczane są w kolejności od lewej do prawej.
Ujęcie wyrażenia w nawiasy powoduje podniesienie pierwszeństwa tego wyrażenia.
Całe wyrażenie jest zawsze liczone kolejno od początku lewej strony w kierunku do prawej strony. Przykładowo - wyrażenie: x*5+2-3 jest liczone w taki sposób ((x*5)+2)-3 a nie np. (x*5)+(2-3).
Środowisko pracy algorytmu: ciąg wejściowy, stos, ciąg wyjściowy:
* Opis algorytmu:
1. pobierz atom z ciągu wejściowego.
-jeśli jest to '(' -nawias otwierający, to przepisz go na stos;
-jeśli jest to operand (stała, liczba, zmienna), to przepisz go do ciągu wyjściowego;
-jeśli jest to operator działania algebraicznego, to porównuj jego priorytet z priorytetem operatora na wierzchu stosu i zdejmuj po kolei z wierzchu stosu do ciągu wyjściowego wszystkie te operatory, które mają priorytet wyższy lub równy;
jeśli priorytet operatora na wierzchu stosu jest mniejszy lub stos jest pusty, to wpisz pobrany operator na wierzch stosu.
-jeśli jest to ')' -nawias zamykający, to przepisz ze stosu do ciągu wyjściowego wszystko do nawiasu otwierającego '(' i usuń ten nawias '(' ze stosu (bez przepisywania go do ciągu wyjściowego).
-jeśli to nazwa funkcji prefiksowej (sin, cos, log) i '('-nawias otwierający, to wpisz na stos '(' i potem tę nazwę funkcji
-jeśli jest to ';'-średnik, to spisz ze stosu wszystko do nazwy funkcji (czyli o priorytetach >0)
-jeśli jest to '!'-silnia, to przepisz go do ciągu wyjściowego (nie na stos!)
2. jeśli ciąg wejściowy jest pusty, to przepisz zawartość stosu do ciągu wyjściowego.
* DZIAŁANIE:
Aby być wydajnym w wielokrotnym obliczaniu wyrażenia, parser stosuje swoistą kompilację wyrażenia do własnej struktury, z której dopiero oblicza wartość, tzn. parser jednokrotnie przetwarza poprawność tekstu wyrażenia i po jego przetworzeniu do własnej struktury potem już liczy tylko wartość tego wyrażenia (bez ponownego sprawdzania poprawności zapisu)
* UŻYWANIE KLASY: Przykład stworzenia obiektu A.
double zm_x=2, zm_y=6; //zmienne, które będziemy zmieniać i będą one wpływać na wartość wyrażenia
char *Nazwyzmiennych[2]={"X","Y"};
double *Adresyzmiennych[2]={&zm_x, &zm_y};
ObliczanieWyrazenia A(2,Nazwyzmiennych,Adresyzmiennych,"X+Y*10",true); //utworzenie obiektu
printf("\n%s",Blad[A.NrBledu]); //sprawdzenie czy pomyślnie utworzono obiekt
if (A.NrBledu!=0) {getchar(); return;}
printf("\nWartosc=%.40f",A.WartoscWyrazenia());
printf("\n%s",Blad[A.NrBledu]);
* Rozwiązanie problemu minusa na początku Nadwyrażenia użycie dodatkowej funkcji '_';
Gdy jest '-' minus przed Nadwyrażeniem np. 7; -2*5; 4/(-3+2), to stosuję do niego specjalną jednoargumentową funkcję negującą to Nadwyrażenie
* Działanie niektórych funkcji:
- x! = (int)x! - x jest zaokrąglane do liczby całkowitej
- pow(x;y)=xy: if (y-floor(y)>0 && x<0) Błąd1; if (y<=0 && x==0) Błąd2
xx max x=143;
* Uwagi:
- Jeśli chcę nową funkcję prefixową jedno argumentową - należy ustalić jej priorytet na odpowiednio wysoki,
np $a prior.=4, bo np. 3^$7 -> 3 7 $ ^
* Zrobić:
-radiany w syntaktyce
-(! zmienić oznaczenie zapisu BIN,OCT,HEX na: 0hAFF7, 0o1234567, 0b10110 wtedy nie ma ograniczeń na nazwy zmiennych i łatwiejsze sprawdzanie liczb
(-sprawdzić i wyjaśnić jeszcze raz dokładnie: const MaxDlDec=38, MaxDlBin=127, MaxDlOct=42, MaxDlHex=31; //max il. cyfr w liczbie
-możliwość zapisu liczb dec tak: .45; .001
-możliwość zapisu: 4M_PI zamiast 4*M_PI
* HISTORIA:
- 1998 r. - pojawienie się problemu na I-roku studiów, podczas pisania programu do rysowania wykresów funkcji
- 10m-2001 - powstanie pomysłu rozwiązania problemu
- początek pisania programu: 11m-2001;
- 14d-2m-2002 -poprawki i dokumentacja
- 22d-2m-2002 -możliwość stosowania zapisów typu: 2x zamiast 2*x, (gdzie x - zmienne)
- 18,19d-11m-2002 dodanie funkcji: rand(x;y), range(x;a;b) i im podobnych oraz usuniecie paru błędów
- 21d-7m-2004 przyspieszenie obliczania wartości
- 2006-12d-26d obliczanie stałych wyrażeń etap1
* OGÓLNIE:
Rozwiązanie tego problemu jest w całości mojego pomysłu z wyjątkiem sposobu przetwarzania do ONP ale i tutaj sam wymyśliłem algorytm przetwarzania, który dodatkowo uwzględniający nawiasy i oznaczenie liczb ujemnych.
Także algorytm sprawdzania gramatyki i wymyślenie samej postaci gramatyki jest mojego autorstwa.
Zatem wszystkie potrzebne algorytmy i sposoby zrobiłem sam.
Nie wiem czy jest to najlepszy sposób i czy w ogóle jest jakiś inny na rozwiązanie w całości tego problemu, tak aby możliwe było stosowanie dowolnej liczby zmiennych i własne ich definiowanie oraz który oferowałby lepszą prędkość obliczania wartości.
Jeżeli jest jakiś lepszy pomysł, to bardzo chciałbym go poznać.
2006-12m-31d
Autor: Artur Czekalski; email ARTUR@epokaY.net
Strona główna www.epokaY.net/artur/programowane.php