Обратиться к регулярному выражению

27

Соревнование

Если задано правильное регулярное выражение, выведите регулярное выражение, которое соответствует тому же набору строк, но в обратном порядке.

Задание

Эта задача использует самые основные операции регулярных выражений: ^, $, ?, +, *, [], {}, |. Нет такой вещи как группы захвата или что-то из этого сложного материала. Специальные символы могут быть экранированы.

Пример ввода / вывода

Примечание: неверный ввод никогда не будет дан, и обычно есть несколько возможных ответов для данного ввода!

Input      | Sample Output
-----------|-------------
abc        | cba
tuv?       | v?ut
a(b|c)     | (c|b)a
1[23]      | [23]1
a([bc]|cd) | (dc|[bc])a
^a[^bc]d$  | ^d[^bc]a$
x[yz]{1,2} | [yz]{1,2}x
p{2}       | p{2}
q{7,}      | q{7,}
\[c[de]    | [de]c\[
ab[c       | <output undefined>
a(?bc)     | <output undefined>
a[]]bc     | <output undefined>

демонстрация

Рабочая демонстрация , демонстрирующая правильные входы / выходы. Это имеет некоторую дополнительную логику для проверки входных данных, которые не нужны в реальном ответе. Считайте неверные входные данные неопределенным поведением.

конкретика

Для простоты все специальные символы либо имеют свое особое значение, либо экранируются; это [[]не диапазон символов для [. Диапазоны длин взяты из стандартных PREIX ERE; то есть {n}, {n,}и {n,m}поддерживаются. Диапазоны символов []и [^]поддерживаются. Из-за этих правил, и поскольку недопустимые входные данные не заданы, вам действительно нужно только скопировать их содержимое непосредственно в выходные данные. Наконец, жадность не имеет значения, т. Е. Не имеет значения, если обратное регулярное выражение сначала находит другое совпадение, просто нужно найти совпадение для того же набора строк.

счет

Побеждает самая маленькая программа в байтах (за исключением мошенничества, например сетевых запросов). Программа может использовать реальный ввод-вывод или просто определить функцию.

TND
источник
1
Потому что нечего ?привязывать. Попробуйте набрать /a(?bc)/в консоли браузера.
TND
3
Хорошо выглядит сейчас. Вы можете добавить что-то вроде (^a|b)(c$|d)тестового примера.
Мартин Эндер
Можем ли мы предположить, что ввод будет содержать только печатные символы ASCII? В частности, нет символов перевода строки?
Мартин Эндер
1
Должны ли мы рассматривать квалификаторы, применяемые к группам, т. (a)?(b)+Е. (b)+(a)??
Kennytm
1
Ваш список операций с регулярными выражениями отсутствует (), что используется в вашем примере.
n15h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

Ответы:

7

Сетчатка , 136 114 110 байт

Эй, черт возьми, я слышал, что вы как регулярное выражение ...

^
;
(T`^$`$^`;.
(.*);(\[(\\.|[^]])*]|\\.|.)([*+?]|{\d+(,|,\d+)?})?
$2$4!$1;
^\(!
) 
^\)(.*)!(.+?) 
($2$1
;$|!
<empty>

Где <empty>представляет собой пустую висячую строку. Запустите код из одного файла с -sфлагом.

... когда вы хотите отменить регулярное выражение, вы должны использовать регулярное выражение. Когда вы хотите использовать регулярные выражения, вы должны использовать язык программирования на основе регулярных выражений.

Этот код предполагает , что вход не содержит ни , ;ни , !ни пространство. Хотя я согласен с тем, что это довольно сильное и потенциально неверное предположение, вы можете заменить эти три в коде на любые три непечатаемых символа (например, нулевые байты, символ колокольчика, <DEL>назовите его), и это не повлияет на размер или функциональность кода. вообще.

Я добавлю объяснение, когда я закончу играть в гольф.

Мартин Эндер
источник
3
«Я стадо * ты lik *»
lirtosiast
Я думаю, что код также предполагает, что регулярное выражение не содержит каких-либо необработанных символов новой строки.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ О, это правда, я предполагал, что на входе не будет непечатных символов. Я исправлю это, как только мы получим разъяснения от ФП. (Если могут появиться какие-либо символы, все еще есть определенные комбинации, которые не будут отображаться в том, что эта задача считает действительным регулярным выражением, например ]]], так или иначе, этот ответ не требует особых изменений.)
Мартин Эндер,
закончил игру в гольф через год? : P
Okx
2

JavaScript ES6, 574 байта

Я, вероятно, могу удалить несколько varзаявлений.

R=e=>{for(var s=0,c=[],h=/(\?|\+|\{\d*,*\d*\}|\*)(\?*)/,t=0;t<e.length;t++)switch(s){case 0:switch(e[t]){case"\\":t++,c.push("\\"+e[t]);break;case"[":j=t,s=1;break;case"(":k=t,s=2;break;default:var l=e.search(h,t);(l>=t+1||0>l)&&c.push(l==t+1?e[t]+e.slice(t,e.length).match(h)[0]:e[t])}break;case 1:"\\"==e[t]?t++:"]"==e[t]&&(c.push(e.slice(j,t+1)+(e.search(h,t)==t+1?e.slice(t,e.length).match(h)[0]:"")),s=0);break;case 2:"\\"==e[t]?t++:")"==e[t]&&(a=R(e.slice(k+1,t)),c.push("("+a+")"),s=0)}c.reverse(),r=c;var i=c.length-1;return"^"==c[i]&&(r[i]="$"),"$"==c[0]&&(r[0]="^"),r.join``}}

JS ES6, непроверенный, 559 байтов

Буду тестировать дома.

R=e=>{for(s=0,c=[],h=/(\?|\+|\{\d*,*\d*\}|\*)(\?*)/,t=0;t<e.length;t++)switch(s){case 0:switch(e[t]){case"\\":t++,c.push`\\${e[t]}`;break;case"[":j=t,s=1;break;case"(":k=t,s=2;break;default:l=e.search(h,t);(l>=t+1||0>l)&&c.push(l==t+1?e[t]+e.slice(t,e.length).match(h)[0]:e[t])}break;case 1:"\\"==e[t]?t++:"]"==e[t]&&(c.push(e.slice(j,t+1)+(e.search(h,t)==t+1?e.slice(t,e.length).match(h)[0]:"")),s=0);break;case 2:"\\"==e[t]?t++:")"==e[t]&&(a=R(e.slice(k+1,t)),c.push`(${a})`,s=0)}c.reverse(),r=c;i=c.length-1;return"^"==c[i]&&(r[i]="$"),"$"==c[0]&&(r[0]="^"),r.join``}}

JavaScript ES5, ungolfed, 961 байт

function revRegex(str){
 var mode = 0;
 var oS = [];
 var post = /(\?|\+|\{\d*,*\d*\}|\*)(\?*)/;
 for(var i=0;i<str.length;i++){
  switch(mode){
   case 0: switch(str[i]){
    case "\\": i++; oS.push("\\"+str[i]); break;
    case "[": j=i; mode = 1; break;
    case "(": k=i; mode = 2; break;
    default:
     var pLoc = str.search(post,i);
     if(pLoc>=i+1||pLoc<0){ // current is not pLoc
      if(pLoc==i+1){
       oS.push(str[i] + str.slice(i,str.length).match(post)[0]);
      } else {
       oS.push(str[i]);
      }
     }
   }; break;
   case 1: if(str[i]=="\\") i++; else if(str[i]=="]"){oS.push

(str.slice(j,i+1)+(str.search(post,i)==i+1?str.slice

(i,str.length).match(post)[0]:""));mode = 0}; break;
   case 2: if(str[i]=="\\") i++; else if(str[i]==")")

{a=revRegex(str.slice(k+1,i));oS.push("("+a+")");mode = 

0};break;
  }
 }
 oS.reverse();
 r=oS;
 var l=oS.length-1;
 if(oS[l]=="^") r[l]="$";
 if(oS[0]=="$") r[0]="^";
 return r.join("");
}
Конор О'Брайен
источник
5
LOL, вы использовали регулярное выражение для обратного регулярного выражения: D
Kritixi Lithos
3
@ ΚριτικσιΛίθος Да, я сделал: D Я бы использовал его для разбора HTML, если бы мог ...
Конор О'Брайен
4
«Если бы ты мог»
Оптимизатор
1
@ CᴏɴᴏʀO'Bʀɪᴇɴ Я проанализировал HTML-коды с помощью регулярных выражений, но получил серьезную проблему с Unicode-
символами
2
@ CᴏɴᴏʀO'Bʀɪᴇɴ Это альтернатива: `code.replace (/.*/," trollolol ");
Kritixi Lithos
2

JavaScript ES6, 343 байта

t=r=>(u="substr",T="(?:[+?*]|{\\d+(?:,\\d*)?})?)([^]*)",(c=r[0])=="(")?([n,s]=v(r[u](1)),[_,q,s]=s.match("^(\\)"+T),["("+n+q,s]):c==")"||c==null?["",r]:c=="^"?["^",r[u](1)]:c=="$"?["^",r[u](1)]:r.match("^("+/(?:\[(?:[^\]\\]|\\[^])*\]|[^[\\]|\\[^])/.source+T).slice(1);(v=r=>{var o="";do{[n,r]=t(r);o=n+o;}while(n&&r);return[o,r]})(prompt())[0]

Оригинальный код (функции, но без prompt):

function reverse(regex) {
    var out = "";
    do {
        // console.log("calling term");
        var [node, regex] = term(regex);
        // console.log("reverse: " + [node, regex]);
        out = node + out;
    } while (node && regex);
    return [out, regex];
}

function term(regex) {
    switch (regex[0]) {
        case "(":
            // console.log("calling reverse");
            var [node, sequel] = reverse(regex.substr(1));
            // console.log("term: " + regex + " / " + [node, sequel]);
            var [_, quantifier, sequel] = sequel.match(/^(\)(?:[+?*]|{\d+(?:,\d*)?})?)([^]*)/);
            return ["(" + node + quantifier, sequel];
        case ")":
        case void 0:
            return ["", regex];
        case "^":
            return ["$", regex.substr(1)];
        case "$":
            return ["^", regex.substr(1)];
        default:
            return regex.match(/^((?:\[(?:[^\]\\]|\\[^])*\]|[^[\\]|\\[^])(?:[+?*]|{\d+(?:,\d+)?})?)([^]*)/).slice(1);
    }
}

reverse("^\\(([The(){}*\\] ]{2,3}world\\\\(begin(ner|ning)?|ends*)+|Con\\|ti\\*n\\)ue...[^%\\[\\]()\\\\])$")[0]

Код реализован как рекурсивный синтаксический анализатор сверху вниз, поэтому он может вызвать переполнение стека при глубоко вложенном вводе.

Код может вызвать бесконечный цикл в недопустимых случаях, так как я не проверяю их, пользуясь предложением «неопределенное поведение».

n̴̖̋h̷͉a̷̭̿h̸̡̅ẗ̵̨d̷̰ĥ̷̳
источник
0

Python 3, 144 байта

(Этот не поддерживает квалификаторы в такой группе, как (a)+(b)*(cde)?.)

import re;f=lambda x:''.join({e:e,'^':'$','$':'^','(':')',')':'('}[e]for e in re.findall(r'(?:\\.|\[(?:\\?.)+?\]|.)(?:[?+*]|\{.+?\})?',x)[::-1])

Тестовые случаи:

test_cases = [
    # Provided test cases
    r'abc',
    r'tuv?',
    r'a(b|c)',
    r'1[23]',
    r'a([bc]|cd)',
    r'^a[^bc]d$',
    r'x[yz]{1,2}',
    r'p{2}',
    r'q{7,}',
    r'\[c[de]',

    # Pathological cases
    r'a{3}b',
    r'(a)?(b)+',            # <-- currently failing!
    r'[\[]{5}[^\]]{6}',
    r'[\[]\]{7}',
    r'[\[\]]{8,9}',
    r'\(\)\^\$',

    # Undefined cases
    r'ab[c',
    r'a(?bc)',
    r'a[]]bc',
]

for t in test_cases:
    print(t, '->', f(t))

Результат:

abc -> cba
tuv? -> v?ut
a(b|c) -> (c|b)a
1[23] -> [23]1
a([bc]|cd) -> (dc|[bc])a
^a[^bc]d$ -> ^d[^bc]a$
x[yz]{1,2} -> [yz]{1,2}x
p{2} -> p{2}
q{7,} -> q{7,}
\[c[de] -> [de]c\[
a{3}b -> ba{3}
(a)?(b)+ -> )+b))?a)                    # <-- note: wrong
[\[]{5}[^\]]{6} -> [^\]]{6}[\[]{5}
[\[]\]{7} -> \]{7}[\[]
[\[\]]{8,9} -> [\[\]]{8,9}
\(\)\^\$ -> \$\^\)\(
ab[c -> c[ba
a(?bc) -> (cb(?a
a[]]bc -> cb[]]a
kennytm
источник