在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*)?(\(?\w\s*\)?)*" + term + @"(\s*\))?";
   Match m = Regex.Match(mainString, pattern);
   if(m.success)
   {
      prunedList.Add(term);
   }
 }

但这种模式并不适用于所有情况... 有人可以建议一下如何做吗？

- user1801163

Answer 1

我写了一个简单的解析器，对于你提供的示例效果很好。

我不知道以这个模式结尾的字符串的预期行为是什么：~（一些单词（即，没有有效的闭合括号）。

我相信你可以进一步完善它...

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

- Austin Salonen

Answer 2

平衡括号的语言不是正则的，因此您无法使用正则表达式完成所需的操作。更好的方法是使用传统的字符串解析方法，使用一对计数器-一个用于开括号，另一个用于闭括号-或堆栈来创建类似于下推自动机的模型。

为了更好地了解概念，请查看维基百科上的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);
 }

当然，这只是一个虚构的例子，需要一些工作来进行更严格的解析，但它给了你基本的想法。我省略了一些东西，比如正确的函数名称（现在不想查找它们），如何获取嵌套括号中的文本，例如从字符串 "(outer (inner))" 中获取 "inner"（该函数将返回 "outer (inner)"），以及如何存储您得到的字符串。

- evanmcdonnal

Answer 3

仅出于学术目的，我也想呈现正则表达式解决方案，主要是因为您可能正在使用唯一能够解决此问题的正则表达式引擎。

在澄清了一些有关.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是唯一支持变长回顾后发机制的正则表达式引擎。如果我们能将这两个特性结合起来，我们就可以查看我们想要的字符串左侧并查看当前嵌套结构之外是否有~(。

但这里有一个问题（请参见上面的链接）。在.NET中，回顾后发机制是从右到左执行的，这意味着我们需要在遇到左括号时推送右括号，并在遇到右括号时弹出左括号，而不是相反。

因此，这里是一些关于那个致命正则表达式的解释（如果您像.NET一样从下往上阅读回溯部分，则更容易理解）：

(?<=              # 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

- Martin Ender

Answer 4

括号匹配是需要使用栈来进行检查的 上下文无关语言 或语法。正则表达式适用于正则语言，但它们没有记忆功能，因此不能用于这种目的。

要进行括号匹配检查，您需要扫描字符串并计算括号数量：

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

你知道，由于正则表达式无法计数，因此它们无法检查这样的模式。

- Sina Iravanian

Answer 5

使用正则表达式是不可能的。 你应该放弃使用它们，而是使用普通的字符串操作，比如IndexOf。

- Euphoric

---

虽然不太美观，但使用像.NET这样强大的正则表达式引擎肯定是可行的（也可能适用于PCRE）。 - Martin Ender

是的，我想我应该放弃使用正则表达式的想法...我有另一个想法是修剪和后面单词之间的空格，并根据空格分割句子，对于以开头的拆分单词，检查列表中的单词是否存在其中。 - user1801163