Zerlegung von Zeichenketten: Die Klasse StringTokenizer

1. Aufgabe

Wir betrachten in dieser Aufgabe eine Klasse StringTokenizer. Darunter verstehen wir eine C++-Klasse, mit deren Hilfe man eine klassische C-Zeichenkette (also ein char-Array mit einer terminierenden Null) in ihre Teilzeichenketten, so genannte Tokens, zerlegen kann. Betrachten Sie dazu das folgende Beispiel zur Zeichenkette Dies ist ein Test:

StringTokenizer st ("Dies ist ein Test");
while (st.HasMoreTokens ())
{
    char* tok = st.NextToken ();
    cout << "found " << tok << endl;
    delete[] tok;
}

Wenn wir das Leerzeichen als Trennzeichen zwischen den einzelnen Teilzeichenketten zu Grunde legen, ist die Ausgabe

found 'Dies'
found 'ist'
found 'ein'
found 'Test'

verständlich. Zur den Begrifflichkeiten: Einzelne Teilzeichenketten werden durch so genannte Begrenzer voneinander getrennt. Unter einem Begrenzer verstehen wir ein einzelnes Zeichen, das die Teilzeichenketten voneinander trennt. Zwischen zwei Teilzeichenketten muss mindestens ein Begrenzer vorhanden sein, es können natürlich auch mehrere (gleiche oder unterschiedliche) Begrenzer dazwischen liegen. Das Leerzeichen ' ' bezeichnen wir als Default-Begrenzer. Siehe ein zweites Beispiel, das auf Basis der zwei Begrenzer '!' und '#' fußt:

StringTokenizer st ("!#!123!456#789#!#", "!#");
while (st.HasMoreTokens ())
{
    char* tok = st.NextToken ();
    cout << "found '" << tok << '\'' << endl;
    delete[] tok;
}

Ausgabe:

found '123'
found '456'
found '789'

Nach diesen einleitenden Betrachtungen kommen wir nun auf die Details einer Klasse StringTokenizer zu sprechen:

1.1. Klasse StringTokenizer

Entwickeln Sie eine Klasse StringTokenizer, in Tabelle 1 finden Sie eine Spezifikation ihrer Elemente vor:

Element

Beschreibung

Standardkonstruktor

StringTokenizer ();

Die zu zerlegende Zeichenkette ist nachträglich mit SetString zu spezifizieren. Als Begrenzer kommt der Default-Begrenzer zum Einsatz.

Benutzerdefinierter Konstruktor

StringTokenizer (char* str);

Die zu zerlegende Zeichenkette ist durch den Parameter str spezifiziert, es ist wiederum der Default-Begrenzer zu Grunde zu legen.

Benutzerdefinierter Konstruktor

StringTokenizer(char* str, char* delim);

Die zu zerlegende Zeichenkette ist durch den Parameter str spezifiziert, der (oder die) Begrenzer durch die Zeichenkette delim.

Methode SetString

void SetString (char* str);

Die durch den Tokenizer zu zerlegende Zeichenkette str wird festgelegt.

Methode SetDelimiters

void SetDelimiters (char* delim);

Die Begrenzer (Zeichenkette delim, bestehend aus einem oder mehreren Zeichen) des Tokenizers werden spezifiziert.

Methode HasMoreTokens

bool HasMoreTokens ();

Liefert true zurück, falls die Zerlegung der Zeichenkette noch nicht abgeschlossen ist und ein anschließender Aufruf der NextToken-Methode erfolgreich ausgeführt werden kann. Andernfalls ist das Ergebnis false.

Methode NextToken

char* NextToken ();

Liefert das nächste Token in der Zeichenkette zurück. Im Fehlerfall (beispielsweise wenn kein Token mehr vorhanden ist) wird der Nullzeiger zurückgeliefert.

Die Ergebniszeichenkette ist mit new zu erzeugen, um zu vermeiden, dass der Benutzer Zugang zu internen Daten des Tokenizers bekommt. Natürlich hat dies zur Folge, dass jeder Aufrufer von NextToken das Ergebnis (Rückgabewert) mit delete wieder freigeben muss, damit kein Speicher in der dynamischen Speicherverwaltung verloren geht.

Methode Count

int Count ();

Berechnet die Anzahl der Token, die die aktuell zu zerlegende Zeichenkette besitzt.

Hinweis: Der interne Zustand des Tokenizers wird von der Count-Methode nicht beeinflusst.

Methode Reset

void Reset ();

Der Tokenizer wird in den Grundzustand versetzt. Nachfolgende Aufrufe von HasMoreTokens und NextToken beginnen mit der Zerlegung der Zeichenkette von vorne.

