Вы хотите токенизировать ваш ввод.Простейшим токенизатором, необходимым для разбора ваших сбалансированных выражений, может быть простое регулярное выражение, разделенное на ( и ), игнорирующее пробел:
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]
Вызов 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
Вам может быть интересно посмотреть на модуль tokenize , который реализует токенизатор для кода Python;исходный код использует серию регулярных выражений для разделения исходного кода Python на токены (где токен содержит не только текст токена, но также тип токена , начало и конецпозиции (столбец, кортеж строки) и полная строка, из которой он получен).