27
\$\begingroup\$

The Challenge

Given a valid regex, output a regex that that matches the same set of strings, but reversed.

The Task

This challenge uses the most basic regex operations: ^, $, ?, +, *, [], {}, |. There's no such thing as capture groups or any of that complicated stuff. Special characters can be escaped.

Sample Input/Output

Note: Invalid input will never be given, and there are generally multiple possible answers for a given input!

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>

Demo

Working demo that demonstrates correct inputs/outputs. This has some additional logic for validating inputs that isn't necessary in a real answer. Consider invalid inputs to be undefined behavior.

Specifics

For simplicity, all special characters either have their special meaning or are escaped; that is, [[] isn't a character range for [. Length ranges come from standard POSIX EREs; that is, {n}, {n,}, and {n,m} are supported. The character ranges [] and [^] are supported. Because of these rules, and since no invalid input is given, you really need only copy the contents of these directly to the output. Lastly, greediness doesn't matter, i.e. it doesn't matter if the reversed regex finds a different match first, it just needs to find a match for the same set of strings.

Scoring

Smallest program in bytes (barring cheating such as network requests) wins. Program can either use real IO or simply define a function.

\$\endgroup\$
  • 1
    \$\begingroup\$ Because there's nothing for the ? to attach to. Try typing /a(?bc)/ into the browser's console. \$\endgroup\$ – TND Nov 4 '15 at 15:16
  • 3
    \$\begingroup\$ Looks good now. You might want to add something like (^a|b)(c$|d) as a test case though. \$\endgroup\$ – Martin Ender Nov 4 '15 at 16:16
  • \$\begingroup\$ Can we assume that the input will contain only printable ASCII characters? In particular, no linefeed characters? \$\endgroup\$ – Martin Ender Nov 4 '15 at 19:25
  • 1
    \$\begingroup\$ Should we consider qualifiers applied on groups i.e. (a)?(b)+(b)+(a)?? \$\endgroup\$ – kennytm Nov 4 '15 at 20:57
  • 1
    \$\begingroup\$ Your list of regex operation is missing (), which is used in your example. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Nov 6 '15 at 3:39
7
\$\begingroup\$

Retina, 136 114 110 bytes

Yo dawg, I heard you like regex...

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

Where <empty> represents an empty trailing line. Run the code from a single file with the -s flag.

...when you wanna reverse regex you should use regex. When you wanna use regex you should use a regex-based programming language.

This code assumes that the input contains neither ; nor ! nor spaces. While I agree that that's a pretty strong and potentially invalid assumption, you could replace those three in the code with any three unprintable characters (like null bytes, bell character, <DEL> you name it), and it wouldn't affect the code size or functionality at all.

I'll add an explanation when I'm done golfing.

\$\endgroup\$
  • 3
    \$\begingroup\$ "I herd* you liek*" \$\endgroup\$ – lirtosiast Nov 5 '15 at 18:00
  • \$\begingroup\$ I think the code also assumes that the regex does not contain any raw new line character. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Nov 6 '15 at 3:03
  • \$\begingroup\$ @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Oh, that is true, I was under the assumption that there will be no unprintable characters in the input. I will fix that once we get clarification from the OP. (If any characters can appear, there are still certain combinations that won't show up in what this challenge considers a valid regex, e.g. ]]], so either way, this answer won't need much modification.) \$\endgroup\$ – Martin Ender Nov 6 '15 at 7:34
  • \$\begingroup\$ done golfing after over a year? :P \$\endgroup\$ – Okx Feb 3 '17 at 16:40
2
\$\begingroup\$

JavaScript ES6, 574 bytes

I can probably remove a few var statements.

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, untested, 559 bytes

Will test at home.

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 bytes

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("");
}
\$\endgroup\$
  • 5
    \$\begingroup\$ lol, you used regex to reverse regex :D \$\endgroup\$ – Cows quack Nov 4 '15 at 17:26
  • 3
    \$\begingroup\$ @ΚριτικσιΛίθος Yes, I did :D I'd use it to parse HTML if I could... \$\endgroup\$ – Conor O'Brien Nov 4 '15 at 17:28
  • 4
    \$\begingroup\$ "if you could" \$\endgroup\$ – Optimizer Nov 4 '15 at 19:12
  • 1
    \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ i parsed html codes with regex but got a serious problem with unicode chars \$\endgroup\$ – Abr001am Nov 4 '15 at 19:21
  • 2
    \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ This is an alternative: `code.replace(/.*/, "trollolol"); \$\endgroup\$ – Cows quack Nov 4 '15 at 20:09
2
\$\begingroup\$

JavaScript ES6, 343 bytes

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]

Original code (the functions, but without 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]

The code is implemented as a recursive top-down parser, so it may cause stack overflow on deeply nested input.

The code may cause infinite loop in invalid cases, since I don't test them, taking advantage of the "undefined behavior" clause.

\$\endgroup\$
0
\$\begingroup\$

Python 3, 144 bytes

(This one does not support qualifiers on a group like (a)+(b)*(cde)?.)

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

Test cases:

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))

Result:

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.