Rheinwerk Computing < openbook > Rheinwerk Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger.

Inhaltsverzeichnis
Vorwort
Vorwort des Gutachters
1 Einstieg in C
2 Das erste Programm
3 Grundlagen
4 Formatierte Ein-/Ausgabe mit »scanf()« und »printf()«
5 Basisdatentypen
6 Operatoren
7 Typumwandlung
8 Kontrollstrukturen
9 Funktionen
10 Präprozessor-Direktiven
11 Arrays
12 Zeiger (Pointer)
13 Kommandozeilenargumente
14 Dynamische Speicherverwaltung
15 Strukturen
16 Ein-/Ausgabe-Funktionen
17 Attribute von Dateien und das Arbeiten mit Verzeichnissen (nicht ANSI C)
18 Arbeiten mit variabel langen Argumentlisten – <stdarg.h>
19 Zeitroutinen
20 Weitere Headerdateien und ihre Funktionen (ANSI C)
21 Dynamische Datenstrukturen
22 Algorithmen
23 CGI mit C
24 MySQL und C
25 Netzwerkprogrammierung und Cross–Plattform-Entwicklung
26 Paralleles Rechnen
27 Sicheres Programmieren
28 Wie geht’s jetzt weiter?
A Operatoren
B Die C-Standard-Bibliothek
Stichwort

Buch bestellen
Ihre Meinung?

Spacer
<< zurück
C von A bis Z von Jürgen Wolf
Das umfassende Handbuch
Buch: C von A bis Z

C von A bis Z
3., aktualisierte und erweiterte Auflage, geb., mit CD und Referenzkarte
1.190 S., 39,90 Euro
Rheinwerk Computing
ISBN 978-3-8362-1411-7
Pfeil 22 Algorithmen
Pfeil 22.1 Was sind Algorithmen?
Pfeil 22.2 Wie setze ich Algorithmen ein?
Pfeil 22.3 Sortieralgorithmen
Pfeil 22.3.1 »Selection Sort« – sortieren durch Auswählen
Pfeil 22.3.2 Insertion Sort
Pfeil 22.3.3 Bubble Sort
Pfeil 22.3.4 Shellsort
Pfeil 22.3.5 Quicksort
Pfeil 22.3.6 qsort()
Pfeil 22.3.7 Zusammenfassung der Sortieralgorithmen
Pfeil 22.4 Suchalgorithmen – Grundlage zur Suche
Pfeil 22.4.1 Lineare Suche
Pfeil 22.4.2 Binäre Suche
Pfeil 22.4.3 Binäre (Such-)Bäume
Pfeil 22.4.4 Elemente im binären Baum einordnen
Pfeil 22.4.5 Binäre Bäume traversieren
Pfeil 22.4.6 Löschen eines Elements im binären Baum
Pfeil 22.4.7 Ein binärer Suchbaum in der Praxis
Pfeil 22.4.8 Binäre Suchbäume mit Eltern-Zeiger und Threads
Pfeil 22.4.9 Ausgeglichene Binärbäume
Pfeil 22.4.10 Algorithmen für ausgeglichene Bäume – eine Übersicht
Pfeil 22.5 Hashing (Zerhacken)
Pfeil 22.5.1 Wann wird Hashing verwendet?
Pfeil 22.5.2 Was ist für das Hashing erforderlich?
Pfeil 22.5.3 Hash-Funktion
Pfeil 22.5.4 Hashing mit direkter Adressierung
Pfeil 22.5.5 Vergleich von Hashing mit binären Bäumen
Pfeil 22.6 String-Matching
Pfeil 22.6.1 Brute-Force-Algorithmus
Pfeil 22.6.2 Der Algorithmus von Knuth/Morris/Pratt (KMP)
Pfeil 22.6.3 Weitere String-Matching-Algorithmen
Pfeil 22.7 Pattern Matching (reguläre Ausdrücke)
Pfeil 22.8 Backtracking
Pfeil 22.8.1 Der Weg durch den Irrgarten
Pfeil 22.8.2 Das 8-Dame-Problem


