c# - 验证递归字符串结构

Question

我想验证一个表示表达式树序列化形式的字符串。以下是我要验证的一些示例:

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

正如您从示例 1 中看到的那样，简单的情况是我有两个数字，其中一个运算用括号括起来。但是，任何一个数字也可以是一个表达式。这些表达式可以根据需要深入。

我在 .NET 中工作，想编写一个正则表达式来验证字符串的格式是否符合我在示例中显示的格式。我不知道如何编写 .NET 正则表达式来执行此验证。

可以使用以下方法验证简单情况:

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

但是，我不知道如何引入一个数字可以被另一个baseExpression替换的递归；

示例显示数字的整数。最终，我希望能够将这些数值表示为带(或不带)小数点的 float 。

有人有什么想法吗？

Answer 1

一般来说，正则表达式的功能不足以验证表达式中的括号。但是，.NET 支持 balancing groups ，可用于验证您的表达式，如下所示:

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

'open' 和 '-open' 是平衡组。该表达式的工作原理在链接中的文章中进行了解释。

尽管 .NET 允许您在正则表达式中执行此操作，但这并不是解决此问题的最佳方法，因为任何基于正则表达式的解决方案都会变得脆弱，“一次写入，再也不会接触”的解决方案.你最好写一个简单的 recursive descent parser对于这项任务，因为您以这种方式编写的解决方案将易于阅读并且更易于维护。