Checking a recursive string structure
I want to validate a string representing a serialized form of an expression tree. Here are some examples that I want to test:
- Example 1:
(6+2)
- Example 2:
(6*(4+2))
- Example 3:
(9*(4-(7*3)))
- Example 4:
((5+2)/(9+2))
- Example 5:
(((2-1)+2)/(9+()7*2))
As you can see in Example 1, the simple case is where I have two numbers with an operation surrounded by parentheses. However, any number can also be an expression. These expressions can be as deep as necessary.
I am working in .NET and I want to write a regex to check that the format of the string matches what I showed in the examples. I can't figure out how to write a .NET regex to do this check.
A simple case can be verified as follows:
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 recursion, that the number can be replaced with another baseExpression;
The examples show integers for numbers. Ultimately I want to be able to represent these numeric values as floating with (or without) a decimal point.
Does anyone have any idea?
source to share
In general, a regular expression is not powerful enough to check for parentheses in an expression. However, .NET does support balancing groups that can be used to test your expressions as follows:
^[^()]*(?>(?>(?'open'\()[^()]*)+(?>(?'-open'\))[^()]*)+)+(?(open)(?!))$
'open'
and '-open'
- balancing groups. How this expression works is explained in the article at the link.
Even though .NET allows you to do this in a regex, this is not the best approach to solving this problem, as any regex solution becomes a fragile "write-once-and-never-touch-again" solution, you had it would be much better to write a simple recursive descent parser for the problem, because the solution you code that way would be easy to read and much more maintainable.
source to share
Regex is not a good tool for analyzing problems. For that specific, you can use a DataTable to evaluate your formula:
static bool evaluateFormula(String formula)
{
DataTable dt = new DataTable();
try
{
var v = dt.Compute(formula, "");//if you need the result return this
return true;
}
catch(SyntaxErrorException)
{
return false;
}
}
In your example, the last formula is not valid since 9 + () 7 * 2 doesn't really make sense:
static void Main(String[] args)
{
Console.WriteLine(evaluateFormula("(6+2)"));
Console.WriteLine(evaluateFormula("(6*(4+2))"));
Console.WriteLine(evaluateFormula("(9*(4-(7*3)))"));
Console.WriteLine(evaluateFormula("((5+2)/(9+2))"));
Console.WriteLine(evaluateFormula("(((2-1)+2)/(9+()7*2))"));
}
Outputs:
True
True
True
True
False
source to share
I think you should be using Stack Structure to group characters from string input. System.Collections.Stack
There is no need for recursion here. Just place your characters one at a time on your stack and control it however you wish.
ps: I made a verifyXML method in java that can help VerifyXML Java somehow
source to share