Rheinwerk Computing - Zum Seitenanfang

22.7 Pattern Matching (reguläre Ausdrücke) topZur vorigen Überschrift

Jeder, der mit einer UNIX/Linux-Maschine zu tun hat, kennt wohl die regulären Ausdrücke. Reguläre Ausdrücke sind auch eine Form der Suche nach Zeichenketten, nur erheblich komfortabler und komplexer.

Der Begriff »regulärer Ausdruck« stammt von dem Sprachwissenschaftler Noam Chomsky und wird in der Informatik verwendet. Es gibt zwar mehrere Varianten von regulären Ausdrücken, doch haben alle dasselbe Ziel.

Bei einem regulären Ausdruck geht es darum, Muster aus Buchstaben zu beschreiben, und dies zusammen mit Wiederholungen, Alternativen und Abkürzungen für Zeichenklassifizierungen wie Ziffern oder Buchstaben. Das bekannteste Beispiel, mit dem sogar MS-DOS klarkommt und das jeder kennen dürfte, ist die Wildcard (*):

dir t*.txt

oder unter UNIX:

ls -l t*.txt

So werden alle Textdateien ausgegeben, die mit »t« beginnen und mit ».txt« enden:

text.txt
test.txt
total.txt

Reguläre Ausdrücke sind keine Funktionen, sondern es handelt sich um eine echte Sprache mit formaler Grammatik, bei der jeder Ausdruck eine präzise Bedeutung hat.

Hierzu folgen einige Funktionen in der Praxis, wobei diejenigen, die mit den regulären Ausdrücken überhaupt nicht vertraut sind, einen kleinen Einblick erhalten, und Anwender, die reguläre Ausdrücke schon häufiger verwendet haben, sehen werden, wie reguläre Ausdrücke in C geschrieben werden können.

Es sei darauf hingewiesen, dass es sich dabei nicht um eine umfassende Anleitung zu regulären Ausdrücken handelt, sondern vielmehr um einen kurzen Überblick.

Das Programm, das erstellt werden soll, liest Zeile für Zeile aus einer Datei aus. Die erste Funktion, die das Pattern Matching einleitet, sieht so aus:

int pmatch(char *ausdruck, char *text) {
#ifdef __unix__
   if(ausdruck[0] == '^')
#elif __WIN32__
   if(ausdruck[0] == '#')
#endif
      return match(ausdruck+1, text);
   else {
      for( ; *text != '\0'; *text++)
         if(match(ausdruck, text))
            return 1;
   }
   return 0;
}

Zuerst wird überprüft, ob der zu matchende Ausdruck am Anfang einer Zeile vorkommt. Dies ist gegeben, wenn der Ausdruck mit dem Zeichen '^' beginnt. Beispielsweise geben Sie als Suchstring folgenden Ausdruck an:

^hallo

Somit müssen die ersten fünf Zeichen einer Zeile in text mit der Zeichenfolge "hallo" übereinstimmen. Beispiele:

hallo welt wie gehts   (Gefunden, da am Anfang der Zeile)
  hallo welt wie gehts (Missmatch -> nicht gefunden)

Im Fall des Zeichens '^' muss der zu matchende Ausdruck inkrementiert werden, damit dieses Zeichen nicht mit verglichen wird. Bei Nichtverwendung des Zeichens '^' wird die Matching-Funktion ganz normal – Zeichen für Zeichen – aufgerufen.


Hinweis

Damit sich dieses Beispiel auch unter MS-DOS/Win32 realisieren lässt, verwenden Sie bitte statt des Zeichens '^' das Zeichen '#'. Daher auch die bedingte Kompilierung in der Funktion.


Jetzt folgt die Matching-Funktion match():

