Inne artykuły

[C++] Tworzenie parsera matematycznego

[artykuł] Artykuł opisuje w jaki sposób utworzyć własny parser matematyczny w oparciu o algorytm odwrotnej notacji polskiej.

Wstęp

W językach skryptowych, takich jak np. JavaScript, znajduje się wbudowana funkcja służąca do wykonywania kodu przekazanego jej jako argument. Przykładem takiej funkcji jest eval(). Niestety, w językach nieskryptowych takiej funkcji nie zdefiniowano, więc musimy poradzić sobie sami.

Przypuśćmy, że chcemy, aby nasz program policzył wynik działania wpisanego w okienku naszego programu. Wiadomo, że z takiego okienka możemy pobrać tylko tekst, bo niestety komputer nie jest na tyle inteligentny, aby w tekście

"Ala ma kota. Oblicz: 5+10*63 Hej!"

znaleźć działanie. Co wtedy? Są dwie możliwości. Albo usiąść i rozpłakać się, albo napisać parser ;).

Jak taki parser napisać? Cóż, wszystko polega na odpowiedniej analizie tekstu. W naszym przykładzie zastosujemy prosty i dający się w miarę szybko zakodować algorytm odwrotnej notacji polskiej.

Jeśli ktoś przed chwilą przerwał czytanie i kliknął powyższy link, z pewnością wie już na czym ten algorytm polega. Jeśli jednak nie wie, jak go zakodować, albo jest zbyt leniwy na czytanie Wikipedii, będzie zmuszony przeczytać ten artykuł ;)

Struktura kodu

Na samym początku należy zdecydować, jak chcemy napisać parser. Ponieważ kod zajmuje trochę miejsca, dla własnej wygody uznałem, że najlepiej będzie wykorzystać do tego celu klasy, i właśnie na klasie będzie się opierał ten artykuł. Jeśli ktoś nie zamierza ich używać, może bezproblemowo przekonwertować kod na bezklasowy.

Na początek kod klasy:

#include <string>
#include <vector>
#include <stdlib.h>

using namespace std;

typedef enum
{
left,
right
} direction;

class math_parser
{
private:
struct oper
{
string name;
int priority;
direction dir;
float( * func )( float, float );
};

vector < oper > ops;
int op_count;
bool err;

bool IsOperator( string ch, oper * op );
vector < string > ConvertToONP( string exp );

public:
math_parser();
~math_parser();
bool AddOperator( string name, int priority, direction dir, float( * func )( float, float ) );
int Parse( string exp );
};

math_parser::math_parser()
{
err = false;
op_count = 0;
}

math_parser::~math_parser()
{
//
}

No to po kolei. Struktura oper opisuje dostępne operatory:

string name - Nazwa operatora, czyli np. "+"
int priority - priorytet operatora
direction dir - kierunek łączenia operatora
float (*func)(float, float) - wskaźnik na funkcję dla danego operatora

Dla ciekawskich, znaczenie drugiego i trzeciego argumentu opisane jest tutaj. Czwarty to wskaźnik na funkcję, która będzie wywołana w momencie obliczania wartości. ops to tablica struktur oper. op_count określa liczbę operatorów. Funkcja IsOperator() sprawdza czy dany znak nie jest czasem operatorem, a jeśli jest, do op przypisuje tenże operator. ConvertToONP() rozpoczyna wreszcie obliczanie wartości danego wyrażenia, konwertując je na ONP.

Teraz część public. Pierwszych dwóch składników wyjaśniać chyba nie muszę. AddOperator() wykorzystamy jako dodanie operatora. Parse() wywoła ConvertToONP(), a następnie obliczy daną wartość.

Oprócz tego, podałem prostego enum-a. Definuje on kierunek łączenia operatora.

Funkcje

Zaczniemy od najprostszej - AddOperator(). Kod:

bool math_parser::AddOperator( string name, int priority, direction dir, float( * func )( float, float ) )
{
oper op;
op.name = name;
op.priority = priority;
op.dir = dir;
op.func = func;
ops.push_back( op );
op_count++;
}

Jak widać, nie robi ona nic szczególnego, po prostu dodaje operator. Następnie IsOperator() i będziemy mogli brać się za pisanie właściwej części parsera.

bool math_parser::IsOperator( string ch, oper * op )
{
oper tmp = { "", - 1,( direction ) - 1, 0 };
* op = tmp;
bool IsOperator = false;
for( int i = 0; i < op_count; i++ )
{
if( ops[ i ].name == ch )
{
IsOperator = true;
* op = ops[ i ];
break;
}
}
return IsOperator;
}

Funkcja ta sprawdza w pętli, czy operator o danej nazwie jest zdefiniowany. jeśli tak, to przekazuje op wskaźnik na strukturę tego operatora. Jeśli nie, to zwróci strukturę, gdzie name będzie równy

, priority tak jak i dir równy

- 1

, a wskaźnik na funkcję func będzie wynosił

.

Jeśli ktoś doczytał do tej pory, gratuluję. Teraz bowiem zabierzemy się wreszcie za kodowanie algorytmu. Weźmy cytat z Wkipedii:

