Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] Klasa przechowująca rozbite wyrażenie algebraiczne względem operatorów i nawiasów

Ostatnio zmodyfikowano 2012-10-18 20:47
Autor Wiadomość
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:

C/C++
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; // */^@(), ale nie +-
       
        for( int i = 0; i < exp.size(); ++i )
        {
            if( exp[ i ] == '(' ) brackets_o++;
           
            if( exp[ i ] == ')' ) brackets_c++;
           
            if( isdigit( exp[ i ] ) || exp[ i ] == '.' ) //badanie ilosci nawiasow
            {
                while( isdigit( exp[ i ] ) || exp[ i ] == '.' ) //ekstrakcja liczb
                {
                    stmp += exp[ i ];
                    ++i;
                }
               
                vtmp.push_back( stmp );
                stmp = "";
            }
           
            if( isalpha( exp[ i ] ) ) //a..z
            {
                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 );
            }
        }
        //drugi etap
        if( brackets_o != brackets_c )
        {
        }
       
        int size = vtmp.size();
       
        if( higher_lvl_op == 0 ) //jesli w wyrazeniu same +-..
        {
            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;
        }
       
        //jesli wyrazenie ma iloczyny, ilorazy lub nawiasy
       
        int bcnt = 0; //bracket counter
       
        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 :)
P-67053
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)
P-67056
« 1 »
  Strona 1 z 1