Laden...

Nested RegularExpression: Hat ein String eine ausbalancierte Anzahl von #regions?

Erstellt von TripleX vor 13 Jahren Letzter Beitrag vor 13 Jahren 1.042 Views
TripleX Themenstarter:in
328 Beiträge seit 2006
vor 13 Jahren
Nested RegularExpression: Hat ein String eine ausbalancierte Anzahl von #regions?

Hallo Gemeinde,

Im Zuge eines aktuellen Projekts möchte ich schauen ob ein gegebener String eine ausgewogene und sinnvolle Anzahl an #region's und #endregion's besitzt.

Auf der Suche nach einer geeigneten Lösung bin ich auf folgendes:

Moving on to what is undoubtedly the most common usage of balancing groups, following is an example of matching balanced sets of parentheses. It's taken from Jeffrey Friedl's book, Mastering Regular Expressions.

\(  
  (?>  
  	[^()]+  
  |  
  	\( (?<Depth>)  
  |  
  	\) (?<-Depth>)  
  )*  
  (?(Depth)(?!))  
\)  
  

Quelle:
>
.

Dieses Beispiel habe ich versucht auf meinen Fall abzuändern, doch ich kriege es nicht hin. Ich habe mehrere Ansätze probiert, folgender sollte meiner Meinung nach funktionieren. Dass das "matchen" der regions nicht ganz korrekt ist weiß ich (z.B. könnte eine Region auskommentiert sein, ...) aber mir geht es erst mal nur ums Prinzip:

      (?>
           \#region(?<Counter>) 
        | \#endregion(?<-Counter>)
        | (  (?!\#region) | (?!\#endregion))+
       )*
      (?(Counter)(?!))

Dieser Ansatz klappt aber nicht, denn wenn ich Regex.IsMatch() ausführe bekomme ich falsche Ergebnisse.

Mir geht es also nur darum nachzusehen ob in einem string die Anzahl der regions ausbalanciert ist, z.B. sollte hier false ausgegeben werden:

#region
#endregion
#endregion

Ist dies überhaupt möglich mit Regex oder muss ich da anders vorgehen?

MfG TripleX

Träume nicht dein Leben sondern lebe deinen Traum.
Viele Grüße, David Teck

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo TripleX,

ohne Not würde ich Ausgleichsgruppen/balancing groups nicht verwenden.

Siehe Parser für BBcode? für einen Ansatz, wie man die Prüfung der Klammerungsebenen aus Regex raushält.

herbivore

799 Beiträge seit 2007
vor 13 Jahren

Hast du noch mehr vor in diesem Check oder prüfst du nur ob #region und #endregion gleich oft vorkommen? Das könntest du ja auch mit dem Zähler aus Matches prüfen in dem du einmal nach #region und einmal nach #endregion suchst.

As a man thinketh in his heart, so he is.

  • Jun Fan
    Es gibt nichts Gutes, außer man tut es.
  • Erich Kästner
    Krawutzi-Kaputzi
  • Kasperl
TripleX Themenstarter:in
328 Beiträge seit 2006
vor 13 Jahren

ohne Not würde ich Ausgleichsgruppen/balancing groups nicht verwenden.

Naja Not ist nicht wirklich da, ich könnte den Check auch einfach übergehen, dann würde die Ausgabe meiner TreeView (mit den regions) nicht sauber sein. Ich würde lieber eine Meldung anzeigen, welche besagt dass eine eine nicht ausgeglichene Anzahl von region's im Code vorhanden sind.

Wenn ich aber bedenke, dass das dauernde Prüfen auf solch einen Fall sich negativ auswirkt auf die Perfomance könnte ich auch auf diese Funktionalität verzichten. Denn solch ein Fall kommt doch relativ selten vor ... . Mich würde trotzdem interessieren ob sowas überhaupt möglich ist, denn ich habe es bisher nicht geschafft 😉.

Hast du noch mehr vor in diesem Check oder prüfst du nur ob #region und #endregion gleich oft vorkommen?

Jein, also #region und #endregion sollte einerseits gleich oft vorkommen, aber es sollte auch sinnvoll verschachtelt sein, also wenn man z.B. folgenden Text hat:

#region
#endregion
#endregion
#region

dann kommen sie zwar gleich oft vor, aber nicht in einer korrekten logischen Reihenfolge.

€dit: Achja, ganz vergessen - es besteht Not, denn wenn ich irgendwo #region schreibe ohne passenden Endtag bleibt mein regex für die Suche nach regions hängen ... 😦 Werde mich jetzt erstmal mit folgenden Code abfinden:

        public bool HasBalancedRegions(string text)
        {
            int opened = Regex.Matches(text, RegexStartOfRegion, RegexOptions.Singleline | RegexOptions.Compiled | RegexOptions.Multiline).Count;
            int closed = Regex.Matches(text, RegexEndOfRegion, RegexOptions.Singleline | RegexOptions.Compiled | RegexOptions.Multiline).Count;
            return (opened-closed == 0);
        }

Träume nicht dein Leben sondern lebe deinen Traum.
Viele Grüße, David Teck

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo TripleX,

wobei HasBalancedRegions auch bei

#endregion
#region

true liefern würde, also die Reihenfolge nicht berücksichtigt. Machs besser so, wie in dem verlinkten Thread beschrieben. Da hast du die voll Kontrolle.

herbivore

TripleX Themenstarter:in
328 Beiträge seit 2006
vor 13 Jahren

wobei HasBalancedRegions auch bei

#endregion
#region

true liefern würde, also die Reihenfolge nicht berücksichtigt.

Im Prinzip hast du recht. Bei meiner Implementierung gibt es trotzdem keine Probleme.

Mein Code sieht jetzt folgendermaßen aus:

Ich habe eine Methode, die aufgerufen hat sobald der Benutzer für mich wichtige Änderungen getätigt hat:

        internal void UpdateRegionsFromCurrentDocument()
        {
            try
            {
                RegionsInCurrentTextDocument = _regionAnalyzer.GetRegionsFromText(_dteWrapper.ActiveTextDocumentContent);
                CurrentTextDocumentHasUnbalancedRegions = false;
            }
            catch (UnbalancedRegionException)
            {
                CurrentTextDocumentHasUnbalancedRegions = true;
            }
        }

Und hier die zwei Methoden, welche zum einen prüft ob ein Text eine balancierte Anzahl von regions hat, und zum anderen die Regions als Liste zurück gibt:

        public bool HasBalancedRegions(string text)
        {
            int opened = Regex.Matches(text, RegexStartOfRegion, RegexOptions.Singleline | RegexOptions.Compiled | RegexOptions.Multiline).Count;
            int closed = Regex.Matches(text, RegexEndOfRegion, RegexOptions.Singleline | RegexOptions.Compiled | RegexOptions.Multiline).Count;
            return (opened - closed == 0);
        }
        public ObservableCollection<Region> GetRegionsFromText(string text, int startLineNumber = 1)
        {
            if (!HasBalancedRegions(text)) throw new UnbalancedRegionException();

            ObservableCollection<Region> regions = new ObservableCollection<Region>();

            Regex regex = new Regex(RegexSearchRegion, RegexOptions.Singleline | RegexOptions.Compiled | RegexOptions.Multiline);
            MatchCollection matches = regex.Matches(text);
            foreach (Match match in matches)
            {
                string[] newLineArr = new string[] { Environment.NewLine };
                int newLinesBeforeMatch = text.Substring(0, match.Index).Split(newLineArr, StringSplitOptions.None).Length - 1;
                int newLinesBetweenMatch = match.Value.Split(newLineArr, StringSplitOptions.None).Length - 1;

                int startLine = startLineNumber + newLinesBeforeMatch;
                int endLine = startLine + newLinesBetweenMatch;

                Region region = new Region(match.Groups["name"].Value.Trim(), startLine, endLine);
                region.Children = GetRegionsFromText(match.Groups["text"].Value, startLine + 1);
                regions.Add(region);
            }
            return regions;
        }

nun wird, wenn der User (bei meinem testcode) #endregion eingibt beim allersten durchlauf gleich eine Exception geworfen. Wenn er nun #region eingibt, wird später, beim holen der Children eine Exception geworfen --> alles funktioniert wie ich möchte 😃

Wenn der User in einem neuen Dokument nur: #endregion\r\n#region eintippt, dann kommt zwar keine Meldung dass es unbalanced ist aber wenigstens freezed mein Programm nicht beim auswerten des Regex. Und gerade dieses freezen wollte ich beheben. Außerdem lässt sich der Code bei dem eingegebenen Text eh net kompilieren, also ist das halb so schlimm dass ich es nicht mitbekomme.

Vielen Dank euch beiden ... Problem behoben 😉

Träume nicht dein Leben sondern lebe deinen Traum.
Viele Grüße, David Teck