Mehrere Zahlen aus einem String extrahieren (durch Zeichen getrennt)



  • Guten Abend,

    es geht um folgendes Problem:

    Man nehme einen String, der eine Funktionsvorschrift enthält, beispielsweise

    2x4-5x3+3.5x^2+2x-5

    Man ahnt möglicherweise schon, worauf ich hinauswill. Ich möchte nun alle Koeffizienten mit ihren Potenzen aus dem String extrahieren und jeweils in ein std::pair schreiben. Es geht nicht ums Berechnen für x = n!

    Mein bisher einziger Ansatz erscheint mir extrem uneffizient:

    Gehe alle Buchstaben des Strings durch. Handelt es sich um ein Minus oder eine Zahl, speichere das ganze Konstrukt solange in einen neuen String, bis ein x kommt. Gehe dann weiter, und wenn ein ^ kommt, werden wieder Zahlen ausgelesen und in einen zweiten Teilstring geschrieben, bis ein neuer Operator kommt. Die beiden entstandenen Teilstrings werden dann in Zahlen umgewandelt und als std::pair niedergespeichert.

    Damit könnte ich jetzt jedes einzelne Koeefizient-Potenz-Paar speichern. Aber was mache ich, wenn ein lineares Glied kommt?

    Grundsätzlich: Mein Verfahren klingt so kompliziert, da muss es doch einen viel simpleren Weg geben, vllt. mit Stacks? Hat jemand eine Idee, wie ich mein Vorhaben simpler in die Tat umsetzen kann?

    Vielen Dank für eventuelle Antworten 🙂

    Zephyr


  • Mod

    Von Vorne nach hinten durchgehen und sich bestimmte Kombinationen zu suchen, ist sicherlich kein guter Ansatz für einen Matheparser. Das ganze kann sehr kompliziert werden, wenn du noch Sachen wie Fakultäten oder Funktionen brauchst. Selbst für einfache zweiseitige Operatoren ist der Ansatz nicht gut genug, wenn du auch noch Operatorpriorität (Punkt vor Strich) oder gar Klammern beachten möchtest.

    Am besten machst du das gar nicht selber (hier im Forum geistern ein paar fertige Parser rum), aber falls doch, dann:
    http://stackoverflow.com/questions/114586/smart-design-of-a-math-parser
    und ähnliche Googletreffer zum Thema



  • Ich habe mal eine Mathe-Parser Lib geschrieben, zu finden auf Github (komme ja nicht auf die Idee, die zu benutzen. Nimm eine anständige!)
    Hier mal ein (sehr fehleranfälliger, dafür kurzer!) Ansatz:

    #include <iostream>
    #include <sstream>
    #include <vector>
    #include <utility>
    
    std::istream& Char( std::istream& is,
    				    char ch,
    					bool skipws = true )
    {
    	if( skipws )
    		is >> std::ws;
    	if( is.get() != ch )
    		is.setstate( std::ios_base::failbit );
    	return is;
    }
    
    int main()
    {
    	std::istringstream stream("2x^4-5x^3+3.5x^2+2x-5");
    
    	using Real = double;
    
    	std::vector<std::pair<Real, Real>> values;
    
    	for(;;)
    	{
    		Real a, b;
    
    		if( !(stream >> a) )
    			break;
    
    		bool succeeded_x = false;
    		if( !Char(stream, 'x')
    		 || (succeeded_x = true, !Char(stream, '^')) )
    		{
    			stream.clear();
    			stream.unget();
    			b = succeeded_x;
    		}
    
    		else if( !(stream >> b) )
    			break;
    
    		values.emplace_back(a, b);
    
    		if( stream.peek() != '+' 
    		 && stream.peek() != '-' )
    			break;
    	}
    
    	for( auto const& p : values )
    		std::cout << p.first << " * x^" << p.second << '\n';
    }
    

    Ideone

    Edit: Ich habe die Vorzeichen der Koeffizienten ignoriert... man, sind Termiten in meinem Kopf?
    Edit²: Gefixt und Link geupdated.



  • @SeppJ:

    Einen kompletten Parser brauche ich eigentlich noch nicht. Wie gesagt, ich will nur die Werte für die Koeffizienten und die dazugehörigen Potenzen in ein std::pair schreiben. Also muss ich mich (noch!) nicht mit UNP und co. rumschlagen. Aber danke schonmal für den Link, wird für spätere Zwecke gespeichert.

    @Sone:

    Vielen Dank für den Code! Letztendlich macht der ja genau das, was ich erreichen wollte. Die Fehleranfälligkeiten werd ich dann wohl noch ausmerzen müssen 🙂
    __

    Mal schauen, was es da noch für Alternativen gibt.



  • Zephyr schrieb:

    Hat jemand eine Idee, wie ich mein Vorhaben simpler in die Tat umsetzen kann?

    Vielen Dank für eventuelle Antworten 🙂

    Zephyr

    Hallo Zephyr;

    ja, beginne (wie so oft) damit, das Problem in kleinerer Einheiten zu zerlegen.
    Grundsätzlich gehe ich nicht über den String, sonder über den std::istream, da dieser IMHO dafür besser geeignet ist.

    1. Wie parst/liest man einen Ausdruck wie "2x", "3.5x^2" oder einfach "5"?
    dazu schreibe man sich eine Klasse, die ich gleich bezeichnender Weise 'polynomial' nenne, und eine passende Einlesefunktion:

    template< typename T >
    class polynomial
    {
    public:
        polynomial()
            : coeff_( 1, T() )
        {}
        template< typename U > friend // Einlesen
            std::istream& operator>>( std::istream& in, polynomial< U >& p );
        template< typename U > friend // Ausgeben
            std::ostream& operator<<( std::ostream& out, const polynomial< U >& p );
    
    private:
        std::vector< T > coeff_;
    };
    

    gleich als Template, dann kannst Du ohne Mehraufwand zwischen double und anderen Typen wählen.

    Als Member habe ich kein pair< double, int > , wie von Dir vorgeschlagen, sondern einen Vektor von T(in Deinem Fall double) und ich werde den Wert an den Index in den vector schreiben, der durch den Exponenten vorgegeben ist. Warum - dazu später, denn ...

    Zephyr schrieb:

    Wie gesagt, ich will nur die Werte für die Koeffizienten und die dazugehörigen Potenzen in ein std::pair schreiben.

    ... das reicht ja nicht, weil damit die Information, ob zwischen den einzelnen Ausdrücken ein '+' oder ein '-' steht, verloren geht.

    Zum Einlesen benütze ich ein Helferlein namens ctest, was hier im Forum schon mehrfach nützliche Dienste geleistet hat. Damit kann man prüfen, ob ein bestimmtes Zeichen im Stream folgt oder nicht.

    Dann geht das Einlesen etwa so:

    template< typename U >
        std::istream& operator>>( std::istream& in, polynomial< U >& p )
    {
        U c;
        int expo = 0;
        if( in >> c ) // zunächst den Wert vor dem 'x' lesen
        {
            std::ios_base::fmtflags fmtflags = in.flags();
            if( ctest( in >> std::noskipws, 'x' ) ) // Leerzeichen sind ab hier nicht gestattet; folgt ein 'x'?
            {
                expo = 1; // Ja, dann ist der Exponent =1, falls jetzt nichts mehr kommt
                if( ctest( in, '^' ) ) // da kommt noch der Exponent
                {
                    if( in >> expo ) // Exponent lesen
                    {
                        if( expo < 0 ) // neg. Exponenten nicht implementiert
                            in.setstate( std::ios_base::failbit );
                    }
                }
            }
            in.flags( fmtflags );
            std::vector< U > coeff( expo+1 );
            coeff.back() = c; // Koeffizienten an die 'expo'-Stelle im Vektor schreiben, der Rest ist =0
            swap( coeff, p.coeff_ ); // Ergebnis übernehmen
        }
        return in;
    }
    

    damit wäre Teil 1 erledigt, das kann man schon mal so für sich testen und benutzen. Die Implementierung der Ausgabe des Polynoms überlasse ich Dir.

    2. Wie interpretiert man einen algebraischen Ausdruck der mit '+' und '-' getrennt ist?
    Ich hatte hier schon mal einen Ausdrucks-parser gepostet. In deinem Fall ist es einfacher, da Du Dich (bisher) auf +,- beschränkst. Also:

    template< typename T >
    class expression_type // ein einfacher Wrapper für den Typ 'T'
    {
    public:
        explicit expression_type( T& x ) : x_( x ) {}
        T& x_;
    };
    template< typename T >
    expression_type< T > expression( T& e ) // Factory Funktion, die macht die Anwendung einfacher
    {
        return expression_type< T >( e );
    }
    
    template< typename T >
    std::istream& operator>>( std::istream& in, expression_type< T > expr  )
    {   // expression =  wert {("+"|"-") wert}.
        for( in >> expr.x_; in; ) // den ersten Wert lesen; ..
        {
            if( ctest( in, '+' ) ) // ist es ein Plus?
            {
                T x2;
                if( in >> x2 ) // .. dann 2.Wert lesen
                    expr.x_ += x2; // .. und addieren
            }
            else if( ctest( in, '-' ) ) // ist es ein Minus?
            {
                T x2;
                if( in >> x2 ) // .. dann 2.Wert lesen
                    expr.x_ -= x2; // .. und subtrahieren
            }
            else
                break; // weder '+' noch '-', dann fertig
        }
        return in;
    }
    

    Du schreibst -Du brauchst keine Parser - aber so viel Code ist es doch nicht - oder?

    3. Jetzt muss man noch dafür sorgen, dass man zwei Polynome auch addieren und subtrahieren kann. Daher die Sache mit dem Vektor, das erreicht man einfach durch Addition bzw. Subtraktion der Koeffizienten:

    template< typename T >
    class polynomial
    {
    public:
        polynomial()
            : coeff_( 1, T() )
        {}
        polynomial& operator+=( const polynomial& b )
        {
            if( coeff_.size() < b.coeff_.size() )
                coeff_.resize( b.coeff_.size() );
            auto dst = begin(coeff_);
            for( auto src = begin(b.coeff_); src != end(b.coeff_); ++src, ++dst )
                *dst += *src;
            return *this;
        }
        polynomial& operator-=( const polynomial& b )
        {
            if( coeff_.size() < b.coeff_.size() )
                coeff_.resize( b.coeff_.size() );
            auto dst = begin(coeff_);
            for( auto src = begin(b.coeff_); src != end(b.coeff_); ++src, ++dst )
                *dst -= *src;
            return *this;
        }
        // usw. (s.o.)
    

    Jetzt nur noch alles zusammenbauen:

    #include "ctest.h" // s.Link oben
    #include <iostream>
    #include <vector>
    
    // Code wie oben
    
    int main()
    {
        using namespace std;
        for( polynomial< double > poly; cin >> expression( poly ); cin.ignore( 999, '\n' ) )
            cout << "die Eingabe: " << poly << endl;
        return 0;
    }
    

    und ein Dialog kann dann zum Beispiel so aussehen:

    2x^4-5x^3+3.5x^2+2x-5;
    die Eingabe: 2x^4+-5x^3+3.5x^2+2x+-5
    7x+6-5x^3-5-3x;
    die Eingabe: -5x^3+4x+1
    

    .. falls Du auch die Ausgabe-Funktion des Polynoms implementiert hast 😉

    Gruß
    Werner



  • Huhu,

    danke für diese sehr ausführliche Antwort!

    Aber ich muss leider zugeben, dass ich da absolut nicht durchblicke. Ich habe alles abgetippt, versucht, den Code anhand der Kommentare und der einen oder anderen stream-Doku zu verstehen, aber leider kompiliert es nichtmal.

    Das Problem liegt irgendwo bei diesem expression_type. In deinem Codeschnippsel ist ein überladener >>-Operator, der aber nicht im Klassenrumpf enthalten ist. Versuche ich, den in expression_type einzubinden, bekomme ich "c2804: Binärer Operator >> hat zuviele Parameter". Im Polynomial klappt das aber mit beiden Parametern. Sobald ich das aus dem Klassenrumpf rausnehme und den >>-Operator einfach so mittendrinne stehen lasse, bekomme ich einen Linker-Error.



  • Aber ich muss leider zugeben, dass ich da absolut nicht durchblicke.

    Hak' aber gerne mal nach, was du nicht verstehst.

    In deinem Codeschnippsel ist ein überladener >>-Operator, der aber nicht im Klassenrumpf enthalten ist.

    Wieso sollte er auch? Ein Operator kann entweder in der Klassendefinition deklariert werden oder außerhalb (bzw. innen aber mit friend -specifier) - davon hängt die Anzahl der Parameter ab, und noch ein daraus resultierender Seiteneffekt.

    Versuche ich, den in expression_type einzubinden

    Erstens: Was heißt einbinden? Ihn blindlings in die Klassendefinition kopieren? Zweitens: Wieso?

    , bekomme ich "c2804: Binärer Operator >> hat zuviele Parameter".

    Wundert mich nicht. Wahrscheinlich nicht als Freund deklariert, nicht wahr?

    Im Polynomial klappt das aber mit beiden Parametern. Sobald ich das aus dem Klassenrumpf rausnehme und den >>-Operator einfach so mittendrinne stehen lasse, bekomme ich einen Linker-Error.

    Welcher Linkererror, welcher Code? Du drückst dich ein wenig wirr aus. Zeig mal den Code.



  • Hallo Zephyr,

    Zephyr schrieb:

    Ich habe alles abgetippt, ..

    hoffentlich nicht, schon mal was von Copy&Paste gehört?

    Zephyr schrieb:

    ..versucht, den Code anhand der Kommentare und der einen oder anderen stream-Doku zu verstehen, aber leider kompiliert es nichtmal.

    Das Problem liegt irgendwo bei diesem expression_type. In deinem Codeschnippsel ist ein überladener >>-Operator, der aber nicht im Klassenrumpf enthalten ist. Versuche ich, den in expression_type einzubinden, bekomme ich "c2804: Binärer Operator >> hat zuviele Parameter".

    friend vergessen (Sone schrieb es schon) - aber warum ändern?

    Zephyr schrieb:

    Im Polynomial klappt das aber mit beiden Parametern. Sobald ich das aus dem Klassenrumpf rausnehme und den >>-Operator einfach so mittendrinne stehen lasse, bekomme ich einen Linker-Error.

    na klar, wer Lesen kann ist im Vorteil

    Werner Salomon schrieb:

    .. falls Du auch die Ausgabe-Funktion des Polynoms implementiert hast

    😉
    diesen Teil hatte ich nicht gepostet. Wenn Du den fort lässt, so gibt es einen Linker Error, da der Build die Implementierung dieser Funktion vermisst:

    template< typename T >
    class polynomial
    {
    public:
        // ...
        template< typename U > friend // Ausgeben
            std::ostream& operator<<( std::ostream& out, const polynomial< U >& p );
    

    Das ist die Ausgabe-Funktion für ein Polynom.

    Hier eine kleine Übung:

    #include <iostream>
    
    class Pups
    {
    public:
        int ein_int_; // Bem.: Member ist public: !
    };
    
    // --   das ist eine freie Funktion mit zwei Parametern; zumm Einlesen eiens Pups-Objekts
    std::istream& operator>>( std::istream& in, Pups& p )
    {
        return in >> p.ein_int_; // da 'ein_int_' public ist, kann hier darauf zugegriffen werden
    }
    // --   noch eine Funktion, zum Ausgaben eines Pups-Objekts
    std::ostream& operator<<( std::ostream& out, Pups p )
    {
        return out << "Pups(" << p.ein_int_ << ")";
    }
    
    class Foo
    {
    public:
        Foo( int ein_int ) 
            : ein_int_( ein_int )
        {}
        friend std::ostream& operator<<( std::ostream& out, Foo f );
    private:
        int ein_int_;
    };
    // --   das ist genauso eine freie Funktion, aber sie ist friend von Foo
    std::ostream& operator<<( std::ostream& out, Foo f )
    {
        return out << "Foo[" << f.ein_int_ << "]"; // 'ein_int_' pist private, aber die Funktion ist ein friend
    }
    
    int main()
    {
        using namespace std;
        Pups pups_objekt;
        if( cin >> pups_objekt ) // Pups lesen
            cout << pups_objekt << endl; // ... und ausgeben
        Foo foo(42);
        cout << foo << endl; // Foo ausgeben
        return 0;
    }
    

    probier's mal aus

    Gruß
    Werner



  • Und hier der gesammelte Source Code inklusive der Implementierung der Ausgabe von polynomial<> exklusiv "ctest.h"; letzteres scheinst Du ja geschafft zu haben.

    #include "ctest.h" // s. http://www.c-plusplus.net/forum/p1828117#1828117
    #include <iostream>
    #include <vector>
    
    template< typename T >
    class polynomial
    {
    public:
        polynomial()
            : coeff_( 1, T() )
        {}
        polynomial& operator+=( const polynomial& b )
        {
            if( coeff_.size() < b.coeff_.size() )
                coeff_.resize( b.coeff_.size() );
            auto dst = begin(coeff_);
            for( auto src = begin(b.coeff_); src != end(b.coeff_); ++src, ++dst )
                *dst += *src;
            return *this;
        }
        polynomial& operator-=( const polynomial& b )
        {
            if( coeff_.size() < b.coeff_.size() )
                coeff_.resize( b.coeff_.size() );
            auto dst = begin(coeff_);
            for( auto src = begin(b.coeff_); src != end(b.coeff_); ++src, ++dst )
                *dst -= *src;
            return *this;
        }
        // -- die Funktionen für Einlesen&Ausgeben werden hier als 'friend' deklariert,
        //    so dass dort auf den private Member von polynomial<> zugegriffen werden kann
        template< typename U > friend 
            std::ostream& operator<<( std::ostream& out, const polynomial< U >& p );
        template< typename U > friend
            std::istream& operator>>( std::istream& in, polynomial< U >& p );
    
    private:
        std::vector< T > coeff_;
    };
    
    // -- Funktion zum Lesen eines einzelnen Ausdrucks eines Polynoms
    template< typename U >
        std::istream& operator>>( std::istream& in, polynomial< U >& p )
    {
        U c;
        int expo = 0;
        if( in >> c ) // zunächst den Wert vor dem 'x' lesen
        {
            std::ios_base::fmtflags fmtflags = in.flags();
            if( ctest( in >> std::noskipws, 'x' ) ) // Leerzeichen sind ab hier nicht gestattet; folgt ein 'x'?
            {
                expo = 1; // Ja, dann ist der Exponent =1, falls jetzt nichts mehr kommt
                if( ctest( in, '^' ) ) // da kommt noch der Exponent
                {
                    if( in >> expo ) // Exponent lesen
                    {
                        if( expo < 0 ) // neg. Exponenten nicht implementiert
                            in.setstate( std::ios_base::failbit );
                    }
                }
            }
            in.flags( fmtflags );
            std::vector< U > coeff( expo+1 );
            coeff.back() = c; // Koeffizienten an die 'expo'-Stelle im Vektor schreiben, der Rest ist =0
            swap( coeff, p.coeff_ ); // Ergebnis übernehmen
        }
        return in;
    }
    
    // -- Funktion zur Ausgabe des Polynoms
    template< typename U >
        std::ostream& operator<<( std::ostream& out, const polynomial< U >& p )
    {
        bool printed = false;
        int expo = int(p.coeff_.size())-1;
        for( auto c = p.coeff_.rbegin(); c != p.coeff_.rend(); ++c, --expo )
        {   // Schleife läuft von rbegin nach rend, so dass die Koeffizienten mit den hohen Werten vorne stehen
            if( *c == U() ) // *c == 0
                continue; // Koeffizienten mit Wert =0 werden nicht ausgegeben
            if( printed ) out << "+";
            out << *c;
            if( expo > 0 )
            {
                out << "x";
                if( expo > 1 ) out << "^" << expo;
            }
            printed = true;
        }
        if( !printed )
            out << U();
        return out;
    }
    
    template< typename T >
    class expression_type
    {
    public:
        explicit expression_type( T& x ) : x_( x ) {}
        T& x_;
    };
    template< typename T >
    expression_type< T > expression( T& e )
    {
        return expression_type< T >( e );
    }
    // -- Funktion zum Einlesen eines expression_type< T >
    template< typename T >
    std::istream& operator>>( std::istream& in, expression_type< T > expr  )
    {   // expression =  wert {("+"|"-") wert}.
        for( in >> expr.x_; in; ) // den ersten Wert lesen; ..
        {
            if( ctest( in, '+' ) ) // ist es ein Plus?
            {
                T x2;
                if( in >> x2 ) // .. dann 2.Wert lesen
                    expr.x_ += x2; // .. und addieren
            }
            else if( ctest( in, '-' ) ) // ist es ein Minus?
            {
                T x2;
                if( in >> x2 ) // .. dann 2.Wert lesen
                    expr.x_ -= x2; // .. und subtrahieren
            }
            else
                break; // weder '+' noch '-', dann fertig
        }
        return in;
    }
    
    int main()
    {
        using namespace std;
        for( polynomial< double > poly; cin >> expression( poly ); cin.ignore( 999, '\n' ) )
            cout << "die Eingabe: " << poly << endl;
        return 0;
    }
    

    sei noch erwähnt, dass man das noch weiter vervollständigen kann.
    So sollte polynomial<> eine Methode bekommen, die den höchsten Koeffizienten beseitigt, falls dieser =0 ist. Es fehlen auch noch die Funktionen um zwei Objekte zu addieren und zu subtrahieren. operator* wäre auch noch sinnvoll, usw.
    Weiter wäre die Ausgabe noch zu verfeinern, so dass z.B. statt

    3x+-5
    

    besser

    3x-5

    ausgegeben wird.
    Aber ich habe mich bemüht, den Code so einfach wie möglich zu halten.

    Über ein Feedback würde ich mich freuen.

    Gruß
    Werner


Log in to reply