Validating recursive string structure

Question

I want to validate a string which represents the serialized form of an expression tree. Here are some examples that I want to validate:

• Ex 1: (6+2)
• Ex 2: (6*(4+2))
• Ex 3: (9*(4-(7*3)))
• Ex 4: ((5+2)/(9+2))
• Ex 5: (((2-1)+2)/(9+()7*2))

As you can see from Ex 1, the simple case is where I have two numbers with an operation surrounded by parenthesis. However, either number could also be an expression. These expressions can be as deep as required.

I am working in .NET and wanted to write a regular expression to validate that the format of the string complies with what I showed in the examples. I cannot figure out how to write the .NET regular expression to perform this validation.

The simple case can be validated with the following:

string testCase = "(6+2)";
string baseExpression = "([(][0-9][+-/*][0-9][)])";
Regex rgx = new Regex(baseExpression );
bool returnValue = rgx.IsMatch(testCase);

However, I don't know how to introduce the recursion that a number can be replaced by another baseExpression;

The examples show integers for the numbers. Ultimately I want to be able to represent these numeric values as floats with (or without) a decimal point.

Anyone have any ideas?

Answer 1

In general, regular expression is not powerful enough to validate parentheses in an expression. However, .NET supports balancing groups, which can be used to validate your expressions as follows:

^[^()]*(?>(?>(?'open'\()[^()]*)+(?>(?'-open'\))[^()]*)+)+(?(open)(?!))$

'open' and '-open' are balancing groups. The working of this expression is explained in the article at the link.

Even though .NET lets you do this in a regex, it is not the best approach to solving this problem, because any regex-based solution becomes a fragile, "write-once-and-never-touch-again" solution. You would be much better off writing a simple recursive descent parser for the task, because the solution that you code in this way would be easy to read and a lot more maintainable.