int match(char *ausdruck, char *text) {
   if(ausdruck[0] == '\0')
      return 1;
   if(ausdruck[1] == '*')
      return wildcard(ausdruck[0], ausdruck+2, text);
   if(ausdruck[0] == '$' && ausdruck[1] == '\0')
      return *text == '\0';
   if(*text != '\0' && (ausdruck[0]== '.'||
     ausdruck[0] == *text) )
      return match(ausdruck+1, text+1);
   return 0;
}

Zuerst wird getestet, ob das Ende des Patterns schon gekommen ist ('\0'). Danach wird überprüft, ob eine Wildcard (*) angegeben ist. Falls ja, wird die entsprechende Funktion aufgerufen, worauf in Kürze eingegangen wird. Das Zeichen '$' bedeutet beim Matching Zeilenende. Als Beispiel dient uns folgende Zeile:

match und$ *.txt

Damit werden alle Ausdrücke gefunden, bei denen die Zeile mit »und« endet. Einige Beispiele:

Ein Text, der mit und endet und            /* Gefunden */
Der Text endet nicht mit und und.          /* Missmatch */
qwert asdf qwert asdf qwert  und           /* Gefunden */
und was jetzt                              /* Missmatch */

Um zu überprüfen, dass nicht nach dem Zeichen '$' gesucht wird, sondern dass es auch wirklich das gewünschte »und« am Ende der Zeile ist (in diesem Fall) ist, wird gleich darauf getestet, ob das nächste Zeichen des Ausdrucks das Endzeichen '\0' ist. Die nächste Überprüfung

if(*text != '\0' &&(ausdruck[0] == '.' ||  ausdruck[0] == *text))

testet, ob nicht schon das Ende gekommen ist, und das nächste Zeichen ein beliebiges sein darf (.) oder das Zeichen im Ausdruck mit demjenigen im Text übereinstimmt. Der Punkt steht somit für ein beliebiges Zeichen, abgesehen vom Zeichenende. Falls diese Bedingung zutrifft, wird die Funktion rekursiv erneut mit den nächsten Zeichen aufgerufen. Der rekursive Aufruf erfolgt so lange, bis eine der Bedingungen in dieser Funktion einen return-Wert (0 == keine Übereinstimmung oder 1 == Übereinstimmung gefunden) zurückliefert.

Jetzt die (primitive) Wildcard-Funktion:

int wildcard(int c, char *ausdruck, char *text) {
   for( ;*text != '\0' && (*text == c || c == '.'); *text++)
      if(match(ausdruck, text))
         return 1;
   return 0;
}

Zugegeben, dies ist eine schwache Wildcard-Funktion; aber sie funktioniert. Was bedeutet aber dieses Sternchen beim Pattern Matching? Der Stern zeigt an, dass das letzte Zeichen (oder der Inhalt) mindestens einmal oder mehrmals vorkommen kann, aber nicht vorkommen muss. Zum Abschluss sehen Sie noch das vollständige Listing:

