Mehrere Zahlen aus einem String extrahieren (durch Zeichen getrennt)

[Zephyr]

Guten Abend,

es geht um folgendes Problem:

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

2x^4-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

[SeppJ]

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

[Sone]

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.

[Zephyr]

@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.

[Werner Salomon]

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

[Zephyr]

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.

[Sone]

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.

[Werner Salomon]

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

[Werner Salomon]

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