2

可能的重复：
用 Python 中的正则表达式匹配嵌套结构

我无法解决这个问题。我有一个类似于以下的字符串：

Lorem ipsum dolor sit amet [@a xxx yyy [@b xxx yyy [@c xxx yyy]]] lorem ipsum sit amet

我的任务是提取命令（它们总是以[@开头并以]结尾）及其子命令。结果像

[
    [@a xxx yyy [@b xxx yyy [@c xxx yyy]]], # the most outer
    [@b xxx yyy [@c xxx yyy]],              # the middle one
    [@c xxx yyy]                            # the inner most
]

将不胜感激。问题是这类命令可能出现在很长的文本消息中，因此“高性能”解决方案会很好。

我大部分时间都在玩弄一些正则表达式模式，比如

(\[@.*?\]\s) # for the outer one

但我没有看到匹配中间和内部的光线。为了使它更复杂，嵌套命令的数量是可变的......可能一些特殊的正则表达式是解决方案吗？我已经阅读了前瞻和后瞻，但不知道如何在这种特殊情况下使用它们。

谢谢一堆！

更新

@Cyborgx37 将我指向另一个使用 pyparsing 包的帖子。有一个没有外部包或库的解决方案会很好。但是 pyparsing 绝对可以解决这个问题！

4

3 回答 3

2

C# 有递归/嵌套的 RegEx，我不相信 Python 有。您可以对以前的结果重新运行 RegEx 搜索，但这可能比仅制作自定义解析器效率低（RegEx 对这种简单搜索的开销）。您搜索“[@”和“]”的文本不是很复杂。

这是一个可以完成这项工作的自定义解析器（在 JavaScript 中）。

var txt = "Lorem ipsum dolor sit amet [@a xxx yyy [@b xxx yyy [@c xxx yyy]]] lorem ipsum sit amet";
function parse(s) {
    var stack = [];
    var result = [];
    for(var x=0; x<s.length; x++) {
        var c = s.charAt(x);
        if(c == '[' && x+1 < s.length-1 && s.charAt(x+1) == '@') {
            for(var y=0; y<stack.length; y++)
                stack[y] += "[@";
            stack.push("[@");
            x++;
        } else if(c == ']' && stack.length > 0) {
            for(var y=0; y<stack.length; y++)
                stack[y] += "]";
            result.push(stack.pop());
        } else {
            for(var y=0; y<stack.length; y++)
                stack[y] += c;
        }
    }
    return result;
}
parse(txt);

它快速遍历文本的所有字符（仅一次）并使用堆栈和 if...if else...else 条件分别推送、弹出和修改该堆栈中的值。

于 2013-02-05T16:45:15.823 回答
0

所以来自 ac# 背景，我不确定这会有所帮助，但是，我想既然你必须解析内部命令，为什么不直接存储命令的内容，然后再次运行你的正则表达式函数内部数据？我知道我可能遗漏了一些东西，但这就是我至少会尝试的原因。

于 2013-02-05T16:25:49.160 回答
0

难怪你无法解决这个问题。有一种关于形式语言的形式语言理论。Noam Chomsky 描述了四种语言类别——称为Chomsky 层次结构。正则表达式确实能够描述语言的简单类别——正则语言。但是，具有嵌套配对结构的语言不属于正则语言，它们不能被正则表达式描述/接受。

最容易实现的一种解析器是基于对解析语言元素的函数的递归调用的解析器。

于 2013-02-05T17:03:34.317 回答