C++ String Problem

04/02/2012 13:17 BrendonHomo#1

Ich stehe vor einem bl�den problem,

wahrscheinlich ist die L�sung ziemlich simple aber habe keine Idee wie ich das umsetzen soll undzwar habe ich einen std::string mystring "000111110000110010111100" und ich m�chte dazwischen / dahinter die length einf�gen so das , dass wie folgt aussieht:

length 3 (000) length 5(11111) length 4 (0000) length 2(11) length 2 (00) length 1 (1) length 1 (0) length 4(1111) length 2(00) am ende sollte der string so aussehen:

300051111140000211200111041111200

Ich hoffe man versteht was ich anhand des beispiels meine.

04/02/2012 14:16 xNopex#2

Ich w�rde es ja rekursiv l�sen:

Code:

#include <iostream>
#include <string>
#include <sstream>

std::string rekChStr(std::string str)
{
    char ch = str.at(0);
    int length = 1;
    while(length < str.size() && str.at(length) == ch)
    {
        length++;
    }
    std::string s(length, ch);
    std::stringstream toString;
    toString << length;

    if(str.size() == length)
    {
        return toString.str()+s;
    }else
    {
        return toString.str()+s+rekChStr(str.substr(length));
    }

}

int main()
{
    std::cout << rekChStr("000111110000110010111100");

    return 0;
}

04/02/2012 22:54 link#3

Sehe keinen Grund f�r Rekursion, wenn's sowieso so straightforwarded ist und die Rekursion ganz simpel den iterativen Ansatz ersetzt, da es in so einem Fall eigentlich nur langsamer werden kann:

Code:

#include <iostream>
#include <string>
#include <sstream>
#include <ctime>

std::string rekChStr(std::string str)
{
    char ch = str.at(0);
    int length = 1;
    while(length < str.size() && str.at(length) == ch)
    {
        length++;
    }
    std::string s(length, ch);
    std::stringstream toString;
    toString << length;

    if(str.size() == length)
    {
        return toString.str()+s;
    }else
    {
        return toString.str()+s+rekChStr(str.substr(length));
    }

}

std::string xyz(std::string str)
{
	int pos = 0;
	std::stringstream toString;

	do
	{
		char ch = str.at(pos);
		int length = 1;

		while (++pos < str.size() && str.at(pos) == ch)
			length++;

		std::string s(length, ch);
		toString << length;
		toString << s;

	} while (pos < str.size());

	return toString.str();
}

int main()
{
	int i, a = clock();

	for (i = 0; i < 1000; i++)
		rekChStr("000111110000110010111100");

    std::cout << rekChStr("000111110000110010111100") << std::endl << clock() - a << std::endl;

	a = clock();
	for (i = 0; i < 1000; i++)
		xyz("000111110000110010111100");

    std::cout << xyz("000111110000110010111100") << std::endl << clock() - a << std::endl;

	std::cin >> a;

    return 0;
}

Kenne mich mit C++ zwar nicht aus, aber es scheint schneller zu sein, wenn man den std::stringstream weiter benutzt anstatt einen neuen std::string zu erzeugen:

Code:

std::string rekChStr(std::string str)
{
    char ch = str.at(0);
    int length = 1;
    while(length < str.size() && str.at(length) == ch)
    {
        length++;
    }
    std::string s(length, ch);
	std::stringstream toString;
    toString << length << s;

    if(str.size() != length)
		toString << rekChStr(str.substr(length));

	return toString.str();
}

04/02/2012 23:40 xNopex#4

Ich bin ein Fan von Rekursion.

04/03/2012 01:13 MrSm!th#5

Sieht man �fters :P, geht mir auch so, dennoch sollte man sie vermeiden, wenn sie nicht implementierungstechnisch den Aufwand erheblich verringert, denn sie birgt nunmal auch immer das Risiko eines Stackoverflows.

04/03/2012 10:44 xNopex#6

Wenn ich das mal so grob umrei�e.. Hat man hier im worst Case ca. ne Tiefe der Anzahl an Zeichen in der Zeichenkette. Wird also weniger das Problem sein, allgemein hast du nat�rlich Recht.
Jedoch sehe ich v.a. die Vorteile in einer besseren Lesbarkeit. Zugegeben in diesem Fall nicht. Aber wenn man sie klug einsetzt, sind rekursive L�sungen imho immer sch�ner als h�ssliche Schleifen. V.a. bei B�umen undsowas finde ich Rekursion wesentlich eleganter als 10.000 Hilfsvariablen anzulegen, dass man iterativ dr�ber laufen kann.
Und vermutlich wird der Compiler auch oft meine Rekursion letzendlich wegoptimieren :)
Bleibt aber Geschmackssache und ich mags :>

04/05/2012 10:56 Muddy Waters#7

Ich verstehe leider noch nicht so ganz genau, was du eigentlich vorhast; mag auch daran liegen, dass ich C++ technisch ziemlich eingerostet bin. :o

Trotzdem mal ein paar Anmerkungen:
Soweit ich das sehe ist die erste for-Schleife obsolet, du k�nntest diese �berpr�fung genausogut in der zweiten for-Schleife machen.

Dein char-Array per while-Schleife zu durchlaufen halte ich f�r unsicher, damit kannst du dir leicht Zugriffsverletzungen einfangen, sofern der zu �berpr�fende Char aus irgendeinem Grund nicht in dem Array vorkommt. Besser w�re es wohl ohnehin dein char Array direkt als String zu definieren, sodass du mit Standardfunktionen arbeiten kannst, um nach dem Index eines Chars zu suchen. In dem Fall w�re das string::find, damit lie�e sich auch die if-Anweisung zur jeweiligen char Pr�fung gegen eine Index �berpr�fung ersetzen, die wiederum deutlich k�rzer w�re.