Регулярное выражение для проверки, находится ли строка в определенном шаблоне, который может содержать вложенные скобки в C#

Я пытался написать код, который будет проверять, содержит ли данная строка определенные строки с определенным шаблоном. Чтобы быть точным, например:

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

Но этот шаблон работает не во всех случаях... Кто-нибудь может подсказать мне, как это можно сделать?

Источник

5 ответов

Решение

Проверка парантеза - это не зависящий от контекста язык или грамматика, для проверки которой требуется стек. Регулярные выражения подходят для регулярных языков. У них нет памяти, поэтому они не могут быть использованы для таких целей.

Чтобы проверить это, вам нужно отсканировать строку и сосчитать скобки:

  • инициализировать 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;
}

Видите ли, поскольку регулярные выражения не способны считать, они не могут проверять такие шаблоны.

Источник

Просто по академическим соображениям я бы тоже хотел представить решение 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 имеет единственный механизм регулярных выражений, который поддерживает просмотр за разной длиной. Если мы можем использовать эти две функции вместе, мы можем посмотреть слева от одной из наших желаемых строк и посмотреть, есть ли ~( где-то за пределами текущей структуры вложенности.

Но здесь есть подвох (см. Ссылку выше). В.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
Источник

Язык сбалансированных скобок не является регулярным, и в результате вы не можете выполнить то, что вы хотите, используя RegEx. Лучшим подходом было бы использовать традиционный разбор строк с парой счетчиков - один для открытого парена и один для близкого парня - или стек для создания модели, аналогичной автомату Push Down.

Чтобы лучше понять концепцию, ознакомьтесь с КПК в Википедии. 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);
 }

Теперь, конечно, это надуманный пример, и ему потребуется некоторая работа для более серьезного разбора, но он дает вам основную идею о том, как это сделать. Я пропустил такие вещи, как; правильные имена функций (не хочется искать их прямо сейчас), как получить текст во вложенных скобках, например, получить "внутреннее" из строки "(external (inner))" "(эта функция вернет" external (inner "))") и как хранить вернувшиеся строки.

Источник

Я написал простой парсер, который хорошо работает для приведенного вами примера.

Я не знаю, каково ожидаемое поведение для строки, которая заканчивается в этом шаблоне: ~(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);
}
Источник

Это невозможно при использовании регулярных выражений. Вы должны отказаться от идеи их использования и использовать обычные строковые операции, такие как IndexOf,

Источник
Другие вопросы по тегам