4

输入是表示元素列表的字符串。

列表被定义为一个开放的卷曲{，后跟 0 个或多个由空格分隔的元素，然后是一个闭合的花括号}。

元素可以是文字或元素列表。

文字是一系列非空白字符。如果元素包含花括号，则必须使用反斜杠 :\{和\}. （或者，为简单起见，您可以假设文字中不允许使用花括号）

例子：

"{abc { def ghi } 7 { 1 {2} {3 4} } {5 6} x\{yz \}foo }"

文字内没有花括号：

"{abc { def ghi } 7 { 1 {2} {3 4} } {5 6} xyz foo }"

（这是 Tcl 列表的简化定义。）

我想知道的是：可以使用正则表达式将输入拆分为最外层循环的元素吗？

预期输出：

abc
{ def ghi }
7
{ 1 {2} {3 4} }
{5 6}
x{yz
}foo

真正的问题是：这可以用正则表达式完成吗？

我对 .NET 风格最感兴趣，但会接受任何答案。

我将在答案中发布我自己的假设，看看它是否被验证或销毁。

4

4 回答 4

4

不幸的是，对于一些正则表达式，例如 PCRE 和 .NET，答案是肯定的，因为它们分别支持递归模式和类似堆栈的操作。

文法可以写成

ELEMENT  -> (?!\{)\S+ | LIST
LIST     -> '\{\s*' ELEMENT? ('\s+' ELEMENT)* '\s*\}'

因此在 PCRE 中，这可以转换为模式：

   \{\s*(?0)?(?:\s+(?0))*\s*\}|(?!\{)(?:[^\s}]|\}(?![\s}]))+

#  ---------------------------                   ^^^^^^^^^
#            LIST                    Make sure the } is not closing the group

例如，请参阅http://www.ideone.com/SnGsU{ （为了简单起见，我已经剥离了顶层}）。

（当然，不要在工作中尝试这个:)）

（顺便说一句，我不知道如何将此 PCRE 转换为 .NET 风格。如果有人知道，请尝试将 PCRE 递归正则表达式模式转换为 .NET 平衡组定义）

于 2010-08-29T10:45:25.930 回答
3

好吧，编辑从标记中删除了花括号并从问题中消除了刺痛，现在使用.Net Regexes，使用平衡组很容易做到这一点。它只是匹配大括号，这是一个基本示例。
就像 KennyTM 的回答一样，这仅在您删除顶级大括号时才有效，否则它将匹配整个输入。
同样，这更适合用于娱乐目的：

(?:                    # try matching...
    (?:\\[{}]|[^\s{}])+\s*? # a literal (allow escaped curly braces)
    |                       # OR
    (?<Curly>{)\s*          # "{" and push to stack
    |                       # OR
    (?<-Curly>})\s*?        # "}", pop from stack and fail if the stack is empty
)+?                    # ...a few times, and stop whenever you can.
(?(Curly)(?!))         # Make sure there aren't any extra open curly braces

有关更多详细信息，请参阅本文：深度正则表达式平衡组

于 2010-08-30T05:05:00.750 回答
2

对此的传统答案是响亮的“不”。正如我们在编译器类中所了解的，常规语法不能用于描述具有递归定义的语言（即，您不能使用有限状态机）

这里需要的是一个上下文无关的解析器，它的实现归结为一个有限状态机+一个堆栈。
见ANTLR，野牛等。

于 2010-08-29T10:14:38.467 回答
1

@Cristi 关于正则表达式是正确的：理论上，使用无堆栈的有限状态自动机解决递归表达式是不可能的。但是，解决方案更简单：您只需要保留一个开括号数的计数器，并确保它不会低于 0。它比维护堆栈更节省内存，您只需要计数- 不是括号的内容。

算法：

counter = 0                        // Number of open parens
For char c in string:              
    print c                        
    if c=='{':                     // Keep track on number of open parens
        counter++
    if c=='}':
        counter--
    if counter==1:                 // New line if we're back to the top level
        print "\n"
    elif counter<1:                // Error if the nesting is malformed
        print "ERROR: parentheses mismatch"
        break
于 2010-08-29T10:27:01.287 回答