Validar una expresión booleana con corchetes en C#

Question

Quiero validar una cadena en C# que contiene una expresión booleana con corchetes. La cadena solo debe contener los números del 1 al 9, corchetes, "O", "Y".

Ejemplos de buenas cadenas:

"1 y 2"

"2 o 4"

"4 y (3 o 5)"

"2"

Y así sucesivamente ...

No estoy seguro de si la expresión regular es lo suficientemente flexible para esta ta sk. ¿Hay alguna manera buena de lograr esto en C#?

Answer 1

Probablemente sea más fácil hacer esto con un analizador simple. Pero usted can do this con.NET regex usando balancing groups y dándose cuenta de que si los corchetes se eliminan de la cadena, siempre tendrá una cadena que coincida con una expresión simple como ^\d+(?:\s+(?:AND|OR)\s+\d+)*\z.

Así que todo lo que tiene que hacer es usar grupos de equilibrio para asegurarse de que los soportes estén equilibrados (y estén en el lugar correcto en la forma correcta).

Reescribiendo la expresión anterior un poco: (. (?x) hace que el motor de expresiones regulares ignorar todos los espacios en blanco y los comentarios en el patrón, por lo que se puede hacer más legible)

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

Dónde OPENING coincide con cualquier número (0 incluido) de soportes de apertura:

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

CLOSING coincide con cualquier número de tramos de cierre también debe asegurarse de que el grupo de equilibrado está equilibrado:

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

y BALANCED realiza una comprobación de equilibrio, fallando si hay soportes más abiertas cierran:

(?(open)(?!)) 

Dar la expresión:

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

Si no desea permitir espacios aleatorios, elimine cada \s*.

Ejemplo

Ver demostración en IdeOne. Salida:

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 Parser Generator?

un corto camino de lograr esto en C#

Aunque puede ser una exageración si es sólo números y O + y

Answer 3

Bastante simple:

A primera etapa se debe determ lexemas (dígito, corchete u operador) con comparsion simple de cuerdas.

En la segunda etapa se debe definir la variable de recuento de soporte cerrado (bracketPairs), que se puede calcular mediante el siguiente algoritmo para cada Lexem:

si Lexem actual es '(', luego bracketPairs ++;

si el lexema actual es ')', luego bracketPairs--.

Else no modifica bracketPairs.

Al final, si se conocen todos los lexemas y bracketPairs == 0, la expresión de entrada es válida.

La tarea es un poco más compleja, si es necesario construir AST.

Answer 4

lo que quiere son "grupos equilibrados", con ellos se puede conseguir todas las definiciones bracet, a continuación, sólo tiene una cadena simple análisis

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

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

Answer 5

Si sólo desea validar la cadena de entrada, puede escribir un analizador simple. Cada método consume un cierto tipo de entrada (dígito, corchetes, operador) y devuelve la cadena restante después de la coincidencia. Se lanza una excepción si no se puede hacer una coincidencia.

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

Si se tiene en cuenta una expresión booleana como generado por una gramática formal escribir un analizador es más fácil.

Hice una biblioteca de código abierto para interpretar expresiones booleanas simples. Puede echarle un vistazo en GitHub, en particular, consulte la clase AstParser y Lexer.