Sprawdzanie poprawności wyrażenia logicznego za pomocą nawiasów w języku C#

Question

Chcę zweryfikować ciąg znaków w języku C#, który zawiera wyrażenie logiczne w nawiasach. Ciąg powinien zawierać wyłącznie cyfry 1-9, nawiasy okrągłe, "LUB", "AND".

Przykładami dobrych struny

"1 i 2"

"2 lub 4"

"4 i (3 lub 5)"

"2"

I tak dalej ...

Nie jestem pewien, czy wyrażenie regularne jest wystarczająco elastyczne dla tej ta sk. Czy istnieje dobry sposób osiągnięcia tego w C#?

Answer 1

Jest to prawdopodobnie prostsze dzięki prostemu analizatorowi składni. Ale ty can do this z.NET regex przy użyciu balancing groups i zdając sobie sprawę, że jeśli nawiasy są usuwane z łańcucha, zawsze masz ciąg dopasowany prostym wyrażeniem, takim jak ^\d+(?:\s+(?:AND|OR)\s+\d+)*\z.

Wszystko co musisz zrobić, to użyć grup równoważących, aby upewnić się, że nawiasy są zrównoważone (i są we właściwym miejscu w odpowiedniej formie).

Przepisanie wyrażenia powyższej trochę: (. (?x) sprawia, że ​​silnik regex ignorować wszystkie białe znaki i komentarze w strukturze, dzięki czemu może być bardziej czytelny)

(?x)^ 
OPENING 
\d+ 
CLOSING 
(?: 
    \s+(?:AND|OR)\s+ 
    OPENING 
    \d+ 
    CLOSING 
)* 
BALANCED 
\z 

Gdzie OPENING dopasowuje dowolny liczba (0 włączone) otworu nawiasami

\s* (?: (?<open> \() \s*)* 

CLOSING pasuje do dowolnej liczby wsporników zamykających również upewniając się, że grupa wyważanie jest zbilansowany:

\s* (?: (?<-open> \)) \s*)* 

i BALANCED wykonuje test bilansujący, w przeciwnym razie, jeśli tam są bardziej otwarte nawiasy następnie zamknięty:

(?(open)(?!)) 

Nadanie wyrażenia:

(?x)^ 
\s* (?: (?<open> \() \s*)* 
\d+ 
\s* (?: (?<-open> \)) \s*)* 
(?: 
    \s+(?:AND|OR)\s+ 
    \s* (?: (?<open> \() \s*)* 
    \d+ 
    \s* (?: (?<-open> \)) \s*)* 
)* 
(?(open)(?!)) 
\z 

Jeśli nie chcesz, aby losowe spacje były usuwane, co \s*.

Przykład

Patrz Demo w IdeOne. Wyjście:

matched: '2' 
matched: '1 AND 2' 
matched: '12 OR 234' 
matched: '(1) AND (2)' 
matched: '(((1)) AND (2))' 
matched: '1 AND 2 AND 3' 
matched: '1 AND (2 OR (3 AND 4))' 
matched: '1 AND (2 OR 3) AND 4' 
matched: ' (1 AND (2 OR (3 AND 4) )' 
matched: '((1 AND 7) OR 6) AND ((2 AND 5) OR (3 AND 4))' 
matched: '(1)' 
matched: '(((1)))' 
failed: '1 2' 
failed: '1(2)' 
failed: '(1)(2)' 
failed: 'AND' 
failed: '1 AND' 
failed: '(1 AND 2' 
failed: '1 AND 2)' 
failed: '1 (AND) 2' 
failed: '(1 AND 2))' 
failed: '(1) AND 2)' 
failed: '(1)() AND (2)' 
failed: '((1 AND 7) OR 6) AND (2 AND 5) OR (3 AND 4))' 
failed: '((1 AND 7) OR 6) AND ((2 AND 5 OR (3 AND 4))' 
failed: '' 

Answer 2

ANTLER Generator parsera?

krótki sposobem osiągnięcia tego celu w C#

Chociaż może to być overkill jeśli jej tylko liczb i OR + I

Answer 3

Całkiem prosto:

W pierwszym etapie Musisz określają leksemów (cyfry, nawiasy lub operator) za pomocą prostego porównywania ciągów znaków.