Operator <<

ostream& operator<< (ostream&, StringTokenizer&);

Ausgabe aller Token eines StringTokenizer-Objekts. Das Format sollte so aussehen:

[Dies,ist,ein,Test]

Tabelle 1. Definition der Klasse StringTokenizer.


Neben den Hinweisen aus Tabelle 1 sind natürlich alle Regeln zu beachten, die in C++ für die Realisierung einer Klasse generell gelten. Die Funktionen aus der C-Runtime-Library (stdio.h, string.h, ...) dürfen Sie natürlich verwenden, wenngleich meiner Meinung nach Ihr Lernerfolg größer ist, wenn Sie diese – nur für diese Aufgabe – außer Acht lassen. Testen Sie Ihre Implementierung an Hand des folgenden Testrahmens:

void main ()
{
    // regular use of this tokenizer
    StringTokenizer st ("Dies ist ein Test");
    while (st.HasMoreTokens ())
    {
        char* tok = st.NextToken ();
        cout << "Found: " << tok << endl;
        delete tok;
    }

    // illegal use of tokenizer - no preceding call of 'HasMoreTokens'
    char* cp = st.NextToken ();
    if (cp == (char*) 0)
        cout << "NextToken failed!" << endl;

    // another test scanario
    st.SetString ("0Auch123dieses456ist789nur12ein34nichtssagender45Satz67zum8Testen9");
    st.SetDelimiters ("0123456789");
    cout << st << endl;

    // testing CountTokens method
    int num = st.Count ();
    cout << "# Tokens: " << num << endl;

    // yet another test scanario
    StringTokenizer st2 ("123!456#789", "!#");
    while (st2.HasMoreTokens ())
    {
        char * tok = st2.NextToken ();
        cout << "Found: " << tok << endl;
        delete tok;
    }

    // testing CountTokens method
    num = st2.Count ();
    cout << "# Tokens: " << num << endl;
}

Das Resultat der Ausführung muss

Found: Dies
Found: ist
Found: ein
Found: Test
NextToken failed!
[Auch,dieses,ist,nur,ein,nichtssagender,Satz,zum,Testen]
# Tokens: 9
Found: 123
Found: 456
Found: 789
# Tokens: 3

lauten.

1.2. Klasse Token

Das Design der Klasse StringTokenizer ist in Bezug auf die Methode NextToken nicht optimal. Der Rückgabewert der Methode darf keinen Zugriff zu internen Daten eines StringTokenizer-Objekts ermöglichen, das Resultat wird folglich dynamisch (auf der Halde des Programms) allokiert. Vergisst der Benutzer eines StringTokenizer-Objekts, diesen Speicherbereich wieder freizugeben, entstehen irreparable Lücken in der Speicherverwaltung.

Wir führen aus diesem Grund in dieser Teilaufgabe eine Hilfsklasse Token ein. Mit ihrer Hilfe definieren wir eine NextTokenEx-Methode nun so:

Token NextTokenEx ();

Die Zerlegung einer Zeichenkette kann nun so erfolgen:

StringTokenizer st ("Dies ist ein Test");
while (st.HasMoreTokens ())
{
    Token tok = st.NextTokenEx ();
    cout << tok << endl;
}

Die Freigabe dynamisch allokierter Daten fällt nun in den Aufgabenbereich des Destruktors des Token-Objekts. Destruktor-Aufrufe wiederum werden vom Compiler automatisch generiert (mit Ausnahme dynamisch allokierter Objekte). Die Robustheit des Programms ist auf diese Weise erheblich verbessert. Implementieren Sie eine Klasse Token so, dass das letzte Codefragment übersetzungs- und lauffähig ist!

1.3. Index-Operator [] und Methode Tokenize

Für eine Klasse StringTokenizer bietet es sich auch an, den Index-Operator [] zu überladen. Mit einem indizierten Zugriff könnte man gezielt das das i.-te Token in einer Zeichenkettenzerlegung zugreifen. Dies wiederum setzt voraus, dass in einem StringTokenizer-Objekt die Zerlegung in einzelne Tokens schon durchgeführt wurde. Deshalb fügen wir gleich noch eine Methode Tokenize zur Klasse hinzu, die eine Zerlegung in einem Rutsch vornimmt. Für das Resultat eines Tokenize-Methodenaufrufs bietet es sich an, in einem StringTokenizer-Objekt ein Array entsprechender Länge mit Token-Objekten zu verwalten. Auf dieses Array lässt sich dann mit dem Index-Operator [] direkt zugreifen.

