"вертикальное" сопоставление регулярных выражений в "изображении" ASCII
Примечание: это вопрос о возможностях современных регулярных выражений. Это не лучший способ решить эту проблему, используя другие методы. Это вдохновлено более ранним вопросом, но тот не ограничен регулярным выражением.
Эта проблема
В ASCII "изображение"/art/map/string, например:
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
Я хотел бы найти простую вертикальную линию из трех X s:
X
X
X
Количество строк в изображении является переменным, и ширина каждой строки также является переменной.
Вопросы)
С помощью регулярных выражений (PCRE/PHP, Perl, .NET или аналогичных) можно:
- Определить, существует ли такая формация
- Подсчитайте количество таких образований / сопоставьте начальную точку их всех (4 в приведенном выше примере)
7 ответов
Ответ на вопрос 1
Чтобы ответить на первый вопрос, можно использовать:
(?xm) # ignore comments and whitespace, ^ matches beginning of line
^ # beginning of line
(?:
. # any character except \n
(?= # lookahead
.*+\n # go to next line
( \1?+ . ) # add a character to the 1st capturing group
.*+\n # next line
( \2?+ . ) # add a character to the 2nd capturing group
)
)*? # repeat as few times as needed
X .*+\n # X on the first line and advance to next line
\1?+ # if 1st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X .*+\n # X on the 2nd line and advance to next line
\2?+ # if 2st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X # X on the 3rd line
Это выражение работает в Perl, PCRE, Java и должно работать в.NET.
Выражение использует заголовки с самообращающимися группами захвата, чтобы добавить символ для каждого повторения заголовка (это используется для "подсчета").
\1?+ означает, что если \1 совпадения (или определены) потребляют это, и не возвращают это (не возвращают). В этом случае это эквивалентно (?(1) \1 ), Что означает совпадение \1 если \1 определено.
polygenelubricants объясняет этот вид упреждения с обратными ссылками очень хорошо в его ответе на Как мы можем сопоставить ^ nb ^ n с регулярным выражением Java?, (Он также написал о других впечатляющих трюках для регулярных выражений Java, включая обратные ссылки и обходные пути.)
Ответ на вопрос 2
Простое соответствие
Когда просто используется сопоставление и требуется ответ (количество) в количестве совпадений, тогда ответ на вопрос 2 будет следующим:
Это не может быть решено напрямую в регулярных выражениях, которые имеют ограниченный вид сзади. В то время как другие разновидности, такие как Java и.NET, могли бы (как, например, в .NET-решении m.buettner).
Таким образом, простые совпадения регулярных выражений в Perl и PCRE (PHP и т. Д.) Не могут напрямую ответить на этот вопрос в этом случае.
(Semi?) Доказательство
Предположим, что нет доступных видоискателей переменной длины.
Вы должны каким-то образом посчитать количество символов в строке перед X,
Единственный способ сделать это - сопоставить их, и поскольку нет доступных видоискателей переменной длины, нужно начинать совпадение (по крайней мере) с начала строки.
Если вы начнете матч в начале строки, вы можете получить не более одного матча в строке.
Поскольку в каждой строке может быть несколько вхождений, это не будет подсчитывать их все и не даст правильного ответа.
Длина / косвенное решение
С другой стороны, если мы примем ответ в качестве длины совпадения или результата замещения, тогда на второй вопрос можно будет ответить в PCRE и Perl (и других вариантах).
Это решение основано на "частичном решении PCRE" от m.buettner.
Можно просто заменить все совпадения следующего выражения на $3, получая ответ на вопрос два (количество шаблонов интересов) как длину полученной строки.
^
(?:
(?: # match .+? characters
.
(?= # counting the same number on the following two lines
.*+\n
( \1?+ . )
.*+\n
( \2?+ . )
)
)+?
(?<= X ) # till the above consumes an X
(?= # that matches the following conditions
.*+\n
\1?+
(?<= X )
.*+\n
\2?+
(?<= X )
)
(?= # count the number of matches
.*+\n
( \3?+ . ) # the number of matches = length of $3
)
)* # repeat as long as there are matches on this line
.*\n? # remove the rest of the line
Который на Perl может быть записан как:
$in =~ s/regex/$3/gmx;
$count = length $in;
Это выражение похоже на решение вопроса 1 выше, с некоторыми изменениями, чтобы включить X в символах, совпадающих с первым взглядом, завернутых в квантификатор и подсчитывающих количество совпадений квантификатора.
За исключением прямых совпадений, это настолько близко, насколько это возможно (дополнительный код, кроме регулярных выражений), и может быть приемлемым ответом на вопрос 2.
Контрольные примеры
Некоторые тестовые случаи и результаты для вышеуказанного решения. Результат, показывающий числовой ответ (длина результирующей строки) и в скобках результирующую строку после подстановки (ей).
Test #0:
--------------------
X
X
X
result: 1 (X)
Test #1:
--------------------
..X....
..X....
..X....
result: 1 (.)
Test #2:
--------------------
..X.X..
..X.X..
....X..
result: 1 (.)
Test #3:
--------------------
..X....
..X....
...X...
result: 0 ()
Test #4:
--------------------
..X....
...X...
..X....
result: 0 ()
Test #5:
--------------------
....X..
.X..X..
.X.....
result: 0 ()
Test #6:
--------------------
.X..X..
.X.X...
.X.X...
result: 1 (.)
Test #7:
--------------------
.X..X..
.X..X..
.X..X..
result: 2 (.X)
Test #8:
--------------------
XXX
XXX
XXX
result: 3 (XXX)
Test #9:
--------------------
X.X.X
XXXXX
XXXXX
.X.X.
result: 5 (XXXXX)
Test #10:
--------------------
1....X.......
2..X..X...X....
3X.X...X..X.....
4X....XXXXXX.....
5X..XXX...........
6.....X..........
7.........X....X
8..X......X....X....
9..X......X....X....X...
A....X.....
B.X..X..
C.....
XXX
XXX
XXX
.
result: 8 (3458.XXX)
редактировать
Следующие решения имеют две серьезные проблемы:
- Они не могут соответствовать нескольким
XXXпоследовательности, начинающиеся на той же строке, что иposслишком много продвигается. - Второе решение неверно: оно соответствует последовательным строкам, где два
Xдруг над другом. Там не обязательно должно быть три подряд.
Следовательно, все отклики (и награды) должны идти либо к Martin Ender .NET, либо к захватывающему ответу PCRE от самого Qtax.
Оригинальный ответ
Это ответ с использованием встраивания кода Perl в регулярные выражения. Поскольку регулярное выражение Perl может использовать код для утверждения произвольных условий внутри регулярных выражений или для создания частичных регулярных выражений, они не ограничиваются сопоставлением с обычными языками или языками без контекста, но могут соответствовать некоторым частям языков выше в иерархии Хомского.
Язык, которому вы хотите соответствовать, может быть описан в терминах регулярных выражений как
^ .{n} X .*\n
.{n} X .*\n
.{n} X
где n это число. Это примерно так же сложно, как сопоставить язык an bn cn, который является каноническим примером для контекстно-зависимого языка.
Мы можем легко сопоставить первую строку и использовать некоторый код на Perl для генерации регулярного выражения для других строк:
/^ (.*?) X
(?: .*\n (??{"." x length($1)}) X){2}
/mx
Это было коротко! Что оно делает?
^ (.*?) Xпривязки в начале строки, соответствует как можно большему количеству не-новых символов, а затемX, Мы помним линию доXкак группа захвата$1,Мы повторяем группу два раза, которая соответствует остальной части строки, символу новой строки, а затем вводим регулярное выражение, соответствующее строке той же длины, что и
$1, После этого должен бытьX,
Это регулярное выражение теперь будет соответствовать каждой строке, которая имеет три X друг на друга
Если мы хотим извлечь все такие последовательности, мы должны быть изящны. Поскольку последовательности могут перекрываться, например,
.X
XX
XX
X.
позиция, где начинается следующий матч, не должна проходить после первого X, Мы можем сделать это через взгляд назад и вперед. Perl поддерживает только постоянный вид сзади, но имеет \K побег, который обеспечивает аналогичную семантику. таким образом
/^ (.*?) \K X
(?=( (?: .*\n (??{"."x length($1)}) X ){2} ))
/gmx
будет соответствовать каждой последовательности из трех вертикальных Xэс. Время тестирования:
$ perl -E'my$_=join"",<>; say "===\n$1X$2" while /^(.*?)\KX(?=((?:.*\n(??{"."x length($1)})X){2}))/gmx' <<'END'
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXX
===
X.X...X..X.....
X....XXXXXX.....
X
===
X....XXXXXX.....
X..XXX...........
.....X
===
..............X
..X...........X....
..X...........X
Примечание: это опирается на экспериментальные функции регулярных выражений, которые доступны по крайней мере в Perl 5, начиная с версии 10. Код был протестирован с Perl v16.
Решение без встроенного кода
Давайте посмотрим на строки
...X...\n
...X..\n
Мы хотим утверждать, что ведущие ... часть каждой строки имеет одинаковую длину. Мы можем сделать это с помощью рекурсии с базовым вариантом X.*\n:
(X.*\n|.(?-1).)X
Если мы закрепим это в начале строки, мы можем сопоставить два вертикальных Xэс. Чтобы сопоставить более двух строк, мы должны выполнить рекурсию в предвкушении, а затем переместить позицию соответствия на следующую строку и повторить. Для этого мы просто сопоставим .*\n,
Это приводит к следующему регулярному выражению, которое может соответствовать строке с тремя вертикальными Xэс:
/ ^
(?:
(?=( X.*\n | .(?-1). ) X)
.*\n # go to next line
){2}
/mx
Но этого недостаточно, поскольку мы хотим сопоставить все такие последовательности. Чтобы сделать это, мы, по сути, ставим все регулярные выражения в поле зрения. Движок регулярных выражений обеспечивает продвижение позиции каждый раз для создания нового совпадения.
/ ^
(?=
(
(?:
(?= (X.*\n | .(?-1). ) X)
.*\n # go to next line
){2}
.* # include next line in $1
)
)
/mx
Время тестирования:
$ perl -E'my$_=join"",<>; say "===\n$1" while /^(?=((?:(?=(X.*\n|.(?-1).)X).*\n){2}.*))/gmx' <<'END'
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
===
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
===
X....XXXXXX.....
X..XXX...........
.....X..........
===
..............X
..X...........X....
..X...........X....X...
Так что это работает так же, как и решение со встроенным кодом, то есть оно сопоставляет каждую группу строк с вертикальной XДа, не каждая группа Xэс. (На самом деле, это решение кажется мне более хрупким, чем встроенный код)
Прежде всего: гениальный вопрос. Я думаю, что это может быть очень поучительно, чтобы попытаться использовать движки регулярных выражений до предела.
Основное решение.NET
Вы, ребята, сказали в комментариях, что было бы легко с.NET, но поскольку ответа пока нет, я подумал, что напишу один.
Вы можете решить как вопросы 1., так и 2., используя.NET с изменяемой длиной, взгляд и группы балансировки. Большая часть работы выполняется балансировочными группами, но просмотр с переменной длиной имеет решающее значение для возможности обнаружения нескольких совпадений, начиная с одной и той же строки.
Во всяком случае, вот шаблон:
(?<= # lookbehind counts position of X into stack
^(?:(?<a>).)* # push an empty capture on the 'a' stack for each character
# in front of X
) # end of lookbehind
X # match X
(?=.*\n # lookahead checks that there are two more Xs right below
(?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
# element onto 'b' and consume a character
(?(a)(?!)) # make sure that stack 'a' is empty
X.*\n # match X and the rest of the line
(?:(?<-b>).)* # while we can pop an element from stack 'b', and consume
# a character
(?(b)(?!)) # make sure that stack 'b' is empty
X # match a final X
) # end of lookahead
Этот шаблон должен использоваться с RegexOptions.Multiline для ^ чтобы соответствовать началу строк (и, очевидно, с RegexOptions.IgnorePatternWhitespace для свободного режима работы).
Вот несколько дополнительных комментариев:
Поместив все, кроме начального X, в обходные пути, у нас не будет проблем с перекрывающимися совпадениями или даже совпадениями, начинающимися на одной строке. Тем не менее, внешний вид должен быть переменной длины, что, безусловно, ограничивает любое решение такого рода.NET.
Все остальное зависит от баланса групп. Я не буду вдаваться в подробности здесь, потому что это дает довольно длинные ответы само по себе. (см. MSDN и этот пост в блоге для получения дополнительной информации)
Взгляд сзади просто совпадает ^.*так что все до начала строки, но для каждого . мы помещаем пустой захват в стек aПосчитав тем самым позицию нашего X как размер стека.
Затем, после прохождения остальной части строки, мы снова сопоставляем .*, но, прежде чем потреблять каждый .мы выталкиваем один элемент из стека a (что приводит к неудаче, один раз a пусто) и вставьте пустой захват на b (чтобы мы не забыли, сколько символов должно быть в третьей строке).
Чтобы убедиться, что мы действительно очищаем весь стек, мы используем (?(a)(?!)), Это условный шаблон, который пытается сопоставить (?!) если стек a не пусто (иначе просто пропускается). А также (?!) пустой отрицательный взгляд, который всегда терпит неудачу. Следовательно, это просто кодирует, "это a не пустой? потерпеть поражение. в противном случае продолжайте ".
Теперь, когда мы знаем, что в новой строке мы использовали абсолютно правильное количество символов, мы пытаемся найти X и остальная часть линии. Затем мы повторим тот же процесс снова со стеком b, Теперь нет необходимости вставлять какой-либо новый стек, потому что, если это сработает, мы закончили. Мы проверяем это b после этого пусто и соответствует третьему X,
Наконец, замечание по поводу оптимизации: этот шаблон все еще работает, если все повторы заключены в атомарные группы (таким образом эмулируя собственнические квантификаторы, которые не поддерживаются.NET)! Это сэкономило бы много возвратов. Более того, если мы поместим хотя бы квантификаторы с выталкивающими стеки в атомарные группы, мы сможем избавиться от обоих (?(...)(?!)) проверки (так как они нужны только для случаев, когда предыдущее повторение пришлось отменить).
Полное решение.NET
(Только самые смелые искатели приключений должны следовать за мной в действительно темную пещеру, в которую я собираюсь спуститься...)
Как обсуждалось в комментариях, это решение имеет один недостаток: оно учитывает перекрывающиеся совпадения. Например
..X..
..X..
..X..
..X..
Дает два матча, один в первой и второй во второй строке. Мы хотели бы избежать этого и сообщать только об одном совпадении (или двух, если есть от 6 до 8). Xс и три, если есть от 9 до 11 Xи так далее). Более того, мы хотим сообщить о матчах на 1, 4, 7, ... X,
Мы можем скорректировать приведенную выше схему, чтобы учесть это решение, потребовав X предшествует целое число, кратное 3 другим XЭто соответствует нашим требованиям. Основная идея проверки этого использует ту же манипуляцию со стеком, что и раньше (за исключением того, что мы перемещаем вещи между 3 стеками, чтобы после нахождения трех Xs мы в конечном итоге, где мы начали). Чтобы сделать это, нам нужно немного поиграть с оглядкой назад.
Хотя есть одна загвоздка. Пересматриваемый объект переменной длины.NET использует еще одну уникальную особенность.NET, RightToLeftMode, в котором образец читается (и сопоставляется) справа налево. Обычно это не должно беспокоить нас, но когда мы объединяем это с уравновешивающими группами, нас могут ожидать некоторые неприятные сюрпризы. В частности, при рассмотрении того, как эволюционируют наши стеки захвата, нам нужно также построить (и прочитать) выражение справа налево (или снизу вверх).
Поэтому, когда вы читаете следующее выражение (и мои аннотации), начинайте с конца самого крайнего вида сзади (вам придется немного прокрутить) - то есть непосредственно перед единственным верхним уровнем X; затем прочитайте полностью до самого верха. А затем продолжить после просмотра.
(?<=
# note that the lookbehind below does NOT affect the state of stack 'a'!
# in fact, negative lookarounds can never change any capturing state.
# this is because they have to fail for the engine to continue matching.
# and if they fail, the engine needs to backtrack out of them, in which
# case the previous capturing state will be restored.
(?<! # if we get here, there is another X on top of the last
# one in the loop, and the pattern fails
^ # make sure we reached the beginning of the line
(?(a)(?!)) # make sure that stack 'a' is empty
(?:(?<-a>).)* # while we can pop an element from stack 'a', and consume
# a character
X.*\n # consume the next line and a potential X
)
# at this point we know that there are less than 3 Xs in the same column
# above this position. but there might still be one or two more. these
# are the cases we now have to eliminate, and we use a nested negative
# lookbehind for this. the lookbehind simply checks the next row and
# asserts that there is no further X in the same column.
# this, together with the loop, below means that the X we are going to match
# is either the topmost in its column or preceded by an integer multiple of 3
# Xs - exactly what we are looking for.
(?:
# at this point we've advanced the lookbehind's "cursor" by exactly 3 Xs
# in the same column, AND we've restored the same amount of captures on
# stack 'a', so we're left in exactly the same state as before and can
# potentially match another 3 Xs upwards this way.
# the fact that stack 'a' is unaffected by a full iteration of this loop is
# also crucial for the later (lookahead) part to work regardless of the
# amount of Xs we've looked at here.
^ # make sure we reached the beginning of the line
(?(c)(?!)) # make sure that stack 'a' is empty
(?:(?<-c>)(?<a>).)* # while we can pop an element from stack 'c', push an
# element onto 'a' and consume a character
X.*\n # consume the next line and a potential X
(?(b)(?!)) # make sure that stack 'b' is empty
(?:(?<-b>)(?<c>).)* # while we can pop an element from stack 'b', push an
# element onto 'c' and consume a character
X.*\n # consume the next line and a potential X
(?(a)(?!)) # make sure that stack 'a' is empty
(?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
# element onto 'b' and consume a character
X.*\n # consume the next line and a potential X
)* # this non-capturing group will match exactly 3 leading
# Xs in the same column. we repeat this group 0 or more
# times to match an integer-multiple of 3 occurrences.
^ # make sure we reached the beginning of the line
(?:(?<a>).)* # push an empty capture on the 'a' stack for each
# character in front of X
) # end of lookbehind (or rather beginning)
# the rest is the same as before
X # match X
(?=.*\n # lookahead checks that there are two more Xs right below
(?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
# element onto 'b' and consume a character
(?(a)(?!)) # make sure that stack 'a' is empty
X.*\n # match X and the rest of the line
(?:(?<-b>).)* # while we can pop an element from stack 'b', and consume
# a character
(?(b)(?!)) # make sure that stack 'b' is empty
X # match a final X
) # end of lookahead
Рабочая демонстрация на RegexHero.net.
На этот раз я объяснил все объяснения прямо по шаблону. Поэтому, если вы читаете шаблон так, как я рекомендовал выше, вы получите правильное объяснение, когда вам это нужно...
Теперь это был один адский зверь. Но теперь он удовлетворяет всей спецификации и демонстрирует, насколько мощным является регулярное выражение.NET. И хотя это кажется довольно ужасным, я думаю (как только вы поймете, что справа налево), это гораздо легче понять, чем сопоставимое решение с PCRE (с использованием рекурсии или иным образом).
Как упомянул Коби в комментарии ниже, это может быть укорочено, если вы согласитесь с тем, что ваши результаты найдены в нескольких захватах одного совпадения (например, если у вас есть столбец 7 Xs вы получаете только один матч, но с двумя захватами в определенной группе). Вы можете сделать это, повторив основную (заглядывающую) часть 1 или более раз и записав начальную X (хотя все в перспективе). Тогда взгляду не нужно отсчитывать тройки Xс, но только нужно проверить, что нет ведущих X, Это, вероятно, сократило бы размер рисунка пополам.
Частичное решение PCRE
(Если бы только самые смелые искатели приключений следовали за мной до последнего решения, я, вероятно, остался бы с безумцами только в следующем путешествии...)
Чтобы доказать, что я только что сказал о том, как это решение сравнивается с PCRE, давайте посмотрим, как мы можем даже удаленно решить полную проблему в PCRE. Нам придётся работать немного усерднее, если не смотреть за плечами переменной длины и балансировать группы.
Qtax (OP) дал блестящее решение своего первого вопроса (проверяя, содержит ли строка какие-либо X-колонна) с использованием самоссылающихся групп для подсчета. Это очень элегантное и компактное решение. Но потому что каждый матч идет от начала строки до X который начинает столбец, и совпадения не могут перекрываться, мы не можем получить несколько совпадений на строку. Мы могли бы попытаться поместить все в заглядывание вперед (так, чтобы ничто фактически не соответствовало), но два совпадения нулевой ширины также никогда не начнутся в той же самой позиции - таким образом, мы все равно получим только одно совпадение на строку кандидата.
Однако действительно возможно решить по крайней мере первую часть вопроса 2 с помощью PCRE: подсчитать количество столбцов, начинающихся в каждой строке (и, следовательно, до общего количества X колонны). Поскольку мы не можем получить этот счет в виде отдельных совпадений (см. Предыдущий абзац), и мы не можем получить этот счет в виде отдельных групп или захватов (поскольку PCRE обеспечивает только фиксированное и конечное число захватов, в отличие от.NET). Вместо этого мы можем кодировать количество столбцов в совпадениях.
Вот как: для каждой строки мы проверяем, начинается ли столбец. Если это так, мы включаем одного персонажа в определенную группу захвата. Затем, прежде чем сообщить об успешном совпадении, мы пытаемся найти как можно больше дополнительных столбцов - для каждого из них добавляется символ в эту конкретную группу. Делая это, мы кодируем количество столбцов, начиная с каждой строки в длине этого конкретного захвата.
На самом деле реализация этой концепции в регулярном выражении намного сложнее, чем может показаться на первый взгляд (и это уже звучит довольно сложно). Во всяком случае, вот оно:
^
(?:(?|
(?(5)(?![\s\S]*+\5))
(?!(?!)()())
(?=
(?:
.
(?=
.*+\n
( \3? . )
.*+\n
( \4? . )
)
)*?
X .*+\n
\3
X .*+\n
\4
)
()
|
(?(5)(?=[\s\S]*+\5)|(?!))
(?:
.
(?=
.*+\n
( \1? .)
.*+\n
( \2? .)
)
)+?
(?=
(?<=X).*+\n
(\1)
(?<=X).*+\n
(\2)
(?<=X)
)
(?=
([\s\S])
[\s\S]*
([\s\S] (?(6)\6))
)
){2})+
(На самом деле, это немного проще - смотрите ответ Qtax о том, как упростить этот подход. В любом случае я оставлю этот подход здесь по академическим соображениям, так как из него можно извлечь некоторые очень продвинутые и интересные методы - см. Резюме на конец.)
Да, аннотаций нет. Я подумал, что в действительности никто их вообще не прочтет, поэтому вместо этого я попытаюсь разбить это выражение на части (я пойду на нисходящий подход).
Итак, давайте посмотрим на внешний слой лука из ада:
^
(?:(?|
checkForNextColumn
|
countAndAdvance
){2})+
Таким образом, наши матчи снова привязаны к началу линий. Тогда у нас есть (?:...{2})+ что означает четное количество повторений чего-либо. И это что-то чередование двух подшаблонов. Эти подшаблоны представляют шаги, которые я упомянул выше. Первый проверяет наличие другого столбца, начинающегося в текущей строке, второй регистрирует счетчик и подготавливает состояние механизма для другого применения первого подшаблона. Таким образом, управление дается второму шаблону - первый просто проверяет другой столбец, используя упреждающий просмотр, и, следовательно, является шаблоном нулевой ширины. Вот почему я не могу просто обернуть все в + но должен сделать {2})+ вещь - в противном случае компонент нулевой ширины будет пробоваться только один раз; это необходимая оптимизация, применяемая практически всеми двигателями, чтобы избежать бесконечных циклов с такими шаблонами, как (a*)+,
Есть еще одна (очень важная деталь): я использовал (?|...) для чередования. В этом виде группировки каждая альтернатива начинается с одного и того же номера группы. Отсюда в /(?|(a)|(b))/ и то и другое a а также b может быть захвачено в группу 1, Это критический прием, который позволяет "общаться" между подшаблонами, так как они могут изменять одни и те же группы.
Во всяком случае... так что у нас есть эти два подшаблона. Мы хотели бы убедиться, что контроль действительно чередуется между ними. Так что каждая группа терпит неудачу, если это была последняя, которая соответствовала. Мы делаем это, оборачивая шаблон в некоторую магию группировки и ссылки:
^(?:(?|
(?(5)(?![\s\S]*+\5)) # if group 5 has matched before make sure that
# it didn't match empty
checkForNextColumn # contains 4 capturing groups
() # this is group 5, match empty
|
(?(5)(?=[\s\S]*+\5)|(?!)) # make sure that group 5 is defined and that it
# matched empty
advanceEngineState # contains 4 capturing groups
(?=
([\s\S]) # this is group 5, match non-empty
[\s\S]* # advance to the end very end of the string
([\s\S] (?(6)\6)) # add a character from the end of the string to
# group 6
)
){2})+
Таким образом, в конце каждой альтернативы мы аннулируем условие для этой альтернативы, чтобы даже начать сопоставление. В конце второго варианта мы также включим персонажа в группу. 6, используя технику, изложенную Qtax. Это шаг подсчета. То есть группа 6 будет содержать столько символов, сколько столбцов начинается в текущей строке.
Сейчас checkForNextColumn будет действительно просто решением Qtax в перспективе. Требуется еще одна модификация, хотя и для обоснования этого мы рассмотрим advanceEngineState первый.
Давайте подумаем о том, как бы мы хотели изменить состояние, чтобы решение Qtax соответствовало второму столбцу подряд. Скажем, у нас есть вход
..X..X..
..X..X..
..X..X..
и мы хотим найти второй столбец. Этого можно достичь, начав матч с позиции сразу после первого X и имеющие группы \1 а также \2 уже инициализированы до первых трех символов (..X) строк 2 и 3 соответственно (вместо того, чтобы быть пустыми).
Теперь давайте попробуем сделать это: сопоставить все до и включая следующее X который начинает столбец, затем заполните две группы соответствующими строковыми префиксами для использования в checkForNextColumn шаблон. Это опять же модель Qtax, за исключением того, что мы считаем X в (вместо остановки прямо перед ним), и что нам нужно добавить захват в отдельную группу. Так вот advanceEngineState:
(?:
.
(?=
.*+\n
( \1? .)
.*+\n
( \2? .)
)
)+?
(?=
(?<=X) .*+\n
(\1)
(?<=X) .*+\n
(\2)
(?<=X)
)
Обратите внимание, как я перевернул Xо том, как перейти на один символ дальше, и как я эффективно копирую окончательное содержание \1 в \3 и те из \2 в \4,
Так что, если мы теперь используем решение Qtax как checkForNextColumn в перспективе, используя группы \3 а также \4 вместо \1 а также \2, мы должны быть сделаны.
Но только как мы делаем эти группы \3 а также \4 вместо \1 а также \2? Мы могли бы начать шаблон с ()(), который всегда совпадает, не затрагивая курсор движка, но увеличивает количество групп на 2. Однако это проблематично: это сбрасывает группы 1 а также 2 пустые строки, которые, если мы найдем второй столбец, advanceEngineState будет в несовместимом состоянии (так как глобальная позиция двигателя была продвинута, но счетные группы снова равны нулю). Таким образом, мы хотим включить эти две группы в схему, но не влияя на то, что они сейчас захватывают. Мы можем сделать это, используя то, что я уже упомянул, в решениях.NET: группы с отрицательным обзором не влияют на захваченное содержимое (потому что для продолжения движка необходимо вернуться назад). Следовательно, мы можем использовать (?!(?!)()()) (негативный взгляд, который никогда не приведет к сбою шаблона), чтобы включить в наш шаблон два набора скобок, которые никогда не используются. Это позволяет нам работать с группами 3 а также 4 в нашем первом подшаблоне, сохраняя при этом группы 1 а также 2 нетронутый для второй части шаблона следующей итерации. В заключение это checkForNextColumn:
(?!(?!)()())
(?=
(?:
.
(?=
.*+\n
( \3? . )
.*+\n
( \4? . )
)
)*?
X .*+\n
\3
X .*+\n
\4
)
Который, по большей части, на самом деле выглядит действительно знакомым.
Вот и все. Выполнение этого с некоторым вводом даст нам группу 6 который содержит один захват для каждой строки, в которой начинается столбец - и длина захвата скажет нам, сколько столбцов началось там.
Да, это действительно работает (живая демонстрация).
Обратите внимание, что это (как и базовое решение.NET) будет пересчитывать столбцы, которые больше 3 Xс долго. Я полагаю, что это количество можно исправить с помощью прогнозирования (аналогично тому, как это делается в полном решении.NET), но это оставлено читателю в качестве упражнения.
Немного прискорбно, что базовая проблема этого решения уже очень запутана и раздувает решение (75% строк в основном являются копиями решения Qtax). Потому что окружающий фреймворк имеет несколько действительно интересных техник и уроков
- Мы можем иметь несколько подчиненных шаблонов, которые выполняют конкретные задачи сопоставления / подсчета, и заставить их "общаться" через группы взаимного захвата, помещая их в
(?|...)чередование и зацикливание на них. - Мы можем принудительно выполнять альтернативы нулевой ширины, оборачивая их в конечный квантор
{2}прежде чем положить все в+, - Номера групп можно пропустить в одном подшаблоне (не затрагивая захваченное содержимое), поместив их в непрерывный негативный взгляд
(?!(?!)()), - Управление может передаваться взад-вперёд между подшаблонами, захватывая что-то или ничего в определенной группе, которая проверяется при входе в чередование.
Это допускает некоторые очень мощные вычисления (я видел утверждения, что PCRE на самом деле является полным по Тьюрингу) - хотя это, безусловно, неправильный подход для продуктивного использования. Но все же попытка понять (и придумать) такие решения может быть очень сложной и несколько полезной задачей при решении проблем.
Если вы хотите найти один "вертикальный" шаблон, вот решение. Если вы также хотите сопоставить "горизонтальный" шаблон, попробуйте сделать это с отдельным соответствием, возможно, проверяя перекрывающиеся позиции соответствия. Помните, что компьютер не знает, что такое линия. Это произвольная вещь, созданная людьми. Строка - это просто одномерная последовательность, где мы обозначаем какой-либо символ (ы) как конец строки.
#!/usr/local/perls/perl-5.18.0/bin/perl
use v5.10;
my $pattern = qr/XXX/p;
my $string =<<'HERE';
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
HERE
$transposed = transpose_string( $string );
open my $tfh, '<', \ $transposed;
while( <$tfh> ) {
while( /$pattern/g ) {
my $pos = pos() - length( ${^MATCH} );
push @found, { row => $pos, col => $. - 1 };
pos = $pos + 1; # for overlapping matches
}
}
# row and col are 0 based
print Dumper( \@found ); use Data::Dumper;
sub transpose_string {
my( $string ) = @_;
open my $sfh, '<', \ $string;
my @transposed;
while( <$sfh> ) {
state $row = 0;
chomp;
my @chars = split //;
while( my( $col, $char ) = each @chars ) {
$transposed[$col][$row] = $char;
}
$row++;
}
my @line_end_positions = ( 0 );
foreach my $col ( 0 .. $#transposed ) {
$transposed .= join '', @{ $transposed[$col] };
$transposed .= "\n";
}
close $sfh;
return $transposed;
}
Рабочее решение вопроса 2
Это вполне возможно в Perl/PCRE!:)
Извините, я немного опоздал на вечеринку, но я просто хотел бы отметить, что вы можете посчитать количество найденных XXX образований; то есть структурируйте выражение таким образом, чтобы при выполнении глобального совпадения было только одно совпадение на формирование. Это довольно сложно, хотя.
Вот:
\A(?:(?=(?(3)[\s\S]*(?=\3\z))(?|.(?=.*\n(\1?+.).*\n(\2?+.))|.*\n()())+?(?<=X)(?=.*\n\1(?<=X).*\n\2(?<=X))(?=([\s\S]*\z)))(?=[\s\S]*([\s\S](?(4)\4)))[\s\S])+[\s\S]*(?=\4\z)|\G(?!\A|[\s\S]?\z)
Я, вероятно, должен добавить некоторые комментарии к этому! Здесь для интересующихся:
\A(?:
(?=
(?(3)[\s\S]*(?=\3\z)) # Resume from where we ended last iteration
(?| # Branch-reset group used to reset \1
.(?=.*\n(\1?+.).*\n(\2?+.)) # and \2 to empty values when a new line
| # is reached. ".*\n" is used to skip the
.*\n()() # rest of a line that is longer than the
)+? # ones below it.
(?<=X)(?=.*\n\1(?<=X).*\n\2(?<=X)) # Find a XXX formation
(?=([\s\S]*\z)) # Save the rest of the line in \3 for
) # when we resume looking next iteration
(?=[\s\S]*([\s\S](?(4)\4))) # For every formation found, consume another
# character at the end of the subject
[\s\S] # Consume a character so we can move on
)+
[\s\S]*(?=\4\z) # When all formations around found, consume
# up to just before \4 at the subject end.
|
\G(?!\A|[\s\S]?\z) # Now we just need to force the rest of the
# matches. The length of \4 is equal to the
# number of formations. So to avoid overmatching,
# we need to exclude a couple of cases.
Я боюсь; что происходит??
По сути, мы проходим весь предмет в одной повторяющейся группе без захвата, переходя от одного формирования XXX к другому. Для каждого найденного формирования прикрепите другого персонажа к прилавку в конце предмета (хранится в \4). Было несколько препятствий:
Если мы сопоставляем все сразу, как мы можем перейти от одной строки к другой? Решение: используйте группу сброса ветви для сброса \1 и \2 при обнаружении новой строки.
Что если у нас есть большая сетка ASCII с небольшим "\nX\nX\nX" в конце? Если мы потребляем предмет из одного образования в другое, мы начнем есть в нашем прилавке. Решение: потребляйте только один символ за один раз и оборачивайте логику поиска формирования в предвкушении.
Но тогда как мы узнаем, где продолжить поиск следующей итерации группы без захвата, если мы не потребляем от одной формации к другой? Решение: когда формация найдена, захватите символы от этой позиции до самого конца предмета - фиксированная точка, на которую всегда можно сослаться. Это тот же трюк, который я использовал для сопоставления вложенных скобок без рекурсии, что действительно иллюстрирует силу прямых ссылок.
Это было очень весело, и я хотел бы видеть больше постов, как это!
Мой подход к сопоставлению вертикальных шаблонов с использованием PHP.
Прежде всего, давайте повернем наш ввод на 90°:
// assuming $input contains your string
$input = explode("\n", $input);
$rotated = array();
foreach ($input as $line)
{
$l = strlen($line);
for ($i = 0; $i < $l; $i++)
{
if (isset($rotated[$i]))
$rotated[$i] .= $line[$i];
else
$rotated[$i] = $line[$i];
}
}
$rotated = implode("\n", $rotated);
Это приводит к
..XXX.....
..........
.XX....XX.
....X.....
X...X....X
.X.XXX....
..XX......
...X......
...X......
.XXX......
...X.....
.........
........
........
....XXX
.....
...
..
..
X
.
.
.
Теперь это может выглядеть странно, но на самом деле приближает нас, так как теперь мы можем просто preg_match_all() над ним:
if (preg_match_all('/\bXXX\b/', $rotated, $m))
var_dump($m[0]);
и вуаля:
array(4) {
[0] =>
string(3) "XXX"
[1] =>
string(3) "XXX"
[2] =>
string(3) "XXX"
[3] =>
string(3) "XXX"
}
Если вы также хотите совпасть с одним и тем же горизонтальным шаблоном, просто используйте то же выражение на не повернутом вводе.