Confirm boolean expression with brackets in C #

Question

I want to check a string in C # that contains a boolean expression with brackets. The string should contain only the numbers 1-9, parentheses, "OR", "AND".

Examples of good lines:

"1 AND 2"

"2 OR 4"

"4 AND (3 OR 5)"

"2"

And so on...

I'm not sure that regex is flexible enough for this task. Is there a good short way to achieve this in C #?

Answer 1

It is probably easier to do this with a simple parser. But you can do it with .NET regex, using balancing groups and realizing that if the brackets are removed from the string, you always have a string matched by a simple expression like ^\d+(?:\s+(?:AND|OR)\s+\d+)*\z .

So, all you have to do is use balancing groups to make sure that the brackets are balanced (and are in the right place in the correct form).

Rewriting the expression above a bit:

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

( (?x) makes the regex mechanism ignore all spaces and comments in the template, so it can be made more readable.)

Where OPENING matches any number (0 included) of opening brackets:

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

CLOSING matches any number of closing brackets, while also providing a balanced balancing group:

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

and BALANCED performs a balancing check if there are no open brackets closed:

 (?(open)(?!)) 

Providing an expression:

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

If you do not want random spaces to remove each \s* .

Example

See the demo at IdeOne . Exit:

 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

If you just want to check the input string, you can write a simple parser. Each method uses a specific type of input (number, brackets, operator) and returns the remaining line after matching. An exception is thrown if a match cannot be made.

 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 3

ANTLER Generator Parser?

short way to achieve this in C #

Although it can be brute force if its fair numbers and OR + AND

Answer 4

Pretty simple:

In the first step, you must define tokens (a digit, a bracket, or an operator) with simple string matching.

In the second step, you must define the count variable of the closed bracket (bracketPairs), which can be calculated using the following algorithm for each token:

if the current token is '(', then bracketPairs ++;

if the current token is ')', then bracketPairs -.

Else do not change bracketPairs.

In the end, if all the tokens are known and bracketPairs == 0, then the input expression is valid.

The task is a little more difficult if you need to assemble an AST.

Answer 5

what you want is "balanced groups", with them you can get all the definitions of bracelets, then you just need a simple line parsing

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

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

Answer 6

If you think that a logical expression generated by a formal grammar is written by a parser .

I created an open source library for interpreting simple Boolean expressions. You can take a look at it on GitHub , in particular, look at the AstParser and Lexer class.