Póki zostały symbole do przeczytania wykonuj:
- Przeczytaj symbol. Jeśli symbol jest liczbą dodaj go do kolejki wyjście.
- Jeśli symbol jest funkcją włóż go na stos.
- Jeśli symbol jest znakiem oddzielającym argumenty funkcji (np. przecinek):
  - Dopóki najwyższy element stosu nie jest lewym nawiasem, zdejmij element ze stosu i dodaj go do kolejki wyjście. Jeśli lewy nawias nie został napotkany oznacza to, że znaki oddzielające zostały postawione w złym miejscu lub nawiasy są źle umieszczone.
- Jeśli symbol jest operatorem, o1, wtedy:
  - 1) dopóki na górze stosu znajduje się operator, o2 taki, że:
    - o1 jest lewostronnie łączny i jego kolejność wykonywania jest mniejsza lub równa kolejności wyk. o2, lub
    - o1 jest prawostronnie łączny i jego kolejność wykonywania jest mniejsza od o2,
    - zdejmij o2 ze stosu i dołóż go do kolejki wyjściowej i wykonaj jeszcze raz 1)
  - 2) włóż o1 na stos operatorów.
- Jeżeli symbol jest lewym nawiasem to włóż go na stos.
- Jeżeli symbol jest prawym nawiasem to zdejmuj operatory ze stosu i dokładaj je do kolejki wyjście, dopóki symbol na górze stosu nie jest lewym nawiasem, kiedy dojdziesz do tego miejsca zdejmij lewy nawias ze stosu bez dokładania go do kolejki wyjście. Teraz, jeśli najwyższy element na stosie jest funkcją, także dołóż go do kolejki wyjście. Jeśli stos zostanie opróżniony i nie napotkasz lewego nawiasu, oznacza to, że nawiasy zostały źle umieszczone.
Jeśli nie ma więcej symboli do przeczytania, zdejmuj wszystkie symbole ze stosu (jeśli jakieś są) i dodawaj je do kolejki wyjścia. (Powinny to być wyłącznie operatory, jeśli natrafisz na jakiś nawias oznacza to, że nawiasy zostały źle umieszczone.)

Zgodnie z powyższym alogrytmem, należy w pętli pobierać kolejne znaki ciągu. Kod:

vector < string > math_parser::ConvertToONP( string exp )
{
vector < string > out;
vector < string > stack;
int length = exp.size();
string ch;
string ch2;
for( int i = 0; i < length; i++ )
{
ch = exp[ i ];
if( atoi( ch.c_str() ) <= 9 &&( atoi( ch.c_str() ) > 0 || ch == "0" ) )
{
// Symbol jest cyfrą
ch2 = exp[ ++i ];
string c = ch;
while( atoi( ch2.c_str() ) <= 9 &&( atoi( ch2.c_str() ) > 0 || ch2 == "0" || ch2 == "." ) )
{
c += ch2;
ch2 = exp[ ++i ];
continue;
}
i--;
out.push_back( c );
}
else if( atoi( ch.c_str() ) <= 'z' && atoi( ch.c_str() ) >= 'a' )
{
// Symbol jest zmienną, albo funkcją
}
else if( ch == "," )
{
// Symbol jest znakiem oddzielającym argumenty funkcji
while( stack[ stack.size() - 1 ] != "(" )
{
out.push_back( stack[ stack.size() - 1 ] );
stack.pop_back();
}
}
else if( ch == "(" )
{
stack.push_back( ch );
}
else if( ch == ")" )
{
while( stack[ stack.size() - 1 ] != "(" )
{
out.push_back( stack[ stack.size() - 1 ] );
stack.pop_back();
}
stack.pop_back();
}
else
{
// Symbol jest operatorem
oper cur;
IsOperator( ch, & cur ); // Pobranie aktualnego operatora do zmiennej cur

if( stack.size() <= 0 )
{
// Nie ma żadnych operatorów na stosie
stack.push_back( ch );
continue;
}

oper op;
while( IsOperator( stack[ stack.size() - 1 ], & op ) == true ) // Dopóki na stosie znajduje się odpowiedni operator
{
if(( cur.dir ==( direction ) 0 && cur.priority <= op.priority ) ||( cur.dir ==( direction ) 1 && cur.priority < op.priority ) )
{
out.push_back( stack[ stack.size() - 1 ] );
stack.pop_back();
}
else
break;

if( stack.size() <= 0 )
{
break;
}
}
stack.push_back( ch );
}
}
while( stack.size() > 0 )
{
// Dodanie wszystkiego do wyjścia
out.push_back( stack[ stack.size() - 1 ] );
stack.pop_back();
}

return out;
}

Metoda push_back() klasy vector dodaje przekazany jej argument na szczyt tablicy, co symuluje stos i wyjście. Metoda pop_back() usuwa ostatni element tablicy. Kluczowe miejsca zostały opisane w komentarzach. Funkcja na końcu zwróci tablicę symboli znajdujących się na wyjściu.

