字符串表达式的递归括号解析器

Question

假设我有一个类似于下面的表达式（实际上这是一个 SQL 语句）：

"v1 and (v2 and (v3 or v4))"

我想解析它以处理字符串并保持括号的优先级。为此，我使用了以下递归函数

def parse_conditions(expr):
    def _helper(iter):
        items = []
        for item in iter:
            if item == '(':
                result, closeparen = _helper(iter)
                if not closeparen:
                    raise ValueError("Unbalanced parentheses")
                items.append(result)
            elif item == ')':
                return items, True
            else:
                items.append(item)
        return items, False
    return _helper(iter(expr))[0] 

给出以下输出：

print(parse_conditions("v1 and (v2 and (v3 or v4))"))

['v', '1', ' ', 'a', 'n', 'd', ' ', ['v', '2', ' ', 'a', 'n', 'd', ' ', ['v', '3', ' ', 'o', 'r', ' ', 'v', '4']]]

然而，预期的输出要么是

['v1 and', ['v2 and', ['v3 or v4']]]

或者

['v1', and', ['v2', and', ['v3', 'or', 'v4']]]

有什么想法如何实现这一目标？

Answer 1

您想要标记您的输入。解析平衡表达式所需的最简单的分词器可能是一个简单的正则表达式，在(和 上拆分)，忽略空格：

import re

_tokenizer = re.compile(r'\s*([()])\s*').split
def tokenize(s):
    return filter(None, _tokenizer(s))

并使用tokenize())而不是iter()：

def parse_conditions(expr):
    def _helper(tokens):
        items = []
        for item in tokens:
            if item == '(':
                result, closeparen = _helper(tokens)
                if not closeparen:
                    raise ValueError("Unbalanced parentheses")
                items.append(result)
            elif item == ')':
                return items, True
            else:
                items.append(item)
        return items, False
    return _helper(tokenize(expr))[0] 

该调用会过滤掉在输入以or开始或结束的点处生成的filter(None, ...)空字符串，或者如果两个或字符直接相邻的话。re.split()()()

演示：

>>> s = 'v1 and (v2 and (v3 or v4))'
>>> parse_conditions(s)
['v1 and', ['v2 and', ['v3 or v4']]]

要也拆分运算符，您可以向拆分表达式添加有效的运算符，或者仅添加空格作为分隔符。

按空格分割，我们不将空格包含在标记中：

_tokenizer = re.compile(r'(?:([()])|\s+)').split

产生：

>>> parse_conditions(s)
['v1', 'and', ['v2', 'and', ['v3', 'or', 'v4']]]

同时关注有效的运算符是：

_tokenizer = re.compile(r'\s*([()]|\b(?:or|and)\b)\s*').split

以及产生相同结果的示例输入。

请注意，您的代码有一个错误；它不会检测到不平衡的右括号：

>>> parse_conditions('foo) and bar')
['foo']

您需要验证第一个_helper()调用是否返回False返回元组中的第二个元素。代替return _helper(tokenize(expr))[0]，使用：

items, closing = _helper(tokenize(expr))
if closing:  # indicating there was a closing ) without opening (
    raise ValueError("Unbalanced parentheses")
return items

最后，我不会在这里使用递归，而是使用显式堆栈来替换构建递归的调用堆栈。您自己的堆栈仅受内存限制，其中递归堆栈仅限于固定大小（默认为 1000）：

def parse_conditions(expr):
    stack = []  # or a `collections.deque()` object, which is a little faster
    top = items = []
    for token in tokenize(expr):
        if token == '(':
            stack.append(items)
            items.append([])
            items = items[-1]
        elif token == ')':
            if not stack:
                raise ValueError("Unbalanced parentheses")
            items = stack.pop()  
        else:
            items.append(token)
    if stack:
        raise ValueError("Unbalanced parentheses")
    return top

您可能有兴趣查看tokenizemodule，它为 Python 代码实现了分词器；源代码使用一系列正则表达式将Python源代码拆分为标记（其中标记不仅包含标记文本，还包含标记类型、开始和结束位置（列、行元组）和整行它来自）。