Laden...

Regex: Anzahl öffnende = Anzahl schließende Klammern

Erstellt von VizOne vor 18 Jahren Letzter Beitrag vor 18 Jahren 3.646 Views
VizOne Themenstarter:in
1.373 Beiträge seit 2004
vor 18 Jahren
Regex: Anzahl öffnende = Anzahl schließende Klammern

Hallo Community!

Ich habe strings in folgendem Format:
a(c) + b(a + b + c) + d(a(b) + d(c))

Jetzt möchte ich diesen String jeweils auf oberster ebene beim +-Zeichen splitten. Das gewünschte Resultat wäre:
a(c), b(a + b + c), d(a(b) + d(c))

Die Teilstrings würde ich dann rekursive mit dem gleichen Splitmuster weiterbearbeiten.

Um die jeweils oberster Ebene zu erhalten müssen öffnende und schließende Klammern sich jeweils ergänzen. Wie formuliere ich das als Regular Expression?

Hab mir für die Überbrückungszeit eine "manuelle" Lösung geschrieben:


static List<string> SplitPlus( string input ) {
	// TODO reimplement as regex

	List<string> strings = new List<string>();

	int openBrackets = 0;
	int left = 0;
	int length = 0;

	foreach( char c in input ) {
		++length;

		switch( c ) {
			case '{':
				++openBrackets;
				break;
			case '}':
				--openBrackets;
				break;
			case '+':
				// only add substring if + appeared on top level
				if( openBrackets == 0 ) {
					// copy substring, omit '+'
					strings.Add( input.Substring( left, length - 1 ) );
					left += length;
					length = 0;
				}
				break;
		}
	}
	// add rest
	strings.Add( input.Substring( left ) );
	return strings;
}

Aber ich denke, dass da mit Regex was zu machen ist. Danke für eure Hilfe!

MfG VizOne

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo VizOne,

nö, RegEx sind gerade nicht in der Lage mit der Paarigkeit von Klammern umzugehen. Du bräuchtest mindestens einen Parser für kontextfreie Sprachen. Aber deine rekursive Vorgehensweise finde ich sehr sinnvoll.

herbivore

I
1.739 Beiträge seit 2005
vor 18 Jahren

Klar lässt sich mit RegEx was machen...
Wenn sich das Problem auf das was du geschilderst hast konzentriert, behalte diese Lösung, sie ist besser(performanter und übersichtlicher). RegEx ist rel. langsam, dafür universeller. Deine Lösung ist für dieses Problem besser.
Das war nur mein Senf dazu. Wenn du nur mehr über RegEx wissen willst bemühe die Forumssuche, oder google danach(Java etc. ist in dem Fall fast equivalent).
Für den beschriebenen Fall ist deine Lösung defintiv gut genug.

C
980 Beiträge seit 2003
vor 18 Jahren

Original von ikaros
Klar lässt sich mit RegEx was machen...

Nein. Herbivore hat schon recht, dafür bräuchtest du zumindest einen Zähler (-> somit eine kontextfreie Sprache). Die Sprache ist also nicht regulär und lässt sich auch nicht auf regulären Ausdrücken abbilden (siehe Pumping Lemma)...

Ich würde auch bei deiner Lösung bleiben, oder sie in eine allgemeine (klassische) Stackmaschine ausbauen falls du die Ausdrücke gleich auswerten möchtest ...

4.207 Beiträge seit 2003
vor 18 Jahren

Das mit einem Stack habe ich gerade für das Validieren von BBcode entwickelt (zwinker zu Herbivore), wo ich letztlich auch prüfen muss, ob die öffnenden Tags zu den schließenden passen.

Falls Interesse besteht, kann ich die Klasse gerne zur Verfügung stellen.

Wissensvermittler und Technologieberater
für .NET, Codequalität und agile Methoden

www.goloroden.de
www.des-eisbaeren-blog.de

M
456 Beiträge seit 2004
vor 18 Jahren

Das geht eigentlich schon fast in Richtung Compilerbau (Lexikalischer Scanner, Parser).
Schau dir einfach mal an wie man einen Parser (lehrbuchmäßig) implementiert, dann sollte das recht einfach gehen.

Schau mal hier (speziell unter Modell-Compiler->ExpressionParser Beispiele):
http://vhb.fh-regensburg.de/co/

I am Jack's smirking revenge.
I am Jack's raging bile duct.
I am Jack's cold sweat.
I am Jack's complete lack of surprise.
I am Jack's broken heart.
I am Jack's wasted life.

VizOne Themenstarter:in
1.373 Beiträge seit 2004
vor 18 Jahren

Oha, eigentlich hätte ich selbst drauf kommen können, dass es mit ner RegEx nicht geht. Letztes Semester an der Uni noch kontextfreie Sprachen, Pumping Lemma etc gehabt. Peinlich, peinlich. Übrigens: ja, ich habe das Fach bestanden. Wie war das? Man lernt fürs Leben? 😉

Danke auf jeden Fall für eure Bemühungen. Ich lasse es so, wie es ist.

MfG VizOne

1.985 Beiträge seit 2004
vor 18 Jahren

Original von Der Eisbär
Das mit einem Stack habe ich gerade für das Validieren von BBcode entwickelt (zwinker zu Herbivore), wo ich letztlich auch prüfen muss, ob die öffnenden Tags zu den schließenden passen.

Falls Interesse besteht, kann ich die Klasse gerne zur Verfügung stellen.

Hallo Der Eisbar,

ich lese Deinen Beitrag ja jetzt erst 🙂. Ich bin an der Klasse interessiert. Ist das nicht evtl. auch was für die Komponentensammlung?
Das Parsen kann ja wahrscheinlich einfach erweitert werden oder nicht und dann haben mit Sicherheit noch andere Leute interesse daran.

Gruß,
Fabian

"Eine wirklich gute Idee erkennt man daran, dass ihre Verwirklichung von vornherein ausgeschlossen erscheint." (Albert Einstein)

Gefangen im magischen Viereck zwischen studieren, schreiben, lehren und Ideen umsetzen…

Blog: www.fabiandeitelhoff.de