Zauważ, że nie przeprowadzamy kontroli, czy np. nawiasy zostały poprawnie umieszczone. Dodatkowo, wprowadzenie unarnego minusa spowoduje natychmiastowe zakończenie programu. Wszystko to da się naprawić, jednak to już będzie Twoje zadanie domowe ;)

Nie wprowadziłem również obsługi zmiennych i funkcji, ponieważ zadaniem tego kursu było pokazanie jak taki parser można napisać, a nie odwalenie całej brudnej roboty. Jeśli ktoś potrzebowałby obsługi funkcji, zostawiłem zaznaczone miejsce w kodzie, gdzie taki kod powinien się znaleźć. Pamiętaj tylko, że funkcja i zmienna najczęściej mają więcej niż jeden znak, tak więc należy zastosować trik zastosowany przy sprawdzaniu liczb. Pamiętaj także, że funkcja posiada nawiasy, a zmienna nie :)

Pozostała ostatnia funkcja - Parse(). Aby ją jednak zrozumieć, potrzebny jest kolejny cytat:

Wyzeruj stos.
Dla wszystkich symboli z wyrażenia ONP wykonuj:
- jeśli i-ty symbol jest liczbą, to odłóż go na stos,
- jeśli i-ty symbol jest operatorem to:
  - zdejmij ze stosu jeden element (ozn. a),
  - zdejmij ze stosu kolejny element (ozn. b),
  - odłóż na stos wartość b operator a.
- jeśli i-ty symbol jest funkcją to:
  - zdejmij ze stosu oczekiwaną liczbę parametrów funkcji(ozn. a1...an)
  - odłóż na stos wynik funkcji dla parametrów a1...an
Zdejmij ze stosu wynik.

Kod:

int math_parser::Parse( string exp )
{
vector < string > symbols = ConvertToONP( exp );
vector < string > stack;

for( int i = 0; i < symbols.size(); i++ )
{
string sym = symbols[ i ];
oper op;
if( atoi( sym.c_str() ) > 0 || sym == "0" )
{
stack.push_back( sym );
}
else if( IsOperator( sym, & op ) )
{
string a = stack[ stack.size() - 1 ];
stack.pop_back();
string b = stack[ stack.size() - 1 ];
stack.pop_back();
float ret =( * op.func )( atof( b.c_str() ), atof( a.c_str() ) );
char buf[ 10 ];
gcvt( ret, 3, buf );
stack.push_back( buf );
}
else if()
{
// Symbol jest funkcją
}
}
string ret = "";
ret = stack[ 0 ];
return atoi( ret.c_str() );

}

Wychwytywanie błędnych wyrażeń

Należy liczyć się z tym, że użytkownik (celowo lub nie) może podać błędne wyrażenie, skutkujące wywaleniem programu. Jak znaleźć błędne wyrażenie? Oto kilka przykładów:

Występowanie 2 operatorów koło siebie
Różna liczba lewych i prawych nawiasów
Występowanie operatorów na początku lub końcu wyrażenia
Użycie unarnego minusa (-a)

Ostatni przykład nie jest błędem, przynajmniej w teorii. Jednak nasz parser nie zrozumie takiego wyrażenia. Dlatego, aby umożliwić działania na liczbach ujemnych, należy wychwytywać unarne minusy i wstawiać przed nimi 0. Kiedy minus jest unarny? Wtedy, gdy znajduje się przed liczbą (zmienną), i jest jednocześnie pierwszym znakiem wyrażenia, albo też, gdy przed nim znajduje się nawias.

Testowanie parsera

Pozostaje przetestować nasz kod:

#include <cstdlib>
#include <iostream>
#include <string>
#include <conio.h>
#include <math.h>
#include "MathParser.hpp" // Zawiera definicję klasy i jej metod

using namespace std;

float _dodawanie( float arg1, float arg2 )
{
return arg1 + arg2;
}

float _odejmowanie( float arg1, float arg2 )
{
return arg1 - arg2;
}

float _mnozenie( float arg1, float arg2 )
{
return arg1 * arg2;
}

float _dzielenie( float arg1, float arg2 )
{
return arg1 / arg2;
}

int main( int argc, char * argv[] )
{
string exp = "5*3+(6/2)-3*9";
math_parser mp;
mp.AddOperator( "+", 1,( direction ) 0, _dodawanie );
mp.AddOperator( "-", 1,( direction ) 0, _odejmowanie );
mp.AddOperator( "*", 2,( direction ) 0, _mnozenie );
mp.AddOperator( "/", 2,( direction ) 0, _dzielenie );
float ret = mp.Parse( exp );
cout << ret << endl;
cout << "Aby kontynuowa" <<( char ) 134 << ", naci" <<( char ) 152 << "nij dowolny klawisz . . .";
getch();
return EXIT_SUCCESS;
}

Kod źródłowy do pobrania

Gotowy kod jest dostępny do pobrania tutaj. Plik .zip zawiera dwa pliki - main.cpp zawierający kod testujący działanie parsera, i MathParser.hpp - kod zawierający klasę.

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.