Я пытаюсь сопоставить строку с математическим выражением, содержащую вложенные круглые скобки.
import re
p = re.compile('\(.+\)')
str = '(((1+0)+1)+1)'
print p.findall(s)
[ '(((1 + 0) + 1) + 1)']
Я хотел, чтобы он соответствовал всем прилагаемым выражениям, таким как (1 + 0), ((1 + 0) +1)...
Мне все равно, соответствует ли оно нежелательным, например ((1 + 0), я могу позаботиться об этом.
Почему это уже не так, и как я могу это сделать?
Регулярное выражение пытается сопоставить как можно больше текста, тем самым потребляя всю вашу строку. Он не ищет дополнительных совпадений регулярного выражения в частях этой строки. Вот почему вы получаете только один ответ.
Решение состоит в том, чтобы не использовать регулярные выражения. Если вы на самом деле пытаетесь разобрать математические выражения, используйте реальные решения синтаксического анализа. Если вы действительно хотите захватить фигуры в круглых скобках, просто зациклируйте символы, подсчитывая, когда вы видите (и), и увеличиваете декремент счетчика.
Как уже упоминалось, регулярные выражения не подходят для вложенных конструкций. Я приведу базовый пример, используя pyparsing:
import pyparsing # make sure you have this installed
thecontent = pyparsing.Word(pyparsing.alphanums) | '+' | '-'
parens = pyparsing.nestedExpr( '(', ')', content=thecontent)
Вот пример использования:
>>> parens.parseString("((a + b) + c)")
Вывод:
( # all of str
[
( # ((a + b) + c)
[
( # (a + b)
['a', '+', 'b'], {}
), # (a + b) [closed]
'+',
'c'
], {}
) # ((a + b) + c) [closed]
], {}
) # all of str [closed]
(с обновлением/отступом/комментариями вручную)
Изменить: Изменено, чтобы исключить ненужные Forward, в соответствии с предложениями Пола МакГира.
Чтобы получить вывод в формате вложенного списка:
res = parens.parseString("((12 + 2) + 3)")
res.asList()
Вывод:
[[['12', '+', '2'], '+', '3']]
Существует новый стандартный модуль двигателя, который готов заменить существующий в Python. Он вводит много новых функций, включая рекурсивные вызовы.
import regex
s = 'aaa(((1+0)+1)+1)bbb'
result = regex.search(r'''
(?<rec> #capturing group rec
\( #open parenthesis
(?: #non-capturing group
[^()]++ #anyting but parenthesis one or more times without backtracking
| #or
(?&rec) #recursive substitute of group rec
)*
\) #close parenthesis
)
''',s,flags=regex.VERBOSE)
print(result.captures('rec'))
Вывод:
['(1+0)', '((1+0)+1)', '(((1+0)+1)+1)']
Связанная ошибка в regex: http://code.google.com/p/mrab-regex-hg/issues/detail?id=78
Языки регексов недостаточно эффективны для сопоставления произвольно вложенных конструкций. Для этого вам нужен пусковой автомат (т.е. Синтаксический анализатор). Существует несколько таких инструментов, таких как PLY.
Python также предоставляет библиотеку парсеров для своего собственного синтаксиса, который может делать то, что вам нужно. Выход очень подробный, однако, и занимает некоторое время, чтобы обернуть голову. Если вас интересует этот угол, следующее обсуждение пытается объяснить вещи как можно проще.
>>> import parser, pprint
>>> pprint.pprint(parser.st2list(parser.expr('(((1+0)+1)+1)')))
[258,
[327,
[304,
[305,
[306,
[307,
[308,
[310,
[311,
[312,
[313,
[314,
[315,
[316,
[317,
[318,
[7, '('],
[320,
[304,
[305,
[306,
[307,
[308,
[310,
[311,
[312,
[313,
[314,
[315,
[316,
[317,
[318,
[7, '('],
[320,
[304,
[305,
[306,
[307,
[308,
[310,
[311,
[312,
[313,
[314,
[315,
[316,
[317,
[318,
[7,
'('],
[320,
[304,
[305,
[306,
[307,
[308,
[310,
[311,
[312,
[313,
[314,
[315,
[316,
[317,
[318,
[2,
'1']]]]],
[14,
'+'],
[315,
[316,
[317,
[318,
[2,
'0']]]]]]]]]]]]]]]],
[8,
')']]]]],
[14,
'+'],
[315,
[316,
[317,
[318,
[2,
'1']]]]]]]]]]]]]]]],
[8, ')']]]]],
[14, '+'],
[315,
[316,
[317,
[318, [2, '1']]]]]]]]]]]]]]]],
[8, ')']]]]]]]]]]]]]]]],
[4, ''],
[0, '']]
Вы можете облегчить боль этой короткой функцией:
def shallow(ast):
if not isinstance(ast, list): return ast
if len(ast) == 2: return shallow(ast[1])
return [ast[0]] + [shallow(a) for a in ast[1:]]
>>> pprint.pprint(shallow(parser.st2list(parser.expr('(((1+0)+1)+1)'))))
[258,
[318,
'(',
[314,
[318, '(', [314, [318, '(', [314, '1', '+', '0'], ')'], '+', '1'], ')'],
'+',
'1'],
')'],
'',
'']
Номера поступают из модулей Python symbol и token, которые вы можете использовать для построения таблицы поиска из чисел в имена:
map = dict(token.tok_name.items() + symbol.sym_name.items())
Вы даже можете свернуть это сопоставление в функцию shallow(), чтобы вы могли работать со строками вместо чисел:
def shallow(ast):
if not isinstance(ast, list): return ast
if len(ast) == 2: return shallow(ast[1])
return [map[ast[0]]] + [shallow(a) for a in ast[1:]]
>>> pprint.pprint(shallow(parser.st2list(parser.expr('(((1+0)+1)+1)'))))
['eval_input',
['atom',
'(',
['arith_expr',
['atom',
'(',
['arith_expr',
['atom', '(', ['arith_expr', '1', '+', '0'], ')'],
'+',
'1'],
')'],
'+',
'1'],
')'],
'',
'']
Стек - лучший инструмент для работы: -
import re
def matches(line, opendelim='(', closedelim=')'):
stack = []
for m in re.finditer(r'[{}{}]'.format(opendelim, closedelim), line):
pos = m.start()
if line[pos-1] == '\\':
# skip escape sequence
continue
c = line[pos]
if c == opendelim:
stack.append(pos+1)
elif c == closedelim:
if len(stack) > 0:
prevpos = stack.pop()
# print("matched", prevpos, pos, line[prevpos:pos])
yield (prevpos, pos, len(stack))
else:
# error
print("encountered extraneous closing quote at pos {}: '{}'".format(pos, line[pos:] ))
pass
if len(stack) > 0:
for pos in stack:
print("expecting closing quote to match open quote starting at: '{}'"
.format(line[pos-1:]))
В клиентском коде, поскольку функция записывается как функция генератора, просто используйте шаблон for loop для разворачивания совпадений: -
line = '(((1+0)+1)+1)'
for openpos, closepos, level in matches(line):
print(line[openpos:closepos], level)
Этот тестовый код выводит следующий на моем экране, заметил, что второй параметр в распечатке указывает глубину скобки.
1+0 2
(1+0)+1 1
((1+0)+1)+1 0
От связанного ответа:
Из утилиты LilyPond convert-ly (и написана/защищена авторским правом, поэтому я могу показать ее здесь):
def paren_matcher (n):
# poor man matched paren scanning, gives up
# after n+1 levels. Matches any string with balanced
# parens inside; add the outer parens yourself if needed.
# Nongreedy.
return r"[^()]*?(?:\("*n+r"[^()]*?"+r"\)[^()]*?)*?"*n
convert-ly имеет тенденцию использовать это как paren_matcher (25) в своих регулярных выражениях, что, вероятно, слишком велико для большинства приложений. Но затем он использует его для соответствия выражений схемы.
Да, он ломается после заданного предела, но способность просто подключать его к регулярным выражениям по-прежнему превосходит "правильные" альтернативы, поддерживающие неограниченную глубину в использовании.
Сбалансированные пары (например, круглые скобки) являются примером языка, который не может быть распознан регулярными выражениями.
Далее следует краткое объяснение математики, почему это так.
Регулярные выражения - это способ определения автоматов конечного состояния (сокращенный FSM). Такое устройство имеет конечное количество возможного состояния для хранения информации. То, как это состояние может быть использовано, конкретно не ограничено, но это означает, что существует абсолютное максимальное количество различных позиций, которые он может распознать.
Например, состояние может использоваться для подсчета, скажем, непревзойденных левых скобок. Но поскольку количество состояний для такого подсчета должно быть полностью ограничено, то данный FSM может рассчитывать до максимума n-1, где n - число состояний, в которых может находиться FSM. Если n - это, скажем, 10, то максимальное количество несогласованных левых скобок FSM может соответствовать 10, пока оно не сломается. Поскольку вполне возможно иметь еще одну левую скобку, нет возможности FSM, который может правильно распознать полный язык совпадающих круглых скобок.
И что? Предположим, вы просто выбираете действительно большой русский? Проблема в том, что в качестве способа описания FSM регулярные выражения в основном описывают все переходы из одного состояния в другое. Так как для любого N FSM потребуется 2 перехода состояний (один для сопоставления левой скобки и один для соответствия справа), само регулярное выражение должно расти, по крайней мере, с постоянным множителем, кратным n
Для сравнения, следующий лучший класс языков (контекстно-свободные грамматики) может решить эту проблему в совершенно компактном виде. Вот пример в BNF
expression ::= `(` expression `)` expression
| nothing
Вы должны написать собственный синтаксический анализатор для синтаксического анализа такого выражения (например, используя pyparsing). Регулярные выражения не являются подходящим инструментом для написания достойных парсеров.
Вы можете использовать регулярные выражения, но вам нужно выполнить рекурсию самостоятельно. Что-то вроде следующего делает трюк (если вам нужно только найти, как говорит ваш вопрос, все выражения, заключенные в круглые скобки):
import re
def scan(p, string):
found = p.findall(string)
for substring in found:
stripped = substring[1:-1]
found.extend(scan(p, stripped))
return found
p = re.compile('\(.+\)')
string = '(((1+0)+1)+1)'
all_found = scan(p, string)
print all_found
Этот код, однако, не соответствует "правильным" круглым скобкам. Если вам нужно это сделать, вам будет лучше со специализированным парсером.
Я считаю, что эта функция может удовлетворить вашу потребность, я быстро выбросил ее, поэтому не стесняйтесь немного ее очистить. Когда вы занимаетесь гнездами, легко думать об этом назад и работать оттуда =]
def fn(string,endparens=False):
exp = []
idx = -1
for char in string:
if char == "(":
idx += 1
exp.append("")
elif char == ")":
idx -= 1
if idx != -1:
exp[idx] = "(" + exp[idx+1] + ")"
else:
exp[idx] += char
if endparens:
exp = ["("+val+")" for val in exp]
return exp
Многие сообщения предполагают, что для вложенных фигурных скобок, REGEX НЕ МОЖЕТ ДЕЛАТЬ ЭТО. ПРОСТО СЧЕТ БРАК: Например, см. Регулярное выражение для обнаружения циклов С++ и для циклов с концевой двоеточием
Вот полный образец python для итерации по строке и подсчета скобок:
# decided for nested braces to not use regex but brace-counting
import re, string
texta = r'''
nonexistent.\note{Richard Dawkins, \textit{Unweaving the Rainbow: Science, Delusion
and the Appetite for Wonder} (Boston: Houghton Mifflin Co., 1998), pp. 302, 304,
306-309.} more text and more.
This is a statistical fact, not a
guess.\note{Zheng Wu, \textit{Cohabitation: An Alternative Form
of Family Living} (Ontario, Canada: Oxford University Press,
2000), p. 149; \hbox{Judith} Treas and Deirdre Giesen, ``Title
and another title,''
\textit{Journal of Marriage and the Family}, February 2000,
p.\,51}
more and more text.capitalize
'''
pos = 0
foundpos = 0
openBr = 0 # count open braces
while foundpos <> -1:
openBr = 0
foundpos = string.find(texta, r'\note',pos)
# print 'foundpos',foundpos
pos = foundpos + 5
# print texta[pos]
result = ""
while foundpos > -1 and openBr >= 0:
pos = pos + 1
if texta[pos] == "{":
openBr = openBr + 1
if texta[pos] == "}":
openBr = openBr - 1
result = result + texta[pos]
result = result[:-1] # drop the last } found.
result = string.replace(result,'\n', ' ') # replace new line with space
print result