/* regular_expression.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUF 4096

int pmatch(char *, char *);
int match(char *, char *);
int wildcard(int, char *, char *);
int my_grep(char *, FILE *, char *);

int pmatch(char *ausdruck, char *text) {
   if(ausdruck[0] == '^')
      return match(ausdruck+1, text);
   for( ; *text != '\0'; *text++)
      if(match(ausdruck, text))
         return 1;
   return 0;
}

int match(char *ausdruck, char *text) {
   if(ausdruck[0] == '\0')
      return 1;
#ifdef __unix__
   if(ausdruck[1] == '*')
#elif __WIN32__
   if(ausdruck[1] == '~')
#endif
      return wildcard(ausdruck[0], ausdruck+2, text);
   if(ausdruck[0] == '$' && ausdruck[1] == '\0')
      return *text == '\0';
   if(*text != '\0' && ( ausdruck[0] == '.' ||
     ausdruck[0] == *text))
      return match(ausdruck+1, text+1);
   return 0;
}
int wildcard(int c, char *ausdruck, char *text) {
   for( ;*text != '\0' && (*text == c || c == '.'); *text++)
      if(match(ausdruck, text))
         return 1;
   return 0;
}

int my_grep(char *ausdruck, FILE *f, char *name) {
   int n, nmatch=0;
   int line=0;
   char buffer[BUF];

   while(fgets(buffer, sizeof(buffer), f) != NULL) {
      line++;
      n = strlen(buffer);
      if(n > 0 && buffer[n-1] == '\n')
         buffer[n-1] = '\0';
      if(pmatch(ausdruck, buffer)) {
         nmatch++;
         if(name != NULL)
            printf("%d. ",line);
      }
   }
   if(nmatch!=0)
      printf("Zeile in der Datei %s (insg.%d)\n\n",name,nmatch);
   return nmatch;
}

int main(int argc, char *argv[]) {
   int i, nmatch=0;
   FILE *f;

   if(argc <= 2) {
      fprintf(stderr, "Verwendung des Programms : "
         "%s pattern quelle\n\n",*argv);
      return EXIT_FAILURE;
   }
   else {
      for(i = 2; i < argc; i++) {
         f = fopen(argv[i], "r");
         if(NULL == f) {
            fprintf(stderr, "Konnte %s nicht "
               "oeffnen\n",argv[i]);
            continue;
         }
         if(my_grep(argv[1],f, argv[i]) > 0)
            nmatch++;
         fclose(f);
      }
   }
   printf("%d Dateien mit passenden Pattern %s gefunden\n",
      nmatch, argv[1] );
   return EXIT_SUCCESS;
}

Hier folgen noch ein paar Matching-Beispiele zum Programm (der Programmname sei match und der Name der Datei test.txt). Folgende Textdatei soll gematcht werden:

ist
 ist
  ist.

Tabelle 22.2 Einige Matching-Beispiele

Matching Gefunden in Zeile
match ^ist test.txt

1

match ^ist$ test.txt

1

match ist$ test.txt

1, 2

match ist test.txt

1, 2, 3

match .ist test.txt

2, 3

match ist. test.txt

3

match .s. test.txt

1, 2, 3

match .s.$ test.txt

1, 2

match ^...$ test.txt

1

match i*. test.txt

1, 2, 3

match ^i*. test.txt

1


Sie sehen schon, was für einen gewaltigen Funktionsumfang Sie mit wenigen Zeilen Code auf die Beine stellen können. Dabei stellt das Programm und das bisher vorgestellte Pattern Matching nur einen Bruchteil dessen dar, wozu Pattern Matching wirklich in der Lage ist.

Sollten Sie also für Ihr Programm reguläre Ausdrücke benötigen, können Sie eigene Funktionen schreiben oder auf entsprechende Funktionen der Headerdatei <regex.h> zugreifen. Allerdings entsprechen diese Funktionen dem POSIX-Standard und sind vorwiegend in der UNIX-Welt zu Hause. MS-Windows-Anwender können diese Bibliothek aber zum Beispiel mit dem gcc-Compiler unter der Cygwin-Umgebung auch verwenden.



Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen. >> Zum Feedback-Formular
<< zurück
  
  Zum Katalog
Zum Katalog: C von A bis Z

 C von A bis Z
Jetzt bestellen


 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Buchtipps
Zum Katalog: C/C++






 C/C++


Zum Katalog: Einstieg in C






 Einstieg in C


Zum Katalog: Schrödinger programmiert C++






 Schrödinger
 programmiert C++


Zum Katalog: C++ Handbuch






 C++ Handbuch


Zum Katalog: IT-Handbuch für Fachinformatiker






 IT-Handbuch für
 Fachinformatiker


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Rheinwerk Verlag GmbH 2009
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Rheinwerk Computing]

Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de