W drugim etapie należy zdefiniować zmienną liczbą zamkniętych wspornik (bracketPairs), która może być obliczona według następującego algorytmu dla każdego lexem:

jeśli prąd lexem jest „(”, następnie bracketPairs ++;

, jeśli aktualny leksemu jest ")", a następnie "bracketPairs".

W przeciwnym razie nie modyfikuj bracketPairs.

Na koniec, jeśli znane są wszystkie leksemy i bracketPairs == 0, wówczas wyrażenie wejściowe jest prawidłowe.

Zadanie jest nieco bardziej skomplikowane, jeśli trzeba zbudować AST.

Answer 4

co chcesz są „zbalansowane grupy”, z nich można dostać wszystkie definicje bracet, wtedy wystarczy prosty ciąg parsowania

http://blog.stevenlevithan.com/archives/balancing-groups

http://msdn.microsoft.com/en-us/library/bs2twtah.aspx#balancing_group_definition

Answer 5

Jeśli chcesz tylko do sprawdzania poprawności ciąg wejściowy, możesz napisać prosty analizator składni. Każda metoda pobiera pewien rodzaj danych wejściowych (cyfra, nawiasy, operator) i zwraca pozostały ciąg znaków po dopasowaniu. Wyjątek jest zgłaszany, jeśli nie można dopasować.

public class ParseException : Exception { } 

public static class ExprValidator 
{ 
    public static bool Validate(string str) 
    { 
     try 
     { 
      string term = Term(str); 
      string stripTrailing = Whitespace(term); 

      return stripTrailing.Length == 0; 
     } 
     catch(ParseException) { return false; } 
    } 

    static string Term(string str) 
    { 
     if(str == string.Empty) return str; 
     char current = str[0]; 

     if(current == '(') 
     { 
      string term = LBracket(str); 
      string rBracket = Term(term); 
      string temp = Whitespace(rBracket); 
      return RBracket(temp); 
     } 
     else if(Char.IsDigit(current)) 
     { 
      string rest = Digit(str); 
      try 
      { 
       //possibly match op term 
       string op = Op(rest); 
       return Term(op); 
      } 
      catch(ParseException) { return rest; } 
     } 
     else if(Char.IsWhiteSpace(current)) 
     { 
      string temp = Whitespace(str); 
      return Term(temp); 
     } 
     else throw new ParseException(); 
    } 

    static string Op(string str) 
    { 
     string t1 = Whitespace_(str); 
     string op = MatchOp(t1); 
     return Whitespace_(op); 
    } 

    static string MatchOp(string str) 
    { 
     if(str.StartsWith("AND")) return str.Substring(3); 
     else if(str.StartsWith("OR")) return str.Substring(2); 
     else throw new ParseException(); 
    } 

    static string LBracket(string str) 
    { 
     return MatchChar('(')(str); 
    } 

    static string RBracket(string str) 
    { 
     return MatchChar(')')(str); 
    } 

    static string Digit(string str) 
    { 
     return MatchChar(Char.IsDigit)(str); 
    } 

    static string Whitespace(string str) 
    { 
     if(str == string.Empty) return str; 

     int i = 0; 
     while(i < str.Length && Char.IsWhiteSpace(str[i])) { i++; } 

     return str.Substring(i); 
    } 

    //match at least one whitespace character 
    static string Whitespace_(string str) 
    { 
     string stripFirst = MatchChar(Char.IsWhiteSpace)(str); 
     return Whitespace(stripFirst); 
    } 

    static Func<string, string> MatchChar(char c) 
    { 
     return MatchChar(chr => chr == c); 
    } 

    static Func<string, string> MatchChar(Func<char, bool> pred) 
    { 
     return input => { 
      if(input == string.Empty) throw new ParseException(); 
      else if(pred(input[0])) return input.Substring(1); 
      else throw new ParseException(); 
     }; 
    } 
} 

Answer 6

Jeśli wziąć pod uwagę logiczną wyrażenia jak generowane przez formalnej gramatyki pisanie parser jest łatwiejsze.

Zrobiłem biblioteki open source do interpretacji prostych wyrażeń logicznych. Możesz spojrzeć na to na GitHub, w szczególności spojrzeć na klasę AstParser i Lexer.