如何从逻辑表达式生成树形结构？用pyparsing/re实现方案咨询

问题描述 #

需要解析逻辑表达式：

(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"]
        },
        ...
    ]
}

一、使用pyparsing实现 #

pyparsing是专门的语法解析库，能完美处理嵌套表达式，步骤如下：

1. 安装pyparsing #

pip install pyparsing

2. 代码实现 #

import pyparsing as pp
import json

# 生成唯一ID的工具类
class IDGenerator:
    def __init__(self):
        self.current = 1
    def get(self):
        res = self.current
        self.current +=1
        return res

id_gen = IDGenerator()
nodes = []
leafs = []

# 定义语法元素
identifier = pp.Word(pp.alphas)
quoted_string = pp.QuotedString("'")
comparison = identifier + pp.Literal("=") + quoted_string
# 定义OR表达式：单个比较，或多个比较用OR连接
or_expr = pp.Group(comparison + pp.ZeroOrMore(pp.CaselessLiteral("OR") + comparison))
# 定义AND表达式：单个OR表达式（或比较），或多个用AND连接，支持括号包裹
and_expr = pp.Group(pp.Optional(pp.Literal("(")) + or_expr + pp.Optional(pp.Literal(")")) + 
                    pp.ZeroOrMore(pp.CaselessLiteral("AND") + pp.Optional(pp.Literal("(")) + or_expr + pp.Optional(pp.Literal(")"))))

# 解析动作：处理比较表达式（生成叶子节点）
def handle_comparison(tokens):
    leaf_id = id_gen.get()
    leafs.append({
        "id": leaf_id,
        "operator": "=",
        "operands": [tokens[0], tokens[2].strip("'")]
    })
    return leaf_id

# 解析动作：处理OR表达式（生成中间节点）
def handle_or(tokens):
    operand_ids = list(tokens[0])
    # 单个操作数直接返回ID，不生成冗余OR节点
    if len(operand_ids) == 1:
        return operand_ids[0]
    or_id = id_gen.get()
    nodes.append({
        "id": or_id,
        "operator": "OR",
        "operands": operand_ids
    })
    return or_id

# 解析动作：处理AND表达式（生成根节点）
def handle_and(tokens):
    operand_ids = list(tokens[0])
    and_id = id_gen.get()
    nodes.append({
        "id": and_id,
        "operator": "AND",
        "operands": operand_ids
    })
    return and_id

# 绑定解析动作
comparison.setParseAction(handle_comparison)
or_expr.setParseAction(handle_or)
and_expr.setParseAction(handle_and)

# 解析目标表达式
target_expr = "(f = '1' OR f = '2') AND (s = '3' OR s = '4' OR s = '5') AND (t = '6')"
and_expr.parseString(target_expr)

# 生成最终JSON结构
result = {
    "nodes": nodes,
    "leafs": leafs
}

# 打印格式化后的JSON
print(json.dumps(result, indent=2))

代码说明 #

• 从叶子到根逐层定义语法规则，支持括号嵌套和大小写不敏感的运算符
• 通过parseAction绑定处理函数，自动生成节点/叶子并分配唯一ID
• 最终输出完全符合要求的JSON结构，可直接复用或扩展支持更多运算符

二、使用re库实现（局限性提示） #

正则表达式处理嵌套结构（如多层括号）难度极大，仅适合简单场景，以下是针对示例表达式的基础实现：

代码示例 #

import re
import json

id_gen = iter(range(1, 100))
nodes = []
leafs = []

# 拆分AND连接的子表达式
target_expr = "(f = '1' OR f = '2') AND (s = '3' OR s = '4' OR s = '5') AND (t = '6')"
and_subparts = re.split(r'\s+AND\s+', target_expr)

# 处理单个OR子表达式
def process_or_subpart(part):
    # 去除首尾括号
    clean_part = re.sub(r'^\(|\)$', '', part.strip())
    or_items = re.split(r'\s+OR\s+', clean_part)
    # 单个比较表达式直接生成叶子
    if len(or_items) == 1:
        return process_comparison(or_items[0])
    # 生成OR节点
    or_id = next(id_gen)
    operand_ids = [process_comparison(item) for item in or_items]
    nodes.append({
        "id": or_id,
        "operator": "OR",
        "operands": operand_ids
    })
    return or_id

# 处理单个比较表达式（生成叶子节点）
def process_comparison(compare_str):
    match = re.match(r'(\w+)\s*=\s*\'(\w+)\'', compare_str.strip())
    if not match:
        raise ValueError(f"无效的比较表达式: {compare_str}")
    var, val = match.groups()
    leaf_id = next(id_gen)
    leafs.append({
        "id": leaf_id,
        "operator": "=",
        "operands": [var, val]
    })
    return leaf_id

# 生成AND根节点
and_root_id = next(id_gen)
operand_ids = [process_or_subpart(part) for part in and_subparts]
nodes.append({
    "id": and_root_id,
    "operator": "AND",
    "operands": operand_ids
})

# 生成最终JSON
result = {
    "nodes": nodes,
    "leafs": leafs
}
print(json.dumps(result, indent=2))

局限性说明 #

• 仅支持单层括号，无法处理((a='1' OR b='2') AND c='3') OR d='4'这类多层嵌套表达式
• 对表达式格式要求严格，必须用单引号、空格分隔运算符，容错性差
• 复杂场景下正则表达式会极度臃肿，维护成本高，优先推荐pyparsing方案

内容的提问来源于stack exchange，提问作者Ipsider