Проанализировать булеву арифметику включая круглые скобки с regex?
Существует ли единственное регулярное выражение, которое может проанализировать строку (в Python и/или JavaScript, не должно быть то же выражение), который представляет простую булеву арифметику? Например, я хочу проанализировать эту строку:
a and (b and c) and d or e and (f or g)
Предположение, что:
* круглые скобки не вкладывают
* условия a, b..., z не являются подвыражениями
Получающиеся получения должны быть сгруппированы круглыми скобками сначала, которые я затем анализирую снова с тем же или более простым regex.
Я имел успех, пишущий наивный regex для парсинга булевой арифметики без круглых скобок.
Какие-либо идеи?
3 ответа
Обычно вы бы использовали, например, рекурсивный анализатор спуска для этой задачи, но вы можете взять все детали (токены) с регелем:
x = 'a and (b and c) and d or e and (f or g)'
import re
matches = re.findall(r'\(.*?\)|\w+', x)
print ','.join(matches)
Операторы обычно имеют разные приоритет . Скобки будут оцениваться в скобки, затем и выражений, и, наконец, или выражения, с левосторонним порядком в случае равного приоритета. Вы говорите, что вы хотите вернуть скобки первыми, но на самом деле то, что вы обычно делаете, это использовать детали, создайте дерево выражения и оцените, что рекурсивно.
Страница примеров на Pyparding Wiki Включает в себя образец SimpleBool.py, который будет анализировать и оценивать такие выражения, как:
test = ["p and not q",
"not not p",
"not(p and q)",
"q or not p and r",
"q or not (p and r)",
"p or q or r",
"p or q or r and False",
]
(хммм, нет никаких примеров с вложенными преподавателями, но они тоже поддерживаются .)
Определяется в целом, используя этот код:
boolOperand = Word(alphas,max=1) | oneOf("True False")
boolExpr = operatorPrecedence( boolOperand,
[
("not", 1, opAssoc.RIGHT, BoolNot),
("and", 2, opAssoc.LEFT, BoolAnd),
("or", 2, opAssoc.LEFT, BoolOr),
])
Остальная часть примера дает реализации лолноты, булера и буланда. Конструкция ProductionPrecedence определяет последовательность операций, их артия и ассоциативности и, необязательно, класс, который будет построен с анализируемыми элементами. ЗатемPreatePrecedence тогда заботится о том, чтобы определить грамматику, включая рекурсивное определение Boolexpr внутри вложенных скобок. Полученную структуру аналогично вложенной AST, используя заданные классы Boolxxx. Эти классы в свою очередь определяют EVAL методы, чтобы выражения могли проанализировать и оценивать использование этого кода:
p = True
q = False
r = True
for t in test:
res = boolExpr.parseString(t)[0]
print t,'\n', res, '=', bool(res),'\n'
сам pyparding является несколько длинным модулем, но это один исходный файл, чтобы его установка был довольно маленьким Отказ Лицензия MIT позволяет как некоммерческое, так и коммерческое использование.
При условии, что вложенность не упрощает его на уровне, где можно использовать Regex. Regex для соответствия, которое было бы (при условии и / или только, может быть легко расширено):
>>> expr = 'a and (b and c) and d or e and (f or g)'
>>> regex = re.compile('\((\w+)\s+(and|or)\s+(\w)\)|(\w+)')
>>> results = regex.findall(expr)
>>> results = [i[:3] if i[0] else i[3] for i in results]
>>> results
['a', 'and', ('b', 'and', 'c'), 'and', 'd', 'or', 'e', 'and', ('f', 'or', 'g')]
Теперь у вас есть части скопик, как кортежи из 3 строк (операнд-оператор-операнда), а остальная часть строки в виде строк для каждого токен (оператор или операнд).
Вы можете пройти через список, оцените каждое выражение в скобках и замените его результатом. Как только это сделано, вы можете снова пройти через него и оценить либо слева направо или в соответствии с некоторыми правилами приоритета, которые вы устанавливаете (например, продолжайте оценку и только до тех пор, пока вы не запустите и не запускаете, а затем начать оценку или начать).