[C++] Klasa przechowująca rozbite wyrażenie algebraiczne względem operatorów i nawiasów
Ostatnio zmodyfikowano 2012-10-18 20:47
crash Temat założony przez niniejszego użytkownika |
[C++] Klasa przechowująca rozbite wyrażenie algebraiczne względem operatorów i nawiasów » 2012-10-18 19:26:45 Siema. Piszę programa do obliczania wyrażeń algebraicznych oraz różnych operacji na nich. Można podstawiać pod zmienne i następnie obliczyć wartość wyrażenia. Teraz cuduję osobną klasę przechowującą wyrażenie w postaci grup wyrazów, np.: 3*x + (x^2)*(x-3) - (x^3)= powinno zostać rozbite na kolejne grupy: 1) 3*x 2) (x^2)*(x-3) 3) -(x^3) i mi trochę nie wychodzi, tak już ze 3 dni. Grupy chcę przechowywać w wektorze na wektory stringów. Dzielenie wyrażenia na małe grupy wyrazów jest po to, że gdyby trzeba było pomnożyć jedno wyrażenie przez drugie, przez liczbę, albo podstawić inne wyrażenie w miejscu którejś zmiennej, to tak pogrupowane wyrazy aż się o takie operacje będą prosiły ;p Dwa wyrażenia jako ułamek będzie można dzięki takiemu rozwiązaniu skracać; dwa wyrażenia, albo i jedno rozbudowane, w formie sumy iloczynów będzie można rozwijać pozbywając się nawiasów, itd, itp. Na ogół staram się radzić sam, ale nie spieszy mi się mieć za szybko siwe włosy :) Klasa sprawiająca problem: class Expression { private: vector < vector < string > > groups; public: Expression( string exp ) { this->operator ()( exp ); } void operator ()( string exp ) { groups.clear(); vector < string > vtmp; string stmp; int brackets_o = 0, brackets_c = 0, higher_lvl_op = 0; for( int i = 0; i < exp.size(); ++i ) { if( exp[ i ] == '(' ) brackets_o++; if( exp[ i ] == ')' ) brackets_c++; if( isdigit( exp[ i ] ) || exp[ i ] == '.' ) { while( isdigit( exp[ i ] ) || exp[ i ] == '.' ) { stmp += exp[ i ]; ++i; } vtmp.push_back( stmp ); stmp = ""; } if( isalpha( exp[ i ] ) ) { char c = exp[ i ]; string s; s += c; vtmp.push_back( s ); } char c = exp[ i ]; if( c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '@' || c == '(' || c == ')' ) { if( c != '+' && c != '-' ) higher_lvl_op++; string s; s += c; vtmp.push_back( s ); } } if( brackets_o != brackets_c ) { } int size = vtmp.size(); if( higher_lvl_op == 0 ) { for( int i = 0; i < size; ++i ) { vector < string > vstr; if( vtmp[ 0 ] == "-" && i == 1 ) vstr.push_back( "-" + vtmp[ i ] ); else vstr.push_back( vtmp[ i ] ); groups.push_back( vstr ); } return; } int bcnt = 0; for( int i = 0; i < size; ++i ) { } } vector < vector < string > > extract() { return groups; } void disp() { cout << "\nExpr::groups.size=" << groups.size() << endl; for( int i = 0; i < groups.size(); ++i ) { vector < string > vstr = groups[ i ]; for( int j = 0; j < vstr.size(); ++j ) cout << endl << vstr[ i ]; } } };
...
Expression E( "(x^2)-(x+3)*(x+4)+5" );
Pomoże ktoś? Jeśli ktoś zechce podrzucę cały kod. Heelp :) |
|
cyklopek11 |
» 2012-10-18 20:47:23 Myślę, że powinieneś zerknąć na wyrażenia regularne i pokombinować. Natomiast bez wyrażeń regularnych (jeszcze ich nie opanowałem więc w nich nie pomogę) wpadł mi do głowy taki algorytm:
1. wprowadzamy dodatkowy typ nawiasu, którego nie może wprowadzać użytkownik np. < > 2. określamy jaki znaczek określa niewiadomą (np. x) 3. wyszukujemy wyrażeń: niewiadoma*liczba, liczba*niewiadoma, niewiadoma/liczba, liczba/niewiadoma, niewiadoma^liczba, liczba^niewiadoma, ... , przed którymi i za którymi występują tylko operatory - lub + lub = .Ujmujemy je w nawiasy < > w naszym wyrażeniu 4. wyszukujemy wszystkie wyrażenia w nawiasach () przed którymi (nawiasami) i za którymi nie ma operatorów *, / ^ (pomijamy to co zostało we wcześniejszym kroku ujęte w nawiasy < >) i ujmujemy w nawiasy < > 5. wyszukujemy wszystkie wyrażenia w nawiasach () przed którymi (nawiasami) i za którymi nie ma już dalej operatorów *, / ^ (pomijamy to co zostało we wcześniejszym kroku ujęte w nawiasy < >) i ujmujemy w nawiasy < > 6. To samo co powyżej tylko bardziej bogate w nawiasy () wyrażenie 7. Jeśli całe wyrażenie algebraiczne jest ujęte w nawias a nie składa się z części określonych jak powyżej to usuwamy te nawiasy np.: ( 2x +(x^2) + 3) = 2x +(x^2) + 3 (wielomian nie "rozłożony" na dwumiany)
8. Piszemy funkcję która będzie wyszukiwała wyrażeń ujętych w nawiasy < > i wstawiała do vectora w kolejności wyrażeń od lewej do prawej.
TEN ALGORYTM NIE JEST ZBYT EFEKTYWNY ale od tego bym rozpoczął. Wszystko zależy też od tego, jakie inne rodzaje działań chcesz mieć w takich wyrażeniach (pierwiastkowanie?, logarytmoiwanie, jednostka urojona, stałe pi, e) |
|
« 1 » |