Im Folgenden finden Sie ein kleines Beispiel zum Zusammenspiel des Index-Operators, der Tokenize-Methode und zur getter-Methode Count vor:

void main ()
{
    StringTokenizer st ("Dies!ist#auch#!#!#!ein!#!#!#Test", "!#");

    st.Tokenize();  // disassemble string into tokens

    cout << "# Tokens: " << st.Count() << endl;
    for (int i = 0; i< st.Count(); i ++)
    {
        Token t = st[i];
        cout << i << ": " << t << endl;
    }
}

Ausgabe:

# Tokens: 5
0: Dies
1: ist
2: auch
3: ein
4: Test

In Tabelle 2 haben wir alle Ergänzungen bzgl. Tabelle 1 noch einmal kompakt zusammengefasst:

Element

Beschreibung

Methode NextTokenEx

Token NextTokenEx ();

Liefert das nächste Token in der Zeichenkette zurück. Im Gegensatz zur Methode NextToken wird das Token in einem Objekt des Typs Token aufbereitet. Im Fehlerfall (beispielsweise wenn kein Token mehr vorhanden ist) wird ein Token-Objekt mit der leeren Zeichenkette "" zurückgeliefert.

Operator []

Token operator[] (int i);

Liefert von einer Zeichenkettenzerlegung das i.-te Token-Objekt zurück. Der Wert des Indizes i muss im Bereich von 0 bis Count()-1 liegen. Im Fehlerfall wird ein Token-Objekt mit der leeren Zeichenkette "" zurückgeliefert.

Methode Tokenize

void Tokenize ();

Zerlegt die in einem StringTokenizer-Objekt abgelegte Zeichenkette in ihre einzelnen Teilzeichenketten. Mit Hilfe des []-Operators kann man direkt auf einzelne Teilzeichenketten zugreifen.

Tabelle 2. Erweiterungen der Klasse StringTokenizer.


Nehmen Sie entsprechende Erweiterungen an der Klasse StringTokenizer vor!

2. Lösung

Quellcode: Siehe auch github.com/peterloos/Cpp_StringTokenizer.git.

Im Lösungsabschnitt finden Sie nun der Reihe nach Schnittstellen samt Implementierung zu folgenden Klassen vor:

01: class Token
02: {
03: friend ostream& operator<< (ostream&, const Token&);
04: 
05: private:
06:     // private member data
07:     char* m_tok;   // token
08: 
09: public:
10:     // c'tors / d'tor
11:     Token ();
12:     Token (char*);
13:     Token (char*, int len);
14:     Token (const Token&);
15:     ~Token ();
16: 
17: public:
18:     // operators
19:     Token& operator= (const Token&);
20:     bool operator== (const Token&);
21: };

Beispiel 1. Klasse Token: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: #include <string>
04: 
05: #include "Token.h"
06: #include "StringTokenizer.h"
07: 
08: // c'tors and d'tor
09: Token::Token ()
10: {
11:     m_tok = (char*) 0;
12: }
13: 
14: Token::Token (char* tok)
15: {
16:     // allocate memory and copy argument
17:     int len = strlen(tok);
18:     m_tok = new char[len + 1];
19:     strcpy_s (m_tok, len + 1, tok);
20: }
21: 
22: Token::Token (char* tok, int len)
23: {
24:     // allocate memory and copy argument
25:     m_tok = new char[len + 1];
26:     strncpy_s (m_tok, len + 1, tok, len);
27: }
28: 
29: Token::Token (const Token& t)
30: {
31:     // allocate memory and copy argument
32:     if (t.m_tok != (char *) 0)
33:     {
34:         int len = strlen(t.m_tok);
35:         m_tok = new char[len + 1];
36:         strcpy_s (m_tok, len + 1, t.m_tok);
37:     }
38:     else
39:         m_tok = (char*) 0;
40: }
41: 
42: Token::~Token ()
43: {
44:     delete[] m_tok;
45: }
46: 
47: // comparison operator
48: bool Token::operator== (const Token& t)
49: {
50:     if (strcmp(m_tok, t.m_tok) != 0)
51:         return false;
52: 
53:     return true;
54: }
55: 
56: // assignment operator
57: Token& Token::operator= (const Token& t)
58: {
59:     // prevent self-assignment
60:     if (this == &t)
61:         return *this;
62: 
63:     // delete old token
64:     delete[] m_tok;
65: 
66:     // copy token
67:     if (t.m_tok != (char *) 0)
68:     {
69:         int len = strlen(t.m_tok);
70:         m_tok = new char[len + 1];
71:         strcpy_s (m_tok, len + 1, t.m_tok);
72:     }
73:     else
74:         m_tok = (char*) 0;
75: 
76:     return *this;
77: }
78: 
79: // output operator
80: ostream& operator<< (ostream& os, const Token& t)
81: {
82:     if (t.m_tok != (char *) 0)
83:         os << t.m_tok;
84:     return os;
85: }

Beispiel 2. Klasse Token: Implementierung.


01: class StringTokenizer
02: {
03: // output operator
04: friend ostream& operator<< (ostream&, StringTokenizer&);
05: 
06: private:
07:     // private member data
08:     char*   m_str;      // string to tokenize
09:     char*   m_delim;    // string of delimiters
10:     int     m_pos;      // current position during tokenization
11:     Token*  m_tokens;   // list of tokens
12: 
13: public:
14:     // c'tors / d'tor
15:     StringTokenizer ();
16:     StringTokenizer (char*);
17:     StringTokenizer (char*, char*);
18:     StringTokenizer (const StringTokenizer&);
19:     virtual ~StringTokenizer ();
20: 
21:     // setter
22:     void SetString (char*);
23:     void SetDelimiters (char*);
24: 
25:     // public methods
26:     int Count ();
27:     void Tokenize ();
28: 
29:     // enumeration
30:     void Reset ();
31:     bool HasMoreTokens () const;
32:     char* NextToken ();
33:     Token NextTokenEx ();
34:     void SkipToken ();
35: 
36: public:
37:     // public operators
38:     Token operator[] (int);
39: 
40: private:
41:     // private helper functions
42:     bool IsDelim (char) const;
43: 
44: public:
45:     // public operators
46:     StringTokenizer& operator= (const StringTokenizer&);
47: };

Beispiel 3. Klasse StringTokenizer: Schnittstelle.


001: #include <iostream>
002: using namespace std;
003: 
004: #include "Token.h"
005: #include "StringTokenizer.h"
006: 
007: // c'tors and d'tor
008: StringTokenizer::StringTokenizer ()
009: {
010:     m_str = (char*) 0;
011:     m_delim = (char*) 0;
012: 
013:     SetString ("");
014:     SetDelimiters (" ");
015: 
016:     m_pos = 0;
017:     m_tokens = (Token*) 0;
018: }
019: 
020: StringTokenizer::StringTokenizer (char* s)
021: {
022:     m_str = (char*) 0;
023:     m_delim = (char*) 0;
024: 
025:     SetString (s);
026:     SetDelimiters (" ");
027: 
028:     m_pos = 0;
029:     m_tokens = (Token*) 0;
030: }
031: 
032: StringTokenizer::StringTokenizer (char* s, char* d)
033: {
034:     m_str = (char*) 0;
035:     m_delim = (char*) 0;
036: 
037:     SetString (s);
038:     SetDelimiters (d);
039: 
040:     m_pos = 0;
041:     m_tokens = (Token*) 0;
042: }
043: 
044: StringTokenizer::StringTokenizer (const StringTokenizer& st)
045: {
046:     m_str = (char*) 0;
047:     m_delim = (char*) 0;
048: 
049:     SetString (st.m_str);
050:     SetDelimiters (st.m_delim);
051: 
052:     m_pos = 0;
053:     m_tokens = (Token*) 0;
054: }
055: 
056: StringTokenizer::~StringTokenizer ()
057: {
058:     delete[] m_str;
059:     delete[] m_delim;
060:     delete[] m_tokens;
061: }
062: 
063: // setter
064: void StringTokenizer::SetString (char* s)
065: {
066:     // release formerly allocated string
067:     delete[] m_str;
068: 
069:     // allocate memory and copy argument
070:     int len = (int) strlen (s);
071:     m_str = new char[len + 1];
072:     strcpy_s (m_str, len + 1, s);
073: }
074: 
075: void StringTokenizer::SetDelimiters (char* d)
076: {
077:     // release formerly allocated delimiter string
078:     delete[] m_delim;
079: 
080:     // allocate memory and copy argument
081:     int len = (int) strlen (d);
082:     m_delim = new char[len + 1];
083:     strcpy_s (m_delim, len + 1, d);
084: }
085: 
086: // public methods
087: int StringTokenizer::Count ()
088: {
089:     int count = 0;
090: 
091:     int ofs = 0;
092:     while (m_str[ofs] != '\0')
093:     {
094:         if (IsDelim (m_str[ofs]))
095:         {
096:             ofs ++;
097:             continue;
098:         }
099:         else
100:         {
101:             // begin of next token found
102:             count ++;
103: 
104:             // search end of token
105:             while (m_str[ofs] != '\0')
106:             {
107:                 if (! IsDelim (m_str[ofs]))
108:                     ofs ++;
109:                 else
110:                     break;
111:             }
112:         }
113:     }
114: 
115:     return count;
116: }
117: 
118: void StringTokenizer::Tokenize ()
119: {
120:     Reset ();
121:     int count = Count();
122:     m_tokens = new Token[count];
123: 
124:     for (int i = 0; i < count; i ++)
125:         m_tokens[i] = NextToken();
126: }
127: 
128: // enumeration
129: void StringTokenizer::Reset ()
130: {
131:     m_pos = 0;
132: }
133: 
134: bool StringTokenizer::HasMoreTokens () const
135: {
136:     int ofs = m_pos;
137:     while (m_str[ofs] != '\0')
138:     {
139:         if (IsDelim (m_str[ofs]))
140:         {
141:             ofs ++;
142:             continue;
143:         }
144: 
145:         // there is at least one token in the string
146:         return true;
147:     }
148: 
149:     // no more chars found (except delimiters)
150:     return false;
151: }
152: 
153: char* StringTokenizer::NextToken ()
154: {
155:     // skip to begin of next token
156:     while (m_str[m_pos] != '\0')
157:     {
158:         if (IsDelim (m_str[m_pos]))
159:             m_pos ++;
160:         else
161:             break;
162:     }
163: 
164:     // end of string reached?
165:     if (m_str[m_pos]  == '\0')
166:         return (char*) 0;  // no more token available
167: 
168:     // search end of token
169:     int begin = m_pos;
170:     while (m_str[m_pos] != '\0')
171:     {
172:         if (! IsDelim (m_str[m_pos]))
173:             m_pos ++;
174:         else
175:             break;
176:     }
177: 
178:     // copy token into temporary buffer
179:     char* tok = new char [m_pos - begin + 1];
180:     for (int i = begin; i < m_pos; i ++)
181:         tok[i - begin] = m_str[i];
182:     tok [m_pos - begin] = '\0';
183: 
184:     return tok;
185: }
186: 
187: Token StringTokenizer::NextTokenEx ()
188: {
189:     // skip to begin of next token
190:     while (m_str[m_pos] != '\0')
191:     {
192:         if (IsDelim (m_str[m_pos]))
193:             m_pos ++;
194:         else
195:             break;
196:     }
197: 
198:     // end of string reached?
199:     if (m_str[m_pos] == '\0')
200:         return Token();  // no more token available
201: 
202:     // search end of token
203:     int begin = m_pos;
204:     while (m_str[m_pos] != '\0')
205:     {
206:         if (! IsDelim (m_str[m_pos]))
207:             m_pos ++;
208:         else
209:             break;
210:     }
211:     
212:     // create token
213:     Token tok (m_str + begin, m_pos - begin);
214:     return tok;
215: }
216: 
217: void StringTokenizer::SkipToken ()
218: {
219: 	if (HasMoreTokens ())
220: 		NextToken ();
221: }
222: 
223: // public operators
224: StringTokenizer& StringTokenizer::operator= (const StringTokenizer& st)
225: {
226:     // prevent self-assignment
227:     if (this == &st)
228:         return *this;
229: 
230:     // release left side
231:     delete[] m_str;
232:     delete[] m_delim;
233:     delete[] m_tokens;
234: 
235:     m_str = (char*) 0;
236:     m_delim = (char*) 0;
237: 
238:     SetString (st.m_str);
239:     SetDelimiters (st.m_delim);
240: 
241:     m_pos = 0;
242:     m_tokens = (Token*) 0;
243: 
244:     return *this;
245: }
246: 
247: Token StringTokenizer::operator[] (int i)
248: {
249:     return m_tokens[i];
250: }
251: 
252: // private helper function isDelim
253: bool StringTokenizer::IsDelim (char c) const
254: {
255:     for (int i = 0; m_delim[i] != '\0'; i ++)
256:         if (m_delim[i] == c)
257:             return true;
258: 
259:     return false;
260: }
261: 
262: // output
263: ostream& operator<< (ostream& os, StringTokenizer& t)
264: {
265:     os << "[";
266:     t.Reset ();
267:     bool first = true;
268:     while (t.HasMoreTokens ())
269:     {
270:         Token tok = t.NextToken ();
271:         if (first)
272:         {
273:             os << tok;
274:             first = false;
275:         }
276:         else
277:             os << "," << tok;
278:     }
279:     os << "]";
280: 
281:     return os;
282: }

Beispiel 4. Klasse StringTokenizer: Implementierung.