正则表达式，单场比赛 - 递归与子程序调用

Question

一个常见的现实世界用途是匹配一组平衡的括号。

\((?>[^()]|(?R))*\) 匹配一对括号和其间的任何文本，包括无限数量的括号，只要它们都正确配对。 (...)

如果您想要一个在包含不平衡括号的字符串中找不到任何匹配项的正则表达式，那么您需要使用子例程调用而不是递归。（这是我不明白的->）。如果要查找多对平衡括号的序列作为单个匹配项，那么您还需要一个子程序调用。

因此使用“(?R)”不会产生 "single match"。它与 "single match" 不同，类似于一场比赛中的多场比赛吗？

来源： https://www.regular-expressions.info/recurse.html

"Matching balanced constructs"部分.

Answer 1

If you want to find a sequence of multiple pairs of balanced parentheses as a single match, then you also need a subroutine call.

我相信这是在说什么，如果你想匹配这个 (.)(.) - 多对平衡括号的序列 - 那么你需要使用子例程。我承认，一个示例会对本教程有所帮助。

为什么递归会失败return"as a single match"？这仅仅是因为递归的工作方式——它将相同的正则表达式应用于一个不断递减的字符串（如果它不是无限递归的话）并且当它到达一个不匹配的元素时 returning 一个结果，然后沿着细绳。它不匹配 (.)(.) 作为单个字符串，因为它没有被定义为这样做（您可以使用量词来做到这一点：(?>\((?>[^()]|(?R))*\)){2} 或更一般地：(?>\((?>[^()]|(?R))*\))*）。

以下是本教程中为 a sequence of multiple pairs of balanced parentheses（第 1 行）和 for balanced constructs or nested constructs（第 2 行）生成的模式：

Answer 2

我知道这个关于正则表达式和递归的问题。但是，如果您的原始任务是在括号之间找到 matches/not 匹配项 ，那么对于这个简单的任务不使用正则表达式会怎么样。可能写一个coupe of lines来解决这个问题更容易：

public static Map<Integer, Integer> findAllPairs(String str) {
    Map<Integer, Integer> map = new TreeMap<>();
    Deque<Integer> stack = new LinkedList<>();
    char[] symbols = str.toCharArray();

    for (int i = 0; i < symbols.length; i++) {
        if (symbols[i] == '(')
            stack.push(i);
        else if (symbols[i] == ')') {
            if (stack.isEmpty())
                throw new IllegalArgumentException("Not pair ')' at position " + i);
            map.put(stack.pop(), i);
        }
    }

    if (!stack.isEmpty())
        throw new IllegalArgumentException("Total " + stack.size() + " not pair '('");

    return map;
}

正则表达式，单场比赛 - 递归与子程序调用

Regex, single match - Recursion vs. Subroutine Call

regex

recursion

subroutine