regex 如何从逻辑表达式创建树结构?

t2a7ltrp  于 2023-05-30  发布在  其他
关注(0)|答案(2)|浏览(111)

我想解析如下的逻辑表达式:

(f = '1' OR f = '2') AND (s = '3' OR s = '4' OR s = '5') AND (t = '6')

我需要的是,这个逻辑表达式的表示,以表达式树的形式。最后,我希望能够以以下形式创建此数据结构的JSON表示:

{
    ...
    nodes: [
    {
        id: 1,
        operator: 'AND'
        operands: [
            2,
            3,
            4
        ]
    },
    {
        id: 2,
        operator: 'OR'
        operands: [
            5,
            6
        ]
    },
    {
        id: 3,
        operator: 'OR'
        operands: [
            7,
            8,
            9
        ]
    },
    leafs: [
    {
        id: 4,
        operator: '='
        operands: [
            t,
            6
        ]
    },
    ...
}

我知道这不是数据结构的最佳表示,但这只是一个示例。我如何使用像pyparse或re这样的包来解决这个问题呢?

mv1qrgav

mv1qrgav1#

如果你的布尔表达式总是A AND B AND C的形式。其中A B C等。总是X或Y或Z的形式,那么你可以通过黑客来做到这一点:挑出括号内的或短语,提取和术语,并将或短语粘在最高级别的和下面。你不需要更多的细节。
如果你的布尔表达式可以是任意的(例如,A AND NOT(B OR NOT C AND D)),那么你需要构建一个解析器,因为正则表达式不能跟踪嵌套的括号。请看我对如何轻松构建解析器的高度评价的SO回答:https://stackoverflow.com/a/2336769/120163。该方法很容易适应任何编程语言,包括Python。
这个答案有一个到另一个答案的链接,告诉您如何从解析操作构建解析树。我认为这就是你想要的内部代表。您可以使用递归访问器遍历解析树以生成所需的JSON文本。

r1wp621o

r1wp621o2#

我假设您的示例是非常基本的,并且真实的输入将包含嵌套。如果是这样,我强烈推荐使用pyparsing模块。它是构建自己的解析器和使用正则表达式之间的中间层次。就像伊拉巴克斯特提到的,正则表达式不是答案,因为它不能真正处理嵌套/递归。
它有一个很好的学习曲线,并且有一个叫做中缀符号的惊人特性,可以处理运算符优先级,运算符结合性,并且可以处理一元/二元/三元运算符。例如,它可以正确地对表达式进行分组,如a or b and c,在大多数语言(至少是我所知道的语言)中是a or (b and c)
一旦你构建了你想要的表示,你就可以使用set_parse_action,这基本上是一种在解析元素时转换解析元素的方法。使用它,你可以把它变成你想要的任何输出。
这里有一本关于如何使用pyparsing的好书:https://www.oreilly.com/library/view/getting-started-with/9780596514235/

相关问题