验证递归字符串结构

本文关键字：结构 字符串 递归 验证 | 更新日期: 2023-09-27 17:56:13

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

  • 例 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替换的递归;

这些示例显示了数字的整数。 最终，我希望能够将这些数值表示为带有（或不带）小数点的浮点数。

有人有什么想法吗？

验证递归字符串结构

通常，正则表达式的功能不足以验证表达式中的括号。但是，.NET 支持平衡组，可用于验证表达式，如下所示：

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

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

尽管 .NET 允许您在正则表达式中执行此操作，但它并不是解决此问题的最佳方法，因为任何基于正则表达式的解决方案都变成了脆弱的"一次写入，永不触摸"解决方案。您最好为该任务编写一个简单的递归下降解析器，因为以这种方式编写的解决方案将易于阅读且更易于维护。

正则表达式不是解析任务的好工具。对于此特定公式，您可以使用 DataTable 来计算公式： 

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;
    }            
}

在您的示例中，最后一个公式无效，因为 9+（）7*2 实际上没有意义：

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))"));
}

输出：

True
True
True
True
False

我认为您应该使用堆栈结构来堆叠字符串输入中的字符。System.Collections.Stack

这里不需要递归。只需将你的角色一次一个地放在你的堆栈中，然后按照你的意愿控制它。

ps：我在java中做了一个verifyXML方法，可能会以某种方式帮助VerifyXML Java

相关文章：