Python分词列表解析格式化报错排查：UnboundLocalError问题

问题描述 #

我有一个形如"(a OR b) AND c OR d AND c"或"(a OR b) AND c OR (d AND c)"的分词列表，需要将其重新格式化为{or {and {or a b} c} {and d c}}格式的字符串。我编写了如下Python代码，处理无括号的分词列表时可正常运行，但处理带括号的情况时会触发UnboundLocalError: local variable 'op' referenced before assignment错误，请问问题出在哪里？

原代码 #

def parse_expression(tokens):

    if len(tokens) == 1:
        return tokens[0]
    
    # 寻找顶层运算符（AND或OR）
    parens = 0
    for i in range(len(tokens) - 1, -1, -1):
        token = tokens[i]
        if token == ')':
            parens += 1
        elif token == '(':
            parens -= 1
        elif parens == 0 and token in {'AND', 'OR'}:
            op = token
            break
    else:
        print('Invalid expression')
    
    # 递归解析子表达式
    left_tokens = tokens[:i]
    right_tokens = tokens[i+1:]
    print(f"{i} left {left_tokens}")
    print(f"{i} right {right_tokens}")
    if op == 'AND':
        left = parse_expression(left_tokens)
        right = parse_expression(right_tokens)
        return f'(and {left} {right})'
    else:
        left = parse_expression(left_tokens)
        right = parse_expression(right_tokens)
        return f'(or {left} {right})'
        

x = ['x', 'AND', 'y', 'AND', 'z', 'AND', '(', '(', 'a', 'AND', 'b', ')', 'OR', '(', 'c', 'AND', 'd', ')', ')']
y = ['x', 'AND', 'y', 'AND', 'z', 'AND', '(', 'w', 'AND', 'q', ')']

错误信息 #

Traceback (most recent call last):
File "./prog.py", line 41, in
File "./prog.py", line 29, in parse_expression
File "./prog.py", line 27, in parse_expression
UnboundLocalError: local variable 'op' referenced before assignment

问题根源 #

1. 未定义变量访问：当解析被括号完全包裹的子表达式（比如['(', 'w', 'AND', 'q', ')']）时，循环遍历所有token后找不到处于括号层级为0的AND/OR，此时会执行else分支打印错误，但没有终止函数执行，后续代码依然尝试访问未赋值的op变量，触发UnboundLocalError。
2. 运算符优先级逻辑错误：循环从后往前找顶层运算符，但未区分优先级（OR优先级低于AND），会破坏原表达式的运算顺序。比如原表达式(a OR b) AND c OR d AND c，应该优先拆分顶层的OR，而非后面的AND。
3. 未处理外层括号：带括号的子表达式进入递归时，外层括号未被剥离，会导致重复处理无效的括号token。

修复方案 #

def parse_expression(tokens):
    # 自动剥离完全包裹的外层括号
    while len(tokens) >= 2 and tokens[0] == '(' and tokens[-1] == ')':
        parens = 0
        valid_wrap = True
        for i, token in enumerate(tokens):
            if token == '(':
                parens += 1
            elif token == ')':
                parens -= 1
            # 如果中途括号闭合，说明不是完全包裹
            if parens == 0 and i != len(tokens)-1:
                valid_wrap = False
                break
        if valid_wrap:
            tokens = tokens[1:-1]
        else:
            break

    if len(tokens) == 1:
        return tokens[0]
    
    op = None
    split_idx = -1
    # 优先找优先级更低的OR作为顶层运算符
    parens = 0
    for i in range(len(tokens)-1, -1, -1):
        token = tokens[i]
        if token == ')':
            parens += 1
        elif token == '(':
            parens -= 1
        elif parens == 0 and token == 'OR':
            op = token
            split_idx = i
            break
    # 找不到OR再找AND
    if op is None:
        parens = 0
        for i in range(len(tokens)-1, -1, -1):
            token = tokens[i]
            if token == ')':
                parens += 1
            elif token == '(':
                parens -= 1
            elif parens == 0 and token == 'AND':
                op = token
                split_idx = i
                break
    
    # 处理无效表达式
    if op is None:
        print('Invalid expression')
        return ''
    
    left_tokens = tokens[:split_idx]
    right_tokens = tokens[split_idx+1:]
    left = parse_expression(left_tokens)
    right = parse_expression(right_tokens)
    return f'(and {left} {right})' if op == 'AND' else f'(or {left} {right})'

# 测试
x = ['x', 'AND', 'y', 'AND', 'z', 'AND', '(', '(', 'a', 'AND', 'b', ')', 'OR', '(', 'c', 'AND', 'd', ')', ')']
y = ['x', 'AND', 'y', 'AND', 'z', 'AND', '(', 'w', 'AND', 'q', ')']
print(parse_expression(x))
print(parse_expression(y))

修复说明 #

• 新增外层括号自动剥离逻辑，避免递归时处理无效括号。
• 优先查找顶层OR运算符，保证运算顺序符合优先级规则。
• 明确处理找不到运算符的情况，终止函数执行并返回空字符串，避免未定义变量访问。

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