Клейкая лента Regex Decider

11

Ваша задача - создать программу, которая определяет, является ли данная строка допустимым регулярным выражением или не использует фрагменты кода, полученные из сайтов в сети StackExchange.

Для целей этой задачи, регулярное выражение говор будет урезанная и в основном минимальный набор мета-символов: ()*?|\. Таким образом, вы не сможете использовать встроенные парсеры регулярных выражений.

  • \используется для экранирования метасимволов. За ним должен следовать метасимвол.
  • Неэкранированные скобки должны быть сбалансированы
  • *и ?должен предшествовать либо не-метасимвол, либо группа в скобках, либо экранированный метасимвол.
  • Все другие печатаемые символы ASCII, а также символы новой строки, табуляции и пробела должны поддерживаться как неметачные символы. Что происходит со строкой, содержащей другие символы, не определено.
  • Фактическое значение регулярного выражения не имеет значения для этой задачи.

Примеры

Truthy:
  abc
  a?
  (a|)*
  ()
  a|b*
  \*
  \\
  \\*
  a*b?(cd|e)
  +
  [
  }
  (123\))*
  \|
  (a(b(c|d)*e)*f)*
  (|\)*)
  (abc)+*
  (abc)+
  +abc

^ last test case is an actual newline

Falsy:
  ?abc
  *
  **
  \
  (
  a*?
  a?*
  ?
  a)
  (\)
  (|\)*
  \()
  |*
  (?:abc)
  \\**
  \n

счет

Ваш общий балл - это количество фрагментов, взятых из вопросов и ответов вокруг StackExchange.

  • Повторные фрагменты учитываются столько раз, сколько они используются.
  • Пробелы могут быть добавлены и удалены свободно (из-за Python, Haskell и других языков, чувствительных к пробелам) и не учитываются при подсчете количества фрагментов.
    • Исключением будет, если ваш код действительно написан в Whitespace .
  • Фрагменты разрешены с любого сайта StackExchange, если они исходят из более старых вопросов, ответов и комментариев (в том числе по времени редактирования - при необходимости используйте более старые ревизии), чем это испытание. (24 сентября 2019 г., 15:30 по Гринвичу)
  • Фрагменты могут поступать из любого места в теле вопроса, ответа или комментария, независимо от того, находится ли он в предварительно отформатированном блоке кода или нет.
  • Соединение фрагмента в середине другого приводит к тому, что внешний фрагмент считается как два фрагмента.

Самый низкий балл побеждает!

Beefster
источник
1
@RobinRyder да, изменилось
Бифстер
Может ли пост быть старше или равным этому испытанию, т.е. можем ли мы использовать фрагменты из тела этого задания?
Джо Кинг,
1
«Таким образом, вы не сможете использовать встроенные парсеры регулярных выражений». Это значит, что он предназначен для того, чтобы помешать его использовать для простого да / нет, или что нам вообще запрещено использовать регулярные выражения в наших ответах?
user0721090601
@guifa это разработано так, что вы не можете просто взять движок регулярных выражений вашего языка и посмотреть, компилирует ли он заданное регулярное выражение. Каждый язык, который я знаю, поддерживает больший набор метасимволов и специализированных групп захвата, поэтому они не будут соответствовать этому набору символов во всех случаях.
Говядина
1
@ JL2210 Это сделало бы два фрагмента: один для начала и один для конца. Вы можете использовать один фрагмент, пока он проходит все тестовые случаи и приходит из ответа / вопроса / поста, который старше этой задачи
Beefster

Ответы:

6

Perl 6 , 20 фрагментов

{$_ eq m/[[<-[()*?|\\]>|\\<[()*?|\\]>|'(' <~~>* ')']<[*?]>?|\|]+/}

Попробуйте онлайн!

Фрагменты взяты из:

{$_ eq, m/[, <-[, ()*?, |\\, ]>, |\\, <[, ()*?, |\\, ]>, |, '(' <~~>* ')', <[, *?, ]>, ?|, \|, ]+/, }.

В основном это жадный подход (очевидный для всех фрагментов из одного или двух символов). Я использовал SymbolHound для поиска отдельных символов, и единственной реальной оптимизацией был '(' <~~>* ')'фрагмент, который взят из моего собственного ответа на рекурсивные регулярные выражения Perl 6.

Объяснение:

Это в основном проверяет, равен ли ввод жадному совпадению действительного регулярного выражения. Причина, по которой мы не можем просто использовать само регулярное выражение и добавить его ^$для обозначения концов, заключается в том, что мы используем рекурсивное регулярное выражение, которое не сработало бы, если бы были ^$маркеры. Само регулярное выражение:

m/[                             ]+/   # Match one or more times
   [              ]  # Any of 
    <-[()*?|\\]> |     # Not a metacharacter
    \\<[()*?|\\]>      # A metacharacter preceded by a \
    '(' <~~>* ')'      # Brackets surrounding a valid regex
                   <[*?]>?  # Optionally followed by a ? or *
                           | \|    # Or just the | metacharacter
Джо Кинг
источник
ТИЛ ~~, спасибо!
user0721090601
@guifa Да, я узнал об этом из спецификации P6 , в которой есть много вещей, которые еще не были должным образом документированы. Я подозреваю, ~~что не появляется, потому что это еще не полностью осуществлено (например <~~0>), хотя там есть другие скрытые драгоценные камни.
Джо Кинг,