正则表达式，用于检查字符串是否在某个模式中，该模式可能包含c#中的嵌套圆括号

Question

我一直在尝试编写一段代码，检查给定字符串是否包含具有特定模式的特定字符串。准确地说，例如：

string mainString = @"~(Homo Sapiens means (human being)) or man or ~woman"
List<string> checkList = new List<string>{"homo sapiens","human","man","woman"};

现在，我想提取

"homo sapiens", "human" and "woman" but NOT "man"

从上面的列表中，因为它们遵循模式，即后面跟着~的字符串或括号内以~开头的字符串之一。到目前为止，我已经想出了：

string mainString = @"~(Homo Sapiens means (human being)) or man or ~woman"
List<string> checkList = new List<string>{"homo sapiens","human","man","woman"};
var prunedList = new List<string>();
foreach(var term in checkList)
{
var pattern = @"~(s)*((s*)?((?ws*)?)*" + term + @"(s*))?";
Match m = Regex.Match(mainString, pattern);
if(m.success)
{
prunedList.Add(term);
}
}

但这种模式并非适用于所有情况。。。有人能建议我怎么做吗？

Answer 1

我编写了一个简单的解析器，它可以很好地用于您给出的示例。

我不知道以这种模式结束的字符串的预期行为是什么：~(some words(即没有带有效开头的右括号)

我相信你可以清理一下。。。

private bool Contains(string source, string given)
{
return ExtractValidPhrases(source).Any(p => RegexMatch(p, given));
}
private bool RegexMatch(string phrase, string given)
{
return Regex.IsMatch(phrase, string.Format(@"b{0}b", given), RegexOptions.IgnoreCase);
}
private IEnumerable<string> ExtractValidPhrases(string source)
{
bool valid = false;
var parentheses = new Stack<char>();
var phrase = new StringBuilder();
for(int i = 0; i < source.Length; i++)
{
if (valid) phrase.Append(source[i]);
switch (source[i])
{
case '~':
valid = true;
break;
case ' ':
if (valid && parentheses.Count == 0)
{
yield return phrase.ToString();
phrase.Clear();
}
if (parentheses.Count == 0) valid = false;
break;
case '(':
if (valid)
{
parentheses.Push('(');
}
break;
case ')':
if (valid)
{
parentheses.Pop();
}
break;
}
}
//if (valid && !parentheses.Any()) yield return phrase.ToString();
if (valid) yield return phrase.ToString();
}

以下是我使用的测试：

// NUnit tests
[Test]
[TestCase("Homo Sapiens", true)]
[TestCase("human", true)]
[TestCase("woman", true)]
[TestCase("man", false)]
public void X(string given, bool shouldBeFound)
{
const string mainString = @"~(Homo Sapiens means (human being)) or man or ~woman";
Assert.AreEqual(shouldBeFound, Contains(mainString, given));
}
[Test]
public void Y()
{
const string mainString = @"~(Homo Sapiens means (human being)) or man or ~woman";
var checkList = new List<string> {"homo sapiens", "human", "man", "woman"};
var expected = new List<string> { "homo sapiens", "human", "woman" };
var filtered = checkList.Where(s => Contains(mainString, s));
CollectionAssert.AreEquivalent(expected, filtered);
}

Answer 2

平衡括号的语言不是正则的，因此您无法使用RegEx实现所需的功能。一种更好的方法是使用带有两个计数器的传统字符串解析(一个用于打开的paren，一个用于关闭的paren)，或者使用堆栈来创建类似于下推自动机的模型。

为了更好地了解这个概念，请查看维基百科上的PDA。http://en.wikipedia.org/wiki/Pushdown_automaton

下面是一个使用堆栈获取字符串(伪代码)的例子。

Stack stack = new Stack();
char[] stringToParse = originalString.toCharArray();
for (int i = 0; i < stringToParse.Length; i++)
{
if (stringToParse[i] == '(')
stack.push(i);
if (stringToParse[i] == ')')
string StringBetweenParens = originalString.GetSubstring(stack.pop(), i);
}

当然，这是一个人为的例子，需要做一些工作来进行更严肃的解析，但它为您提供了如何进行解析的基本概念；正确的函数名称(现在不想查找)，如何在嵌套的parens中获取文本，如从字符串"(outer(inner))"中获取"inner"(该函数将返回"outer(internal)")，以及如何存储返回的字符串。

Answer 3

出于学术原因，我也想介绍regex解决方案。大多数情况下，因为您可能正在使用唯一能够解决此问题的正则表达式引擎。

在解决了一些关于.NET独特功能组合的有趣问题之后，下面是可以获得所需结果的代码：

string mainString = @"~(Homo Sapiens means (human being)) or man or ~woman";
List<string> checkList = new List<string> { "homo sapiens", "human", "man", "woman" };
// build subpattern "(?:homo sapiens|human|man|woman)"
string searchAlternation = "(?:" + String.Join("|", checkList.ToArray()) + ")";
MatchCollection matches = Regex.Matches(
mainString,
@"(?<=~|(?(Depth)(?!))~[(](?>[^()]+|(?<-Depth>)?[(]|(?<Depth>[)]))*)"+searchAlternation,
RegexOptions.IgnoreCase
);

这是怎么回事？首先，.NET支持平衡组，这允许检测正确嵌套的模式。每次我们用一个命名的捕获组捕获东西时(与(?<Depth>somepattern)类似)它不会覆盖上一次捕获，而是被推送到堆栈上。我们可以使用(?<-Depth>)从该堆栈中弹出一个捕获。如果堆栈为空(就像在当前位置不匹配的东西一样)，这将失败。我们可以用(?(Depth)patternIfNotEmpty|patternIfEmpty)来检查堆栈是否为空。

除此之外，.NET还有唯一一个支持可变长度lookbehinds的正则表达式引擎。如果我们可以同时使用这两个特性，我们可以查看所需字符串之一的左侧，并查看当前嵌套结构之外是否存在~(。

但问题在于此(请参阅上面的链接)。在.NET中，Lookbehinds是从右到左执行的，这意味着我们需要推动关闭的parens，并在遇到打开的parens时弹出，而不是反过来。

因此，下面是对这个凶残的正则表达式的一些解释(如果你像.NET一样从下到上阅读lookbacking，会更容易理解)：

(?<=              # lookbehind
~               # if there is a literal ~ to the left of our string, we're good
|                 # OR
(?(Depth)(?!))  # if there is something left on the stack, we started outside
# of the parentheses that end end "~("
~[(]            # match a literal ~(
(?>             # subpattern to analyze parentheses. the > makes the group
# atomic, i.e. suppresses backtracking. Note: we can only do
# this, because the three alternatives are mutually exclusive
[^()]+        # consume any non-parens characters without caring about them
|               # OR
(?<-Depth>)?  # pop the top of stack IF possible. the last ? is necessary for
# like "human" where we start with a ( before there was a )
# which could be popped.
[(]           # match a literal (
|               # OR
(?<Depth>[)]) # match a literal ) and push it onto the stack
)*              # repeat for as long as possible
)                 # end of lookbehind
(?:homo sapiens|human|man|woman)
# match one of the words in the check list

Answer 4

Paranthesis检查是一种上下文无关的语言或语法，需要堆栈进行检查。正则表达式适用于正则语言。它们没有内存，因此不能用于此类目的。

要检查这一点，你需要扫描字符串并计算括号：

• 将count初始化为0
• 扫描字符串
  • 如果当前字符为(，则递增count
  • 如果当前字符是)，则递减count
  • 如果count为负数，则引发括号不一致的错误；例如)(
• 最后，如果count是正的，那么就有一些未闭合的括号
• 如果count为零，则测试通过

或者在C#中：

public static bool CheckParentheses(string input)
{
int count = 0;
foreach (var ch in input)
{
if (ch == '(') count++;
if (ch == ')') count--;
// if a parenthesis is closed without being opened return false
if(count < 0)
return false;
}
// in the end the test is passed only if count is zero
return count == 0;
}

你看，由于正则表达式不能计数，所以它们不能检查这样的模式。

Answer 5

这在使用正则表达式时是不可能的。您应该放弃使用它们的想法，使用像IndexOf这样的普